algospot - poly

//poly
 
#include <iostream>
#include <vector>
using namespace std;
 
#define MOD 10000000
 
int N;
vector<vector<int>> cache;
 
void init()
{
    cin >> N;
    cache = vector<vector<int>>(N + 1, vector<int>(N + 1, -1));
}
 
int dp(int n, int first)
{
    if (n == first)
        return 1;
 
    int &ret = cache[n][first];
    if (ret != -1)
        return ret;
    ret = 0;
 
    for (int i = 1; i <= n - first; ++i)
    {
        ret += (first + i - 1) * dp(n - first, i);
        ret %= MOD;
    }
    return ret;
}
 
int main()
{
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        int ans = 0;
        for (int i = 1; i <= N; ++i)
        {
            ans += dp(N, i);
            ans %= MOD;
        }
        cout << ans << "\n";
    }
}

 

 

 

 

 

 

https://www.algospot.com/judge/problem/read/POLY

algospot.com :: POLY

 

 

 

 

 

 

poly

C(n, first) : 맨 윗줄이 first개인 n개의 폴리의 가짓수

C(n, first)는 각각의 C(n-first, i) (1 <= i <= n-first) 들과 조합할수 있는 가짓수의 합입니다!

각각의 C(n-first, i)와는 first + i - 1 가지의 조합을 만들어 낼수 있습니다!

 

 

<poly 점화식>