一道装呀（状压）DP

generator

题目描述:

 

 

　　自己的数学太差了，居然没看出来和这两个是相同的；

　　啊啊啊；

　　所以装呀一下就好了；

#include<iostream>
#include<cstdio>
typedef long long LL;
const LL maxsz=(1<<16)+5,maxn=21,kcz=1000000000+7,zss=1000000000+5;
LL a[maxn],f[maxsz],sum[maxsz],i,j,k,t,m,n,p,ans,num,x,y,ce;
LL ksm(LL ds,LL zs)
{
    LL temp = ds,res = 1;
    while (zs)
    {
        if (zs & 1) res = res * temp % kcz;
        temp = temp * temp % kcz;
        zs >>= 1;
    }
    return res;
}
LL chu(LL p,LL q)
{
    return p * ksm(q , zss) % kcz;
}
int main()
{
    scanf("%lld%lld",&n,&k);
    if (k==n) 
    {
        printf("1");
        return 0;
    }
    for(i=0;i<n;i++)
        scanf("%lld",&a[i]);
    f[0] = 1;
    sum[0] = 1000;
    for(i=1;i<(1<<n);i++)
    {
        num = 0;
        for(j=0;j<n;j++)
        if((1 << j) & i)
        {
            num++;
            ce=i - (1 << j);
            sum[i] = sum[ce] - a[j];
            if (!(ce & 1)) 
                f[i] = (f[i] + f[ce] * chu(a[j] , sum[ce]) % kcz) % kcz;
        }
        if ((i & 1) && (num <= k)) ans = (ans + f[i]) % kcz;
    }
    printf("%lld",ans);
}