思路:
我们来看一下第i个数字 & 第i + 1 个数字 = 第i个数字有什么可探究的性质。
显然:第i个数字数字第bit位上是1,说明i + 1往后的所有数第bit位上也是1,
而第bit位为1代表着2的某个次幂。
更一般的,原题等价于将m拆分成若干个2的次幂的和,其中同种类的2次幂的个数≤n,求划分数。
由于数据范围为5e6
而2^23 > 5e6
因此,我们可以将问题转化成,用上限为n的前23个2的幂次,组成m的方案数
则这就是一个多重背包求方案数的模板。
代码如下:
#include <bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9 + 7; ll dp[5000010]; ll sz[24] = {0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304}; ll n, m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; //多重背包有上限求方案数的模板 dp[0] = 1; for (int i = 1 ; i <= 23 ; i++) { for (int j = sz[i] ; j <= m ; j++) { dp[j] = (dp[j] + dp[j - sz[i]]) % mod; } for (int j = m ; j >= (n + 1) * sz[i] ; j--) { dp[j] = (dp[j] - dp[j - (n + 1) * sz[i]] + mod) % mod; } } cout << dp[m] << "\n"; return 0; }