[数位dp][斯特林反演] Jzoj P5765 相互再归的鹅妈妈

阅读量：4318 次

发布时间：2019-06-06

本文共 1639 字，大约阅读时间需要 5 分钟。

Description

Input

Output

Sample Input

Input 13 1101Input 24 310Input 35 1001

Sample Output

Output 11Output 21978Output 3598192244

Data Constraint

对于所有数据，保证满足m<=50000

题解

题目大意：选出n个0~R-1的数，两两不能相同，要使得这n个数的异或和为0，求方案数

要求求无序方案，可以转化为求有序方案，最后除n!

现在，考虑一下，如果不要求两两不能相同（就是可以相同），可以怎么做

枚举脱离限制的位置（该位置在R中必须为1），脱离限制也就是说后面怎样选都不会超过R（也就是R为1的位置选了0）

可以用g(n)表示，选n个数异或值为0的方案数

然后，考虑加上两两必须不同

可以用斯特林反演式子来求容斥

式子：[?=1]=∑︀∏︀(?,?=1)(?[?] − 1)!(−1)^?[?]−1

枚举一个m的集合划分，其实k就是这种集合划分方案的几何数，而a表示各个集合的大小（可以用dfs实现）

注意，答案最后要除于n!，要用逆元做

代码

1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 5000010 5 #define N 8 6 #define ll long long 7 #define up(x,y) x=(x+(y))%mod 8 using namespace std; 9 const int mod=1000000007;10 int n,m,K,w[M],p2[M][N],pw[M][N];11 ll g[N],C[N][N],f[N],fac[N],ans;12 char s[50010];13 bool a[M];14 ll ksm(ll a,ll b)15 {16     ll r=1;17     for(;b;b>>=1,a=a*a%mod) if(b&1) r=r*a%mod;18     return r;   19 }20 void find(int num,int v)21 {22     if(v>n)23     {24         ll c=1,cnt=0;25         for(int i=1;i<=num;i++) c=c*fac[f[i]-1]*((f[i]&1)?1:-1)%mod;26         for(int i=1;i<=num;i++) if(f[i]&1) cnt++; else c=c*w[1]%mod;27         up(ans,c*g[cnt]);   28         return;29     }30     for(int i=1;i<=num+1;i++) f[i]++,find(max(num,i),v+1),f[i]--;31 }32 int main()33 {34     scanf("%d%d%s",&n,&K,s+1);35     m=strlen(s+1);36     for(int i=0;i
        
         >1);k++)59                     up(g[j],C[j][k<<1]*pw[i+1][k<<1]%mod*p2[m-i][j-(k<<1)-1]);60     find(0,1);61     printf("%lld",(ans+mod)*ksm(fac[n],mod-2)%mod);62     return 0;63 }