题目链接
题解
不好形容的DP。设$f(i,j,k)$表示当前在第$i$行,有$j$列没炮,$k$列$1$个炮。就可以愉快的转移了。
转移的时候注意系数。(也就是组合数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 #define Mod 9999973ll using namespace std; typedef long long ll; int (){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } ll n,m,f[105][105][105]={0};
void init(){ n=read(),m=read(); f[1][m][0]=1,f[1][m-1][1]=m; if(m!=1)f[1][m-2][2]=m*(m-1)/2; } void solve(){ for(int i=2;i<=n;i++) for(ll j=0;j<=m;j++) for(ll k=0;k+j<=m;k++){ f[i][j][k]+=f[i-1][j][k]; if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*(j+2)*(j+1)/2; if(j+1<=m)f[i][j][k]+=f[i-1][j+1][k]*(j+1)*k; if(k+2<=m)f[i][j][k]+=f[i-1][j][k+2]*(k+2)*(k+1)/2; if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1); if(k+1<=m)f[i][j][k]+=f[i-1][j][k+1]*(k+1); f[i][j][k]%=Mod; } ll ans=0; for(int j=0;j<=m;j++) for(int k=0;k+j<=m;k++) ans=(ans+f[n][j][k])%Mod; printf("%lldn",ans); } int main(){ init(); solve(); return 0; }
|
近期评论