这是一道恶评题(\(CF\)上\(2300\),洛谷上是一道紫题)
这题其实并不难(当然用\(FFT\)的当我没说)
（〇）前置知识
1.动态规划
2.FFT
（一）解题思路
这个\(DP\)应该是很容易看出来的。
题目有\(k\)次操作，每次操作可以将\(1\)个正方形划分成\(4\)个正方形，给出一个\(n\times n\)的正方形，问有多少种不同的划分方案。
需要注意的是，每次操作会占用正方形最中间的一行和最中间的一列，且每次必须要将一个大正方形划分为四个小正方形(即划分方案中不能存在非正方形)。
初看题目，很容易想到\(DP\)。\(DP\)的状态也很容易表示，设\(f(n,k)\)表示将一个大小为\(n\)的正方形划分\(k\)次的方案数。
状态转移方程很显然。即
\[f(n,k)=\sum\limits_{i+j+x+y=k-1}f(\dfrac{n-1}{2},i)\times f(\dfrac{n-1}{2},j)\times f(\dfrac{n-1}{2},x)\times f(\dfrac{n-1}{2},y) \]
于是我们很开心地看了一眼数据范围:\(1\leq n\leq10^9,0\leq k\leq 1000\)GG
空间和时间都爆了。
首先我们来解决空间问题。不难发现(假设\(n\)很大)，我们需要用到的只有\(f(n,k)\)和\(f(\dfrac{n-1}{2},k)\)中间\(n-1\)到\(\dfrac{n-1}{2}+1\)的空间其实都浪费了。
而且，由于每次必须切成四个正方形，所以当\(n\%2=0\)时，是无法划分出正方形的。换句话说，当二进制下\(n\)的末尾为\(0\)时，\(ans=0\)，后面\(\dfrac{n-1}{2}\)
的情况我们也不需要考虑了。
由此，我们需要的空间大大减小了，只需要关注\(\dfrac{n-1}{2}\)和二进制下\(n\)的末尾不为\(0\)的情况。
用一个\(cnt\)记录\(n\)满足以上条件的\(n\)的数量。那么\(cnt\)实质上就等于二进制下\(n\)的末尾连续\(1\)的个数(当然当\(n=1\)时，按照题目要求我们同样不考虑)。
显然\(cnt\leq 29\)
再解决时间复杂度的问题。
观察状态转移方程，我们发现其实\(k^4\)的枚举做了很多无用功，很多\(i+j+x+y\not= x\)的情况都被枚举了。下面是\(FFT\)惯用伎俩。
考虑将状态转移方程拆分。变为
\(\sum\limits_{i+j=l}f(\dfrac{n-1}{2},i)\times f(\dfrac{n-1}{2},j)\)和\(\sum\limits_{x+y=z}f(\dfrac{n-1}{2},x)\times f(\dfrac{n-1}{2},y)\)
其中\(l+z=k-1\)。感觉到了卷积吗？
最终的答案其实就是上述两个多项式相乘(这个不用解释吧)
设\(g(x,y)=\sum\limits_{i+j=y}f(x,i)\times f(x,j)\)
那么原状态转移方程就变为:
\[f(n,k)=\sum\limits_{i+j=k-1}g(\dfrac{x-1}{2},i)\times g(\dfrac{x-1}{2},j) \]
显然上述两个式子都能用\(FFT\)快速求出来。然而数据范围告诉我们不用\(FFT\)。所以我才不用FFT呢，谁用谁***。当然数据范围扩大就必须用了。建议扩大数据范围
（二）代码实现
我知道你们一定最喜欢看这个。
由于我比较懒，所以变量全用了long long。反正能过
#include<bits/stdc++.h>
using namespace std;
const long long maxk = 1005, mod = 7340033;
long long f[40][maxk], g[40][maxk];
int main(){
for(long long i=0; i<=30; i++) f[i][0] = g[i][0] = 1;
for(long long i=1; i<=30; i++){
for(long long j=1; j<=1000; j++){
for(long long k=0; k<j; k++){
f[i][j] = (f[i][j] + g[i-1][k]*g[i-1][j-k-1]%mod)%mod;
}
for(long long k=0; k<=j; k++){
g[i][j] = (g[i][j] + f[i][k]*f[i][j-k]%mod)%mod;
}
}
}
long long T;
scanf("%lld", &T);
while(T--){
long long n, k, cnt = 0;
scanf("%lld%lld", &n, &k);
while(n > 1){
if(n&1) cnt ++, n >>= 1;
else break;
}
printf("%lld\n", f[cnt][k]);
}
return 0;
}