题解 P5879 【放棋子】

· · 题解

P5879 放棋子 题解

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

4 3 2 1 0
4 14 14 9 4 1
3 5 5 3 1
2 2 2 1
1 1 1

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。

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

f_{i,j} = f_{i-1,j} + f_{i,j-1}

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. 后话