这是一道恶评题((CF)上(2300),洛谷上是一道紫题)
这题其实并不难(当然用(FFT)的当我没说)
（〇）前置知识
1.动态规划
2.FFT
（一）解题思路
这个(DP)应该是很容易看出来的。
题目有(k)次操作，每次操作可以将(1)个正方形划分成(4)个正方形，给出一个(n imes n)的正方形，问有多少种不同的划分方案。
需要注意的是，每次操作会占用正方形最中间的一行和最中间的一列，且每次必须要将一个大正方形划分为四个小正方形(即划分方案中不能存在非正方形)。
初看题目，很容易想到(DP)。(DP)的状态也很容易表示，设(f(n,k))表示将一个大小为(n)的正方形划分(k)次的方案数。
状态转移方程很显然。即
于是我们很开心地看了一眼数据范围:(1leq nleq10^9,0leq kleq 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)时，按照题目要求我们同样不考虑)。
显然(cntleq 29)
再解决时间复杂度的问题。
观察状态转移方程，我们发现其实(k^4)的枚举做了很多无用功，很多(i+j+x+y ot= x)的情况都被枚举了。下面是(FFT)惯用伎俩。
考虑将状态转移方程拆分。变为
(sumlimits_{i+j=l}f(dfrac{n-1}{2},i) imes f(dfrac{n-1}{2},j))和(sumlimits_{x+y=z}f(dfrac{n-1}{2},x) imes f(dfrac{n-1}{2},y))
其中(l+z=k-1)。感觉到了卷积吗？
最终的答案其实就是上述两个多项式相乘(这个不用解释吧)
设(g(x,y)=sumlimits_{i+j=y}f(x,i) imes f(x,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
", f[cnt][k]);
}
return 0;
}