[hdu6391]Lord Li's problem

首先发现结果与需要改变的具体位置无关，只和需要改变的位置的个数有关，因此设f[i][j]表示选取了i个数字异或结果有j个1，只要分析接下来选择的数和这j个1有几个重合即可：

1. 三个数字全部重合，即$f[i][j+3]+=f[i-1][j]\cdot c(n-j,3)$

2. 有两个数字重合，即$[i][j+1]+=f[i-1][j]\cdot c(n-j,2)\cdot j$

3. 有一个数字重合，即$f[i][j-1]+=f[i-1][j]\cdot (n-j)\cdot c(j,2)$

4. 有0个数字重合，即$f[i][j-3]+=f[i-1][j]\cdot c(j,3)$

然而这并不正确，因为不能重复选择，因此去掉($c(n,3)-(i-2))\cdot f[i-2][j]$，同时这里我们考虑了操作的顺序和操作的位置，再除以$n!\cdot c(n,m)$才是最终答案。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define mod 19260817

 4 int n,m,t,sum,inv[101],fac[101],f[101][101];

 5 char s1[101],s2[101];

 6 int c(int n,int m){

 7     return 1LL*fac[n]*inv[n-m]%mod*inv[m]%mod;

 8 }

 9 int cc(int n,int m){

10     return 1LL*inv[n]*fac[n-m]%mod*fac[m]%mod;

11 }

12 int main(){

13     inv[0]=inv[1]=fac[0]=fac[1]=1;

14     for(int i=2;i<=40;i++)fac[i]=1LL*fac[i-1]*i%mod;

15     for(int i=2;i<=40;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

16     for(int i=2;i<=40;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;

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

18         if ((!n)&&(!m))return 0;

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

20         sum=0;

21         for(int i=0;i<n;i++)

22             if (s1[i]!=s2[i])sum++;

23         memset(f,0,sizeof(f));

24         f[0][0]=1;

25         for(int i=0;i<=m;i++)

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

27                 if (i>1)f[i][j]=(f[i][j]-f[i-2][j]*(i-1LL)%mod*(c(n,3)-i+2)%mod+mod)%mod;

28                 for(int k=-1;k<3;k++)

29                     if ((n>j+k)&&(j+k>1))

30                         f[i+1][j+2*k-1]=(f[i+1][j+2*k-1]+1LL*c(n-j,k+1)*c(j,2-k)*f[i][j])%mod;

31             }

32         printf("Case #%d: %d\n",++t,1LL*f[m][sum]*cc(n,sum)%mod*inv[m]%mod);

33     }

34 }

巴特西

[hdu6391]Lord Li's problem

最新文章

热门文章