DP，递推，组合数
其实相当于就是一个递推推式子，然后要用到一点组合数的知识
一道很妙的题，因为不能互相攻击，所以任意行列不能有超过两个炮
首先令f[i][j][k]代表前i行，有j列为一个炮，有k列为两个炮的方案
那么有如下转移：
1,这行不放炮，add+=f[i-1][j][k];
2,放一个炮，并且放在没有炮的那列 add+=f[i-1][j-1][k] * (m - j - k + 1);,因为放了这个炮后，
一个炮的变多了，也就是上一行的j+1得到这一行的j，所以上一行的j就是j-1，
又因为有m - (j - 1) - k列没有炮的，所以有乘上m- j - k + 1种方案
3,放一个炮，并且放在原先有一个炮的那列，add+=f[i-1][j+1][k-1] * (j + 1);
放了这个炮后，一个炮的变少了一个，两个炮的变多了一个，所以还回去就是j+1,k-1，
又因为有j+1列一个炮的，所以有j+1种方案放置
4,放两个炮，都放在没有炮的列上面，add+=f[i-1][j-2][k] * (m - j - k + 2) * (m - j - k + 1) / 2;
那么放了炮后，一个炮的变多了2列，所以还回去是j-2,又因为有(m - j - k + 2)列空的，所以就是在这些里面选两个组合，所以组合数计算
5,放两个炮，分别放在有炮的和没有炮的，add+=f[i-1][j][k-1] * (m - j - k + 1) * j;
因为没有炮 --- > 1个炮 ---> j++
一个炮 ---> 2个炮 ---> j--，k++
相当于j没有变化，而k要还回去，所以是f[i-1][j][k-1]
又因为有(m - j - k + 1)列空的，j列一个炮的，所以相乘得到方案
6,放两个炮，都放在原来有炮的，add+=f[i-1][j+2][k-2] * (j + 2) * (j + 1) / 2;
放了炮后，j-=2,k+=2,所以还回去就是j+2,k-2,
又因为有j+2列一个炮，选两个组合，所以就是(j + 2) * (j + 1) / 2
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define mod 9999973 5 #define AC 110 6 #define LL long long 7 int n,m,ans; 8 LL f[AC][AC][AC]; 9 void work() 10 { 11 scanf("%d%d",&n,&m); 12 f[0][0][0]=1; 13 for(R i=1;i<=n;i++)//枚举行 14 for(R j=0;j<=m;j++)//枚举一个炮有多少列 15 { 16 int all=m-j;//因为要保证j+k<=m 17 for(R k=0;k<=all;k++)//枚举两个炮有多少列 18 { 19 LL add=0;//用一个变量存增量，避免多次访问3维数组，也许可以加速？ 20 add+=f[i-1][j][k]; 21 if(j) add+=f[i-1][j-1][k] * (m - j - k + 1); 22 if(k && j + 1 <= m) add+=f[i-1][j+1][k-1] * (j + 1);//有j+1列一个炮可以选 23 if(j - 2 >= 0) add+=f[i-1][j-2][k] * (m - j - k + 2) * (m - j - k + 1) / 2; 24 if(k - 1 >= 0) add+=f[i-1][j][k-1] * (m - j - k + 1) * j; 25 if(j + 2 <= m && k - 2 >= 0) add+=f[i-1][j+2][k-2] * (j + 2) * (j + 1) / 2; 26 if(add > mod) add%=mod; 27 f[i][j][k]=add; 28 } 29 } 30 for(R j=0;j<=m;j++)//枚举最后的情况是怎么样的 31 { 32 int all=m-j; 33 for(R k=0;k<=all;k++) 34 ans=(ans + f[n][j][k])%mod; 35 } 36 printf("%d ",ans); 37 } 38 39 int main() 40 { 41 freopen("in.in","r",stdin); 42 work(); 43 fclose(stdin); 44 return 0; 45 }