[模拟赛]拆分（div）

前言：

之前考过，现在被拿来作为DIV2的T3，给学第、学妹们考。回忆的时候对状态的设计没有太清晰还是写一下吧。

题面描述：

给定一个数 \(n\)，你需要输出将 \(n\) 拆分成若干可重无序的二的次幂的方案数。答案对 \(10^9+7\) 取模。

解题思路：

首先有一个结论，那就是如果 \(n\) 为 \(2^i\)，那么分成大于等于两份的话，对拆分出来的的数排序后一定存在一个前缀和为 \(2^{i-1}\)。

因为小于 \(2^i\) 的最大的 \(2\) 的整数次幂只有 \(2^{i-1}\)，所以如果拆出 \(2^{i-1}\) 那么一定会有一个前缀和为 \(2^{i-1}\)，如果不拆，那么只能拆更小的数，肯定能组成 \(2^{i-1}\)。

所以设计状态，\(f_{i,j}\) 表示用 \(\le 2^{j}\) 的数组成 \(2^i\) 的方案数。

根据上面所说的结论，可以知道排完序后，存在一个前半部分和为 \(2^{i-1}\)，后半部分和为 \(2^{i-1}\)。

考虑 \(f_{i,j}\) 的值，转移枚举 \(k \le j\) 表示前半部分所用的数 \(\le 2^{k}\) 组成 \(2^{i-1}\) 的方案数，后半部分用区间 \([2^k, 2^j]\) 的数字组成 \(2^{i-1}\) 的方案数。\(f_{i,j}\) 为两部分的乘积。

前半部分是简单的，后半部分可以将所有数字 \(\div 2{k}\) 这样后半部分就变为了使用区间 \([1,2^{j-k}]\) 的数组成和为 \(2^{i-1-k}\) 的方案数了。即：

\[f_{i,j} \longleftarrow \sum _{k=0}^{j} f_{i-1,k} \times f_{i-1-k,j-k} \]

那么现在我们会做 \(n\) 是 \(2\) 的整数次幂的情况了，考虑不是 \(2\) 的次幂的情况。

还有个结论，那就是一个数 \(n\) 拆分完后排序，一定存在一个前缀和为 \(lowbit(n)\)。

考虑扩大范围，即排序后，一定存在一种划分方案，使得每段为 \(2^{a_{i}}\)，\(a_{i}\) 为 \(n\) 从低到高考虑第 \(i\) 个二进制为 \(1\) 的位置。

那么设计状态 \(g_{i,j}\) 表示用 \(\le 2^{j}\) 的数字拼出了最低的 \(i\) 个 \(2\) 进制为 \(1\) 的位置的方案数。

推的方法同理。

\[g_{i,j} \longleftarrow \sum _{k=0}^{j} g_{i-1,k} \times f_{a_{i}-k,j-k} \]

时间复杂度: \(O(\log^3 n)\)。

代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 70, mod = 1e9 + 7;
int n, m, tot, cnt, f[N][N], g[N][N], a[N];
void add(int &x, int y){x = (x + y) % mod;}
void solve(){cin >> n, cnt = tot = 0, m = log2(n);while(n){if(n & 1) a[++tot] = cnt;++cnt;n >>= 1;}for(int i = 0; i <= m + 1; i++)for(int j = 0; j <= m + 1; j++) f[i][j] = g[i][j] = 0;f[0][0] = 1;for(int i = 1; i <= m; i++){f[i][i] = 1;for(int j = 0; j <= i; j++){for(int k = 0; k <= j; k++)add(f[i][j], f[i - 1][k] * f[i - 1 - k][j - k] % mod);}}g[0][0] = 1;for(int i = 1; i <= tot; i++){for(int j = 0; j <= a[i]; j++){for(int k = 0; k <= j; k++){add(g[i][j], g[i - 1][k] * f[a[i] - k][j - k] % mod);}}}int ans = 0;for(int i = 0; i <= m; i++) add(ans, g[tot][i]);cout << ans << endl;
}
signed main(){freopen("div.in", "r", stdin);freopen("div.out", "w", stdout);int T;cin >> T;while(T--) solve();return 0;
}