转换一下变成 a 层的完全四叉树, 占领 k 个点有多少种方案, 点能被占当且仅当它的父亲被占。
a <= 30, 所以我们把每层都dp出来, dp[ i ][ j ] 表示 i 层完全四叉树占领 k 个点的方案数。
#include<bits/stdc++.h> #define LL long long #define LD long double #define ull unsigned long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ALL(x) (x).begin(), (x).end() #define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int N = 5000 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 7340033; const double eps = 1e-8; const double PI = acos(-1); template<class T, class S> inline void add(T &a, S b) {a += b; if(a >= mod) a -= mod;} template<class T, class S> inline void sub(T &a, S b) {a -= b; if(a < 0) a += mod;} template<class T, class S> inline bool chkmax(T &a, S b) {return a < b ? a = b, true : false;} template<class T, class S> inline bool chkmin(T &a, S b) {return a > b ? a = b, true : false;} int dp[31][1007]; int q, n, k; int main() { dp[0][0] = 1; for(int o = 1; o < 31; o++) { dp[o][0] = 1; dp[o][1] = 1; for(int c = 0; c < 4; c++) { for(int i = 1000; i >= 1; i--) { for(int j = 1; i + j <= 1000; j++) { add(dp[o][i + j], 1LL * dp[o][i] * dp[o - 1][j] % mod); } } } } scanf("%d", &q); while(q--) { scanf("%d%d", &n, &k); int c = 0; while((n & 1) && n != 1) { c++; n--; n >>= 1; } printf("%d\n", dp[c][k]); } return 0; } /* */