描述
给定 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
注意到ai AND ai + 1 = ai + 1可以理解为是后面的数包含了前一个所有的二进制位。
那么我们可以想象是将每个位分配给一个后缀，因为对于每一位，整个序列肯定是000011111111。
设f[len][k]表示后len位，和为k，DP即可。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int mod=1000000009; ll f[20][100010]; int main() { int T=read(); while(T--) { int n=read(),k=read(); memset(f,0,sizeof(f)); rep(i,0,min(k,n)) f[0][i]=1; rep(len,1,19) rep(i,0,k) { rep(j,0,n) if(i>=(1<<len)*j) (f[len][i]+=f[len-1][i-(1<<len)*j])%=mod; else break; } printf("%lld\n",f[19][k]); } return 0; }