济南学习 Day 5 T1 am

炮(cannon)
【题目描述】
众所周知，双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须
隔一个棋子跳吃，即俗称“炮打隔子”。炮跟炮显然不能在一起打起来，于是rly
一天借来了许多许多的炮在棋盘上摆了起来……他想知道，在N×M的矩形方格
中摆若干炮（可以不摆）使其互不吃到的情况下方案数有几种。
棋子都是相同的。
【输入说明】
一行，两个正整数N和M。
【输出说明】
一行，输出方案数mod 999983。
【样例输入】
1 3
【样例输出】
7
【数据范围】
对于40%的数据,N<=4,M<=4
对于70%的数据,N<=100,M<=8
对于100%的数据,N<=100,M<=100

 /*

   动态规划，状态的表示很巧妙

   f[i][j][k]表示放了前i行，有j列放了1个，有k列放了2个，那么就有m-i-j列没放的方案数。然后完成转移。

 */

 #include<cstdio>

 #include<iostream>

 #define mod 999983LL

 #define N 110

 using namespace std;

 long long f[N][N][N],n,m;

 int main()

 {

     cin>>n>>m;

     f[][][]=;

     for(long long i=;i<=n;i++)

       for(long long j=;j<=m;j++)

         for(long long k=;j+k<=m;k++)

         {

             f[i][j][k]=f[i-][j][k];f[i][j][k]%=mod;//不放

             if(j>=)f[i][j][k]+=f[i-][j-][k]*(m-j-k+);f[i][j][k]%=mod;//空处放1个

             if(k>=)f[i][j][k]+=f[i-][j+][k-]*(j+);f[i][j][k]%=mod;//1个处放1个

             if(j>=)f[i][j][k]+=f[i-][j-][k]*(m-j-k+)*(m-j-k+)/;f[i][j][k]%=mod;//空处放2个

             if(k>=)f[i][j][k]+=f[i-][j+][k-]*(j+)*(j+)/;f[i][j][k]%=mod;//1处放2个

             if(k>=)f[i][j][k]+=f[i-][j][k-]*j*(m-j-k+);f[i][j][k]%=mod;//空处和1个处

         }

     long long ans=;

     for(long long j=;j<=m;j++)

       for(long long k=;j+k<=m;k++)

         ans+=f[n][j][k],ans%=mod;

     printf("%d",ans);

     return ;

 }

巴特西

济南学习 Day 5 T1 am

最新文章

热门文章