最近智商有点不在线。其实一直不在线。

题目


先是想用$f[i][j][k][0/1/2]$表示摆了i行时有j列空着,k列有了一个炮,且当下摆了0/1/2个的状态,转移方程写的出来但是极其繁琐。于是又设法听取评讲者题解修改状态,最后的012完全可以删去。那么仍可以表示这一行那些列摆过1个,那些列摆过0个的种类。转移时分类即可。

$f[i][j][k]+=f[i-1][j][k]$ 什么都不摆

$f[i][j][k]+=(j+1)*f[i-1][j+1][k-1]$  摆1个炮

$f[i][j][k]+=(k+1)*f[i-1][j][k+1]$  摆1个炮

$f[i][j][k]+=(j+1)*(j+2)/2*f[i-1][j+2][k-2]$  摆两个炮,下同

$f[i][j][k]+=(k+1)*(k+2)/2*f[i-1][j][k+2]$

$f[i][j][k]+=k*(j+1)*f[i-1][j+1][k]$

注意边界就行。

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=(x<<)+(x<<)+(c^),c=getchar();return f?x=-x:x;
}
const int N=+,P=;
int n,m,ans,f[N][N][N]; inline void inc(int&x,int y){(x+=y)>=P?x-=P:;} int main(){//freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);
read(n),read(m);if(m<){printf("%d\n",+n+(n)*(n-)/);return ;}
f[][m][]=,f[][m-][]=m,f[][m-][]=m*(m-)/;
for(register int i=;i<=n;++i)
for(register int j=;j<=m;++j)
for(register int k=;k<=m-j;++k){
inc(f[i][j][k],f[i-][j][k]);
if(k)inc(f[i][j][k],(j+)*f[i-][j+][k-]%P);
inc(f[i][j][k],(k+)*f[i-][j][k+]%P);
if(k>=)inc(f[i][j][k],((j+)*(j+)>>)*1ll*f[i-][j+][k-]%P);
inc(f[i][j][k],((k+)*(k+)>>)*1ll*f[i-][j][k+]%P);
inc(f[i][j][k],1ll*k*(j+)*f[i-][j+][k]%P);
}
for(register int i=;i<=m;++i)for(register int j=;j<=m-i;++j)inc(ans,f[n][i][j]);
printf("%d\n",ans);
return ;
}
05-28 11:25