Our happy ending
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 570 Accepted Submission(s): 183
Y*wan still remember the day he first meets the devil. Now everything is done and the devil is gone. Y*wan feel very sad and suicide.
You feel guilty after killing so many loli, so you suicide too.
Nobody survive in this silly story, but there is still some hope, because this is just a silly background story during one programming contest!
And the last problem is:
Given a sequence a_1,a_2,...,a_n, if we can take some of them(each a_i can only be used once), and they sum to k, then we say this sequence is a good sequence.
How many good sequence are there? Given that each a_i is an integer and 0<= a_i <= L.
You should output the result modulo 10^9+7.
For each test case, the first line contains 3 integers n, k, L.
T<=20, n,k<=20 , 0<=L<=10^9.
2 2 2
递推实现 f[i][j]表示前i个数能够表示j状态的方案数，其中j为最多20位的二进制，每一二进制位表示‘和’为该位置是否达到，比如第20位二进制位若为1，表示的就是前i个数和有达到20，这20位表示的就是一个状态。
从j状态向上推，若该位置取k，则 需要更新的状态为 j | j<<k | 1<<(k-1) 注意包括0位置
可以用一维数组实现滚动数组优化
复杂度理论上高达O(n^2*2^k)会超时，但是要注意到很大部分f[i][j]=0，加上这个优化瞬间快了10倍多
中间的递推过程从标程中照搬下来了，惭愧！
#include "cstdio"
#include "cstring"
#define min(x,y) (x>y?y:x) #define MOD 1000000007 int f[];
int n,k,l;
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
memset(f,,sizeof(f));
scanf("%d%d%d",&n,&k,&l);
int ms=(<<k)-;
long long ans=; for(int j=; j<=min(l,k); j++)
f[<<(j-)]=;
if(l>k) f[]=(f[]+l-k)%MOD; for(int i=; i<n; i++)
for(int s=ms; s>=; s--) //从大到小 避免重复计算
if(f[s]>) //没加这句20s+ 加了就1286ms
{
long long tmp=f[s]; //滚动数组压缩 发现滚动数组都不需要了 !
for(int j=; j<=min(l,k); j++) //f[i][s] 插入j=0的情况直接保存给 f[i+1][s]
{
int ns=(s|(s<<j)|(<<(j-)))&ms; //包括从0处向右推j位
f[ns]=(f[ns]+tmp)%MOD;
}
if(l>k)
f[s]=(f[s]+(l-k)*tmp%MOD)%MOD;
} for(int s=; s<=ms; s++)
if(s&(<<(k-)))
ans=(ans+f[s])%MOD; printf("%lld\n",ans);
}
return ;
}
之前看解题报告写的
开了二维数组，画蛇添足的加了个快速幂和组合 =.= 时间20s+
超时代码：
#include "cstdio"
#include "cstring"
#define min(x,y) (x>y?y:x)
#define MOD 1000000007
int f[][],c[][];
int n,k,l;
inline long long pow(long long a, long long b)
{
long long ret=,tmp=a%MOD;
while(b)
{
if(b&) ret=(ret*tmp)%MOD;
tmp=(tmp*tmp)%MOD;
b>>=;
}
return ret;
}
int main()
{
for(int i=; i<=; i++)
for(int j=; j<=i; j++)
if(j>) c[i][j]=c[i-][j]+c[i-][j-];
else c[i][j]=;
int tt;
scanf("%d",&tt);
while(tt--)
{
memset(f,,sizeof(f));
scanf("%d%d%d",&n,&k,&l);
int ms=(<<k)-;
for(int j=; j<=min(l,k); j++)
f[][<<(j-)]=;
for(int i=; i<n; i++)
for(int j=; j<=min(l,k); j++)
for(int s=; s<=ms; s++)
{
f[i+][(s|(s<<j)|(<<(j-)))&ms]+=f[i][s];
f[i+][(s|(s<<j)|(<<(j-)))&ms]%=MOD;
}
long long ans=;
if(l<=k)
{
for(int s=; s<=ms; s++)
if(s&(<<(k-)))
ans=(ans+f[n][s])%MOD;
}
else
{
for(int i=; i<=n; i++)
for(int s=; s<=ms; s++)
if(s&(<<(k-)))
ans=(ans+((long long)f[i][s]*(long long)c[n][i])%MOD*pow(l-k,n-i))%MOD;
}
printf("%lld\n",ans);
}
return ;
}