淘先锋技术网

首页 1 2 3 4 5 6 7

1801: [Ahoi2009]chess 中国象棋

题目:传送门

 

题解:

   表示自己的DP菜的抠脚

   %题解...

   定义f[i][j][k]表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数 (对于任意的一行或者一列,棋子数都不会超过2)

   那么以下的转移其实就很容易YY了:

   对于当前的第i行,一共分为6种情况:

   1、啥玩意儿都不填 f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j+1-k))%mod;

   2、只填一个棋子,并且填在当前没有棋子的一列 f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j+1-k))%mod;

    因为对于上一个状态来说,只有一个棋子的就多了一列啊

   3、只填一个棋子,并且填在当前仅有一个棋子的一列 f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod;

    很明显两个棋子的列数多了一,且一个棋子的列数少了一

   以下三种和前面的都一样,就不解释了:

   4、填两个棋子,并且都填在当前没有棋子的列上 f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*calc(m-j+2-k))%mod;

   5、填两个棋子,一个填在有一个棋子的列上,一个填在没有棋子的列上 f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1))%mod;

   6、填两个棋子,都填在有一个棋子的列上 f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*calc(j+2))%mod;

   PS:calc(int x){return x*(x-1)/2;}

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define qread(x) x=read()
 7 using namespace std;
 8 typedef long long LL;
 9 const LL mod=9999973;
10 inline int read()
11 {
12     int f=1,x=0;char ch;
13     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return f*x;
16 }
17 int n,m;
18 LL f[110][110][110];//f[i][j][k] 表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数 
19 LL calc(int x){return x*(x-1)/2;}
20 int main()
21 {
22     qread(n);qread(m);
23     memset(f,0,sizeof(f));
24     f[0][0][0]=1LL;
25     for(int i=1;i<=n;i++)
26         for(int j=0;j<=m;j++)
27             for(int k=0;k<=m-j;k++)
28             {
29                 f[i][j][k]=f[i-1][j][k];
30                 if(j>0)f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j+1-k))%mod;
31                 if(k>0)f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod;
32                 if(j>1)f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*calc(m-j+2-k))%mod;
33                 if(j>0 && k>0)f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1))%mod;
34                 if(k>1)f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*calc(j+2))%mod;
35             }
36     LL ans=0;
37         for(int j=0;j<=m;j++)
38             for(int k=0;k<=m-j;k++)
39                 ans=(ans+f[n][j][k])%mod;
40     printf("%lld\n",ans);
41     return 0;
42 }

 

感觉很毒瘤。。。

 

转载于:https://www.cnblogs.com/CHerish_OI/p/8149164.html