ZOJ 3791 An easy game DP+组合数

给定两个01序列，每次操作可以任意改变其中的m个数字 0变 1 1 变 0，正好要变化k次，问有多少种变法

dp模型为dp[i][j]，表示进行到第i次变化，A,B序列有j个不同的变法总和。

循环k次，每次针对m，向那j个不同分1-j个即可，不过要用到组合数，因为对每个数操作不同都不一样

最后结果就是 dp[k][0]

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define LL long long

using namespace std;

LL dp[][];

LL c[][];

int n,m,k,len;

char s1[],s2[];

const LL M=+;

void init()

{

    c[][]=;

    for (int i=;i<;i++){

        c[i][]=;

        for (int j=;j<=i;j++){

            c[i][j]=c[i-][j-]+c[i-][j];

            c[i][j]%=M;

        }

    }

}

int main()

{

    init();

    while (scanf("%d%d%d",&n,&k,&m)!=EOF)

    {

        scanf("%s%s",s1,s2);

        int a=;

        for (int i=;i<n;i++){

            if (s1[i]!=s2[i]){

                a++;

            }

        }

        memset(dp,,sizeof dp);

        dp[][a]=;

        for (int i=;i<k;i++){

            for (int j=;j<=n;j++){

                if (dp[i][j]){

                    for (int q=;q<=min(m,j);q++){

                        int sta=j+m-*q;

                        dp[i+][sta]+=c[j][q]*c[n-j][m-q]%M*dp[i][j]%M;

                        if (dp[i+][sta]>=M) dp[i+][sta]%=M;

                    }

                }

            }

        }

        printf("%lld\n",dp[k][]);

    }

    return ;

}

巴特西

ZOJ 3791 An easy game DP+组合数

最新文章

热门文章