8_14.cpp

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 10 * 1000 * 1000;
long long poly(vector<vector<long long>> D, int N) {
	for (int n = 1; n <= N; n++) {
		for (int down = 1; down <= n; down++) {
			for (int i = 1; i <= n - down; i++) {
				D[n][down] += D[n - down][i] * (down + i - 1);
			}
			if (n == down)
				D[n][down] = 1;
			D[n][down] %= MOD;
		}
	}

	long long ans = 0;
	for (int down = 1; down<= N; down++) {
		ans += D[N][down];
		ans %= MOD;
	}

	return ans ;
}

int main() {
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int n; cin >> n;
		vector<vector<long long>> D(101, vector<long long>(101));
		cout << poly(D, n) << endl;;
	}
	return 0;
}

다른 풀이

#pragma once
#include<cstdio>
#include<cstring>
 
int poly[101][101] = { 0 };
const int MOD = 10000000;
 
int getPOLY(int nums, int down)
{
    int& ret = poly[nums][down];
 
    if (nums == down)
    {
        return ret = 1;
    }
 
    if (ret != -1) return ret;
 
    ret = 0;
 
    int blocks = nums - down;
    for (int i = 1; i <= blocks; i++)
    {
        ret += (i + down - 1) * getPOLY(blocks, i);
        ret %= MOD;
    }
 
    return ret;
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        int n;
        scanf("%d\n", &n);
 
        memset(poly, -1, sizeof(poly));
 
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            res += getPOLY(n, i);
            res %= MOD;
        }
 
        printf("%d\n", res);
    }
 
    return 0;
}

https://sangdo913.tistory.com/41