直接背包不可做
我们只需要知道每个数位上有多少个$1$，那么我们就能构造出解
因此，我们对每一位讨论，
可以拆出$n + \frac{n}{2} + \frac{n}{4} + ... = 2n$个物品，然后去做背包
加上足够的剪枝就可以过了...
复杂度$O(Tn^2)$
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
namespace remoon {
#define re register
#define de double
#define le long double
#define ri register int
#define ll long long
#define sh short
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define tpr template <typename ra>
#define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++)
#define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --)
#define gc getchar
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc(); return p * w;
}
int wr[], rw;
#define pc(iw) putchar(iw)
tpr inline void write(ra o, char c = '\n') {
if(!o) pc('');
if(o < ) o = -o, pc('-');
while(o) wr[++ rw] = o % , o /= ;
while(rw) pc(wr[rw --] + '');
pc(c);
}
tpr inline void cmin(ra &a, ra b) { if(a > b) a = b; }
tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; }
tpr inline bool ckmin(ra &a, ra b) { return (a > b) ? a = b, : ; }
tpr inline bool ckmax(ra &a, ra b) { return (a < b) ? a = b, : ; }
}
using namespace std;
using namespace remoon; #define sid 200050
#define mod 1000000009 inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; }
inline int Inc(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; } int n, k;
int f[sid], g[sid][]; inline void Solve() {
int flag;
memset(g, , sizeof(g));
k = read(); n = read();
int now = , pre = ; g[now][] = ;
rep(i, , ) {
now ^= ; pre ^= ; flag = ;
memset(f, , sizeof(f));
rep(j, , k) {
if(( << i) * j > n) break;
f[( << i) * j] = ; flag = ;
}
if(flag == ) { flag = i - ; break; }
rep(j, , n) g[j][now] = ;
rep(j, , n) if(f[j])
rep(p, , n) {
if(j + p > n) break;
inc(g[j + p][now], g[p][pre]);
}
}
write(g[n][now]);
} int main() {
int Tt = read();
while(Tt --) Solve();
return ;
}