实名(大雾)反对楼上的题解。楼上的代码 i=0 的时候循环就会跑到O(n^2)的复杂度，并不是O(n*W^2)，只是常数小一点而已。

这题可以做到O(nlogn)的复杂度。
题目本质是一个多重背包，
用重量为2^0,2^1,2^2...的物品拼出总重n，并且每个物品最多k个
设f[i][j]为前i个物品拼出重量j的方案数即可
楼下的写法是直接暴力转移这个背包，复杂度非常爆炸，题面数据范围小所以跑过去了。

然后考虑优化，设p[i]为第i个物品的重量,显然 p[i]=1<<(i-1)
注意到转移方程 f[i][j]=sum{f[i-1][j-p[i]*x]} 其中 0<=x<=k ,且 j-p[i]*x>=0
我们开一个数组Sum[i][j]记录 Sum[i][j]=sum{f[i][x]} 其中 x%p[i]==j
那么可以发现f[i][j]的转移变成了Sum[][]的前缀和

因为f[i][j]中i是O(logn)的,j是O(n)经过上面的优化O(1)转移 所以总复杂度O(nlogn)
下面是比较容易看的代码，注意f[i][j]和sum[i][j]是同时转移的
```c++
#include <cstdio>
#include <cstring>
#define N 10050
#define mo 1000000009
#define Min(a,b) (a<b?a:b)
typedef long long ll;
int f[15][N];
int sum[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int k,n;scanf("%d%d",&k,&n);
memset(f,0,sizeof(f));
f[0][0]=1;
int s=0;
for(int i=1;i<=n;i*=2)
{
s++;
int lim=Min(k*i+i,n/i*i+i);
for(int j=0;j<=i;j++)
sum[j]=0;
for(int j=0;j<=n;j++)
{
sum[j%i]+=f[s-1][j];
if(j>=lim) sum[j%i]-=f[s-1][j-lim];
sum[j%i]=((ll)sum[j%i]+mo)%mo;
f[s][j]=sum[j%i];
}
}
printf("%d\n",f[s][n]);
}
}

下面是丧心病狂的常数优化后的代码 应该可以应对百万级的数据范围
```c++
#include <cstdio>
#define N 10050
#define mo 1000000009
#define Min(a,b) (a<b?a:b)
typedef long long ll;
int f[2][N];
int sum[N];
void update(int x,int w,int lim,int n)
{
    for(int i=0;i<=w;i++)
        sum[i]=0;
    for(int i=0,j;i<=n;i++)
    {
        j=i&w;
        sum[j]+=f[x^1][i];
        if(i>=lim) sum[j]-=f[x^1][i-lim];
        if(sum[j]>=mo) sum[j]-=mo;
        else if(sum[j]<0) sum[j]+=mo;
        f[x][i]=sum[j];
    }
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int k,n;scanf("%d%d",&k,&n);
        int x=0;f[x][0]=1;
        for(int i=1;i<=n;i++)
            f[x][i]=0;
        for(int i=1;i<=n;i<<=1)
            update(x^=1,i-1,Min(k*i+i,n/i*i+i),n);
        printf("%d\n",f[x][n]);
    }
}

#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

const int N=10001;
const int W=14;
const int K=100001;
const int LM=1000000009;

int t,c,n;
long long f[W+1][N];

int main(void)
{
scanf("%d",&t);
for (;t--;)
{
scanf("%d%d",&c,&n);
memset(f,0,sizeof f);
for (int i=0;i<=c;i++) if (i>n) break; else f[0][i]=1;
for (int i=0;i<W;i++) for (int j=0;j<=n;j++) for (int k=0;k<=c;k++)
if (j+k*(1<<i+1)>n) break;
else f[i+1][j+k*(1<<i+1)]=(f[i+1][j+k*(1<<i+1)]+f[i][j])%LM;
printf("%lld\n",f[W-1][n]);
}
return 0;
}

http://shadowchaser.lofter.com/post/1d04e306_5e01c44