时间限制:24000ms
单点时限:3000ms
内存限制:256MB
描述
给定 n 和 k。计算有多少长度为 k 的数组 a1, a2, ..., ak，(0≤ai) 满足：
a1 + a2 + ... + ak = n。
对于任意的 i = 0, ..., k - 1 有 ai AND ai + 1 = ai + 1。其中AND是与操作。
输入
第一行包含一个整数 T - 测试数据组数（1 ≤ T ≤ 2）。接下来的 T 行，每行包含两个整数 k 和 n (k ≤ 105, n ≤ 104)。
输出
对于每组测试数据，输出一行表示对应的答案。答案可能很大，输出模 1000000009 后的结果。
样例输入
-
2 3 2 4 2
样例输出
-
2 2
- 后一位数如果含有1<<i，则前一位也含有1<<i；即1<<i从第a[x]延续到最后a[k]。转化一下，其实就是求一个柱形图， 使得它的面积和为n。其中，每条柱子的宽分别是1<<0,1<<1....1<<14，每条柱子的高最多是min(k,n/(1<<i))，高度表示a[x]到a[k]这些数的个数。
- 注意初始化
DP代码：
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int Mod=1000000009; int k,n,dp[10010][20]; int main() { int T,i,j,p,ans; scanf("%d",&T); while(T--){ scanf("%d%d",&k,&n); memset(dp,0,sizeof(dp)); for(i=0;i<=14;i++) dp[0][i]=1; for(i=0;i<=min(n,k);i++) dp[i][0]=1; //初始化
for(i=1;i<=14;i++) for(j=1;j<=n;j++) for(p=0;p<=min(k,j/(1<<i));p++){ dp[j][i]=(dp[j][i]+dp[j-p*(1<<i)][i-1])%Mod; } printf("%d ",dp[n][14]); } return 0; }
附上暴力的搜索，这样就能理解了。（当然，暴力是超时的）
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; const int Mod=1000000009; int k,n; int dfs(int pos,int sum) { if(pos==15){ if(sum==n) return 1; return 0; }int tmp=0; for(int i=0;i<=min(k,(n-sum)/(1<<pos));i++){ tmp=(tmp+dfs(pos+1,sum+i*(1<<pos)))%Mod; }return tmp; } int main() { int T,i,j,ans; scanf("%d",&T); while(T--){ scanf("%d%d",&k,&n); ans=dfs(0,0); printf("%d ",ans); } return 0; }