题目大意是这样的:
无论行与列,都必须满足炮的数量$\le 2$
所以我们需要设计一个方程来满足这两个条件。
状态可以描述列的正确性
转移可以描述行的正确性
因此就有状态$f_{i,j,k}$表示前$i$行,有$j$列有一个炮,有$k$列有两个炮,有$m-j-k$列没有炮的方案数。
转移可以描述成,第$i$行不放,放一个,放两个。
具体请自行实现。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=105,mod=9999973;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(ll x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
ll f[N][N][N];
int main()
{
int n,m;qr(n),qr(m);
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-j;k++)
{
int z=(m-j-k);
f[i][j][k]=f[i-1][j][k];
if(j>=1)f[i][j][k]+=f[i-1][j-1][k]*(z+1);
if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);
if(k>=1)f[i][j][k]+=f[i-1][j][k-1]*j*(z+1);
if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*((j+2)*(j+1)/2);
if(j>=2)f[i][j][k]+=f[i-1][j-2][k]*((z+2)*(z+1)/2);
f[i][j][k]%=mod;
}
ll ans=0;
for(int j=0;j<=m;j++)
for(int k=0;k<=m-j;k++)
ans=(ans+f[n][j][k])%mod;
qw(ans);puts("");
return 0;
}
最后一次更新于2020-05-13
0 条评论