简述

　　标签里 fft 是什么鬼.. 　　 f[i][j] 表示如果每次都划分左上角能划分 i 次的正方形，给j次划分机会的方案数。 　　如果直接枚举四个正方形分配多少次划分机会的话，枚举的复杂度就是组合数级别的。 　　考虑分治，我从中间一劈为二，左边分配 k 次划分，右边分批j−k−1次划分，乘起来求个和就是答案。 　　那么问题转成怎样求两个一样大的正方形总共 j 次划分的方案数，那就再次枚举左边划分多少次，右边划分多少次，乘起来求个和就是答案。 　　这样预处理的复杂度是O(k2logn)。 　　那么对于一次询问，怎样求答案？ 　　假设输入的是 n 和k，显然只有当 n 是奇数的时候才能够进行一次划分，那划分的层数就取决于你不断整除二多少次除成1或者偶数。其实就是看二进制末尾不包含最高位有多少个 1 。 　　求出来之后直接将对应的f输出就行了。

代码

//dp #include <cstdio> #include <algorithm> #define mod 7340033 #define ll long long using namespace std; ll f[31][1005], g[31][1005]; void init() { int i, j, k; for(i=0;i<=30;i++)f[i][0]=g[i][0]=1; for(i=1;i<=30;i++) { for(j=1;j<=1000;j++) { for(k=0;k<=j-1;k++)f[i][j]+=(ll)g[i-1][k]*g[i-1][j-k-1]; for(k=0;k<=j;k++)g[i][j]+=(ll)f[i][k]*f[i][j-k]; f[i][j]%=mod, g[i][j]%=mod; } } } int main() { init(); int T, n, k, t; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(t=0;n&1 and n^1;n>>=1)t++; printf("%d\n",f[t][k]); } return 0; }