[AHOI2009]中国象棋---------------递推

题目描述

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

输入输出格式

输入格式：

一行包含两个整数N，M，之间由一个空格隔开。

输出格式：

总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

输入输出样例

输入样例#1：

1 3

输出样例#1：

7

说明

样例说明

除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

　　　　因为每行每列只能够放置两枚棋子，所以考虑如何完全表示当前状态。

　　　　• f【i】【j】【k】【q】表示到第 i 行为止，有 j 列上有零枚棋子，有 k 列上有一枚棋子，还有 q 列上有两枚棋子的状态的方案数。

　　　　• 由于对于任意一种合法的状态必然满足 j+k+q=m 。所以我们可以省略掉一维。

　　　　• 考虑转移，我们可以用大量的讨论来枚举每一行的棋子放在哪种列中，然后就可以愉快的 AC 了。

#include<bits/stdc++.h>
#define p 9999973
#define ll long long
using namespace std;
int n,m;
ll f[105][105][105],s,q,ans;
int main()
{
    scanf("%d%d",&n,&m);
    f[0][0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=m;++j)
            for(int k=0;j+k<=m;++k)
                if(f[i-1][j][k])
                {
                    s=f[i-1][j][k];
                    q=m-j-k;
                    (f[i][j][k]+=s)%=p;
                    if(q-1>=0) (f[i][j+1][k]+=s*q)%=p;
                    if(j-1>=0) (f[i][j-1][k+1]+=s*j)%=p;
                    if(q-2>=0) (f[i][j+2][k]+=s*(q*(q-1)/2))%=p;
                    if(j-2>=0) (f[i][j-2][k+2]+=s*(j*(j-1)/2))%=p;
                    if(q-1>=0&&j-1>=0) (f[i][j][k+1]+=s*q*j)%=p;
                }
    for(int i=0;i<=m;++i)
        for(int j=0;i+j<=m;++j)
            (ans+=f[n][i][j])%=p;
    printf("%lld",ans);
    return 0;
}

　　　　　　这是这题的升级版，如果讨论的话难免出错，就算不出错的话，也很浪费时间。

　　　　　　为了避免大量的讨论我们可以用多重循环或者dfs，那么就只需要确保转移的过

　　　　　　程合法就不会有问题了。

#include<bits/stdc++.h>
#define p 19890604
#define ll long long
using namespace std;
int n,m;
ll f[2][66][66][66],vx,vy,vz,s,q,ans;
void c(int a,int b,ll &pos)
{
    pos=1;
    for(int i=0;i<b;++i)
        pos*=(a-i);
    for(int i=1;i<=b;++i)
        pos/=i;
}
int main()
{
    scanf("%d%d",&n,&m);
    f[0][m][0][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=m;++j)
            for(int k=0;j+k<=m;++k)
                for(int q=0;j+k+q<=m;++q)
                    f[i&1][j][k][q]=0;
        for(int j=0;j<=m;++j)
            for(int k=0;j+k<=m;++k)
                for(int q=0;j+k+q<=m;++q)
                    if(f[i&1^1][j][k][q])
                        for(int x=0;x<=3&&x<=j;++x)
                        {
                            c(j,x,vx);
                            for(int y=0;x+y<=3&&y<=k&&k-y+x<=m;++y)
                            {
                                c(k,y,vy);
                                for(int z=0;x+y+z<=3&&z<=q&&q-z+y<=m;++z)
                                {
                                    c(q,z,vz);
                                    (f[i&1][j-x][k-y+x][q-z+y]+=f[i&1^1][j][k][q]*vx%p*vy%p*vz%p)%=p;
                                }
                            }
                        }
    }
    for(int i=0;i<=m;++i)
        for(int j=0;i+j<=m;++j)
            for(int k=0;i+j+k<=m;++k)
                (ans+=f[n&1][i][j][k])%=p;
    printf("%lld",ans);
    return 0;
}