about 4 years ago

显然,每行不超过2个炮,每列不超过两个炮.

进而发现,解的个数和具体每一列的状态无关,具体点说,解数就是只和当前有1个炮的列数与有2个炮的列数有关
由于只和列数有关,而和具体是哪些列无关,我们就可以得出一个dp方程来


具体转移分当前这行不放棋子,放一个棋子,放两个棋子分开来讨论。 具体实现略有复杂,我就放代码吧。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define mo 9999973LL
using namespace std;
typedef long long LL;
int n,m;
LL f[111][111][111];
LL c[111];
LL ans=0;
int main()
{
    cin>>n>>m;
    for (int i=0;i<=m;++i)
        c[i]=i*(i-1)/2;
    f[0][0][0]=1;
    for (int i=1;i<=n;++i)
        for (int j=0;j<=m;++j)
            for (int k=0;k<=m;++k)
            {
                if (k+j>m) break;
                f[i][j][k]=f[i-1][j][k];
                if (k>0) f[i][j][k]+=f[i-1][j+1][k-1]*(LL)(j+1)%mo;
                if (j>0) f[i][j][k]+=f[i-1][j-1][k]*(LL)(m-j-k+1)%mo;
                if (k>1) f[i][j][k]+=f[i-1][j+2][k-2]*c[j+2]%mo;
                if (j>1) f[i][j][k]+=f[i-1][j-2][k]*c[m-k-j+2]%mo;
                if (j>0&&k>0) f[i][j][k]+=f[i-1][j][k-1]*(LL)(m-k-j+1)*(LL)(j)%mo;
                f[i][j][k]%=mo;
                if (i==n) ans+=f[i][j][k];
                ans%=mo;
            }
    cout<<ans<<endl;
    return 0;
}
← BZOJ2820 YY的GCD 单位根的妙用 PYXFIB & Guideposts →
 
comments powered by Disqus