[DP][计数DP][组合数学] HDU 6377 度度熊看球赛

https://cn.vjudge.net/problem/HDU-6377

不懂dp的我根本想不到是用dp来做。。。emm

如果把每一对情侣两个人看成等价的，那么可以构造出来，状态只与两个因素有关：一共有多少对情侣；有多少对情侣是坐在一起的，用dp[i][j]来表示有i对情侣，其中j对坐在一起的方案数，在这个的基础上可以往里面继续插入一对新的情侣，而插入的方式和结果总共会导致五种变化，每次都考虑一下，刷表即可。预处理出所有的可能情况，接下来每次输入的时候过一遍dp[n][i]就行了。由于把两个人看成了一样的，所以最后还要乘上2^n，用快速幂即可。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int maxn=1e3+5;
const int MOD=998244353;


int f[maxn][maxn],n2[maxn];

void init()
{
    n2[0]=1;
    for (int i=1; i<=1000; i++)
        n2[i]=2LL*n2[i-1]%MOD;
    f[1][1]=1;
    f[1][0]=0;
    for (int i=1; i<=1000; i++)
        for (int j=0; j<=i; j++)
        {
            f[i+1][j]=(1LL*f[i][j]*j+f[i+1][j])%MOD;
            f[i+1][j+1]=(1LL*f[i][j]*(2*i-j+1)+f[i+1][j+1])%MOD;
            if(j>=2)
                f[i+1][j-2]=(1LL*f[i][j]*j*(j-1)/2+f[i+1][j-2])%MOD;
            if(j>=1)
                f[i+1][j-1]=(1LL*f[i][j]*j*(2*i-j+1)+f[i+1][j-1])%MOD;
            f[i+1][j]=(1LL*f[i][j]*(2*i-j+1)*(2*i-j)/2+f[i+1][j])%MOD;
        }
}

LL pow2(LL a,LL p)
{
    LL ans=1;
    a%=MOD;
    while(p)
    {
        if(p&1)
            ans=ans*a%MOD;
        a=(a%MOD)*(a%MOD)%MOD;
        p>>=1;
    }
    return ans;

}

int main()
{
    init();
    int ans,n,d,k;
    while(~scanf("%d%d",&n,&d))
    {
        ans=0;
        for (int i=0;i<=n;i++)
            ans=(1LL*ans+f[n][i]*pow2(d,i))%MOD;
        ans=1LL*ans*n2[n]%MOD;
        printf("%d\n",ans);
    }
    return 0;
}