【HDOJ5519】Kykneion asma（状压DP，容斥）

题意：给定n和a[i](i=0..4)，求所有n位5进制数中没有前导0且i出现的次数不超过a[i]的数的个数

2<=n<=15000，0<=a[i]<=3e4

思路：设f(n,a,b,c,d,e)为可以含前导0的答案

则ANS=f(n,a,b,c,d,e)-f(n-1,a-1,b,c,d,e)

考虑对每一种数字出现的情况进行容斥

设dp[i][j]为当前到第i位，数字出现的情况为j，至少有一种数字超过了限制次数的方案数

转移有两种：已经出现过的数字可以再出现一次，没有出现过的数字先强行取a[i]+1个再用组合数计算方案转移

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<string>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<map>
 8 #include<set>
 9 #include<queue>
10 #include<vector>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned int uint;
14 typedef unsigned long long ull;
15 typedef pair<int,int> PII;
16 typedef vector<int> VI;
17 #define fi first
18 #define se second 
19 #define MP make_pair
20 #define N      31000
21 #define M      40
22 #define MOD 1000000007
23 #define eps 1e-8 
24 #define pi     acos(-1)
25 #define oo     1100000000
26 
27 ll dp[N][M],fac[N],inv[N],exf[N]; 
28 int cnt[N],a[N],n,sta;
29 
30 void add(ll &x,ll y)
31 {
32     x+=y;
33     if(x<0) x+=MOD;
34     if(x>=MOD) x-=MOD;
35 }
36 
37 ll c(int x,int y)
38 {
39     return fac[x]*exf[y]%MOD*exf[x-y]%MOD;
40 }
41 
42 int lowbit(int x)
43 {
44     return x&(-x);
45 }
46 
47 int calc()
48 {
49     memset(dp,0,sizeof(dp));
50     for(int i=0;i<=sta;i++) 
51      if(cnt[i^sta]&1) dp[0][i]=MOD-1;    //容斥系数 
52       else dp[0][i]=1;
53     for(int i=1;i<=n;i++)
54      for(int j=0;j<=sta;j++)
55      {
56          add(dp[i][j],dp[i-1][j]*cnt[j]%MOD);
57          for(int k=0;k<=4;k++)
58           if(!((j>>k)&1)&&a[k]<i) add(dp[i][j|(1<<k)],dp[i-1-a[k]][j]*c(i-1,a[k])%MOD);    //当前数字取a[k]+1个
59      }
60      return dp[n][sta];
61 }
62         
63 int main()
64 { 
65     //freopen("hdoj5519.in","r",stdin);
66     //freopen("hdoj5519.out","w",stdout);
67      int cas;
68      scanf("%d",&cas);
69      fac[0]=1;
70      for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD; 
71     inv[0]=inv[1]=exf[0]=exf[1]=1;
72     for(int i=2;i<N;i++)
73     {
74          inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
75          exf[i]=exf[i-1]*inv[i]%MOD;
76     }    
77     cnt[0]=0;
78     for(int i=1;i<N;i++) cnt[i]=cnt[i-lowbit(i)]+1; 
79      for(int v=1;v<=cas;v++)
80      {
81          scanf("%d",&n);
82          for(int i=0;i<=4;i++) scanf("%d",&a[i]);
83          sta=(1<<5)-1; 
84          ll ans=calc();
85          if(a[0])
86          {
87              n--; a[0]--;
88              ans=(ans-calc()+MOD)%MOD;
89          }
90         printf("Case #%d: %I64d
",v,ans);
91     }
92     return 0;
93 }
94