自动搬运

查看原文

来自洛谷，原作者为

	Blunt_Feeling 快来卷题！

搬运于2025-08-24 22:15:13，当前版本为作者最后更新于2020-07-16 17:39:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5879 放棋子 题解

这道题的状态转移方程有点难推。首先看一张状态表：

1. 这张表表示什么？

在这个表中，行数 $i$ 从下往上递增，列数 $j$ 从右往左递增，$f_{i,j}$ 表示在第 $i$ 行摆 $j$ 个棋子时的方案数，且想求摆 $i$ 行的方案数，只要算出 $f_{i,1}+f_{i,2}+f_{i,3}+…+f_{i,i}$ 即可。

2. 怎么推？

首先，对于所有 $i$，$f_{i,0}$ 都为 $1$，因为什么都不放也是一种放法；还要把 $f_{1,1}$ 设为 $1$。——以上为初始化。接下来：

第二行

1. 在第二行放一个的时候，第一行可以放一个也可以不放，有 $2$ 种放法，于是 $f_{2,1}=2$；
2. 在第二行放两个的时候，第一行可以放一个也可以不放，有 $2$ 种放法，于是 $f_{2,2}=2$。

第三行

1. 在第三行放一个的时候，第二行可以放一个也可以不放，有 $f_{2,1}+f_{2,0}=3$ 种放法，于是 $f_{3,1}=3$；
2. 在第三行放两个的时候，第二行可以放两个、一个也可以不放，有 $f_{2,2}+f_{2,1}+f_{2,0}=5$ 种放法，于是 $f_{3,2}=5$；但是在这里，$f_{2,1}+f_{2,0}$ 刚好是 $f_{3,1}$，所以 $f_{3,2}=f_{2,2}+f_{3,1}=5$；
3. 在第三行放三个的时候，第二行可以放两个、一个也可以不放，所以 $f_{3,3}=f_{3,2}=5$。

第四行

1. 在第四行放一个的时候，第三行可以放一个也可以不放，有 $f_{3,1}+f_{3,0}=4$ 种放法，于是 $f_{4,1}=4$；
2. 在第四行放两个的时候，第三行可以放两个、一个也可以不放，有 $f_{3,2}+f_{3,1}+f_{3,0}=9$ 种放法，于是 $f_{4,2}=9$；但是在这里，$f_{3,1}+f_{3,0}$ 刚好是 $f_{4,1}$，所以 $f_{4,2}=f_{3,2}+f_{4,1}=9$；
3. 在第四行放三个的时候，第三行可以放三个、两个、一个也可以不放，有 $f_{3,3}+f_{3,2}+f_{3,1}+f_{3,0}=14$ 种放法，于是 $f_{4,3}=14$；但是在这里，$f_{3,2}+f_{3,1}+f_{3,0}$ 刚好是 $f_{4,2}$，所以 $f_{4,3}=f_{3,3}+f_{4,2}=14$；
4. 在第四行放四个的时候，第三行可以放三个、两个、一个也可以不放，所以 $f_{4,4}=f_{4,3}=14$。

如果你耐心地看到这里，那么恭喜你，此题的状态转移方程已经一目了然了：

3. 高精度

此题输出的结果非常大，当 $n=100$ 时，输出的答案居然有 $58$ 位之长。你可以乖乖写高精，也可以像我一样，把一个数用两个__int128压位存储，偷个懒。

4. Code

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
const int maxn=110;
inline void write(__int128 x) { //用来输出__int128
    if(x<0) { putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+48);
}
int n;
__int128 M=1,f[maxn][maxn][2],ans[2]; //把一个数用两个__int128压位存储
int main()
{
	cin>>n;
	For(i,1,n) f[i][0][0]=1;
	For(i,1,30) M*=10; //构造一个30位的取模数，方便压位
	For(i,1,n)
		For(j,1,i)
		{
			f[i][j][0]=(f[i][j-1][0]+f[i-1][j][0])%M; //压位，状方在前文已经讲过了
			f[i][j][1]=f[i][j-1][1]+f[i-1][j][1]+(f[i][j-1][0]+f[i-1][j][0])/M;
		}
	For(i,1,n) ans[0]+=f[n][i][0];
	ans[1]=ans[0]/M; //处理进位（很容易写错）
	ans[0]%=M;
	For(i,1,n) ans[1]+=f[n][i][1];
	if(ans[1]!=0)
	{
		write(ans[1]);
		if(ans[0]<=M/10) cout<<0; //用一个比较讨巧的方法处理首位是0的情况
	}
	write(ans[0]);
	cout<<endl; //可省
	return 0;
}

5. 后话

• 关于__int128的使用，可以参考我的这篇文章。
• 十分感谢
  https://www.luogu.com.cn/user/235855
  的帮助！
• 因为__int128在正式比赛中不能使用，所以你可以先用__int128打表，再把打表程序交上去。限于篇幅，想看打表程序请阅读这篇文章。