http://www.lydsy.com/JudgeOnline/problem.php?id=1801
在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法
100%的数据中N,M不超过100
容易发现每行每列最多两个
然后就不会了...看了别人的状态表示:
$f[i][j][k]$表示前$i$行有$j$列放了$1$个$k$列放了$2$个
因为只有那些行放了几个影响当前转移
然后转移自己随便写写就行了....注意$j$可能需要减
$1A$啦啦啦
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <set> using namespace std; typedef long long ll; const int N=105,P=9999973; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m; ll f[N][N][N]; inline int C2(int n){return n*(n-1)/2;} void dp(){//printf("dp %d %d ",m,n); f[0][0][0]=1; for(int i=0;i<m;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n&&n-j-k>=0;k++) if(f[i][j][k]){//printf("update %d %d %d ",i,j,k); ll now=f[i][j][k]; (f[i+1][j][k]+=now)%=P; if(j<n) (f[i+1][j+1][k]+=now*(n-j-k))%=P; if(j>=1) (f[i+1][j-1][k+1]+=now*j)%=P; if(j+2<=n) (f[i+1][j+2][k]+=now*C2(n-j-k))%=P; if(j>=2&&k+2<=n) (f[i+1][j-2][k+2]+=now*C2(j))%=P; if(k<n) (f[i+1][j][k+1]+=now*(n-j-k)*j)%=P; } //for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) printf("f %d %d %d %lld ",i,j,k,f[i][j][k]); ll ans=0; for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) ans=(ans+f[m][j][k])%P;//printf("hi %d %d %lld ",j,k,f[m][j][k]); printf("%lld",ans); } int main(){ freopen("in","r",stdin); m=read();n=read(); if(n>m) swap(m,n); dp(); }