【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个再用组合数计算方案转移

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N      31000

 #define M      40

 #define MOD 1000000007

 #define eps 1e-8

 #define pi     acos(-1)

 #define oo     1100000000

 ll dp[N][M],fac[N],inv[N],exf[N];

 int cnt[N],a[N],n,sta;

 void add(ll &x,ll y)

 {

     x+=y;

     if(x<) x+=MOD;

     if(x>=MOD) x-=MOD;

 }

 ll c(int x,int y)

 {

     return fac[x]*exf[y]%MOD*exf[x-y]%MOD;

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 int calc()

 {

     memset(dp,,sizeof(dp));

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

      if(cnt[i^sta]&) dp[][i]=MOD-;    //容斥系数

       else dp[][i]=;

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

      for(int j=;j<=sta;j++)

      {

          add(dp[i][j],dp[i-][j]*cnt[j]%MOD);

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

           if(!((j>>k)&)&&a[k]<i) add(dp[i][j|(<<k)],dp[i--a[k]][j]*c(i-,a[k])%MOD);    //当前数字取a[k]+1个

      }

      return dp[n][sta];

 }

 int main()

 {

     //freopen("hdoj5519.in","r",stdin);

     //freopen("hdoj5519.out","w",stdout);

      int cas;

      scanf("%d",&cas);

      fac[]=;

      for(int i=;i<N;i++) fac[i]=fac[i-]*i%MOD;

     inv[]=inv[]=exf[]=exf[]=;

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

     {

          inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;

          exf[i]=exf[i-]*inv[i]%MOD;

     }

     cnt[]=;

     for(int i=;i<N;i++) cnt[i]=cnt[i-lowbit(i)]+;

      for(int v=;v<=cas;v++)

      {

          scanf("%d",&n);

          for(int i=;i<=;i++) scanf("%d",&a[i]);

          sta=(<<)-;

          ll ans=calc();

          if(a[])

          {

              n--; a[]--;

              ans=(ans-calc()+MOD)%MOD;

          }

         printf("Case #%d: %I64d\n",v,ans);

     }

     return ;

 }