https://ac.nowcoder.com/acm/contest/554/A

看到神仙们的代码真的长知识了，以为是出题人忘了mod，结果居然是故意玩大数，写爆了啊。

然后发现了神仙们的大数原来是分块的，get

1、考虑某一行，如果这一行的下一行没有棋子，那么这是一种，所以将每一行没有棋子的情况初始化为1

2、假设当前第  行放了  个棋子并且第  行放棋子的方案数都知道 ，那么当前情况的方案数就等于第 行放 到个数字的方案数的总和。所以递推式为

3、然后发现要用大数？分块大法好。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e8;
const int N = 105;
ll dp[N][N][100];
ll ans[100];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i <= n; i++)
			dp[i][0][1] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			for (int k = 0; k <= j; k++)
				for (int l = 1; l < 10; l++)
				{
					dp[i][j][l] = dp[i][j][l] + dp[i - 1][k][l];
					if (dp[i][j][l] > mod)
					{
						dp[i][j][l + 1] += dp[i][j][l] / mod;
						dp[i][j][l] %= mod;
					}
				}
	for (int i = 1; i <= n; i++)
		for (int l = 1; l < 10; l++)
		{
			ans[l] += dp[n][i][l];
			if (ans[l] > mod)
			{
				ans[l + 1] += ans[l] / mod;
				ans[l] %= mod;
			}
		}
	for (int l = 10; l >= 1; l--)
	{
		if (ans[l] != 0)
		{
			printf("%d", ans[l]);
			l--;
			while (l >= 1)
			{
				printf("%08lld", ans[l]);
				l--;
			}
		}
	}
}
/*
16 129644789
17 477638699
*/