P4317 花神的数论题
大意
求 \(\prod_{i = 1} ^ k \text{pop_count(i)}\) 的答案。
\(k \le 10 ^ 15\)
思路
由于此题的 \(k\) 较大，且与二进制有关，我们求的又是 \(1 \sim k\) 的答案，我们不妨想想数位 DP 的实现方式。
很显然的地方就是我们可以把 \(k\) 二进制拆分，拆成 01 串，然后我们要统计所有在二进制下的 01 串中，其十进制表示 \(\le k\) 的，然后把这些合法串的 1 的个数相乘。
那么我们知道，第一要保证的是大小 \(\le k\)，第二是保证记录 \(1\) 的个数。所以数位 DP 的思路就出来了，我们定义 \(f[pos][sum][lim]\) 表示在第 \(pos\) 位，前面的 \(1\) 的个数为 \(sum\)，后面在是否满足限制 \(lim\) 的前提下后面可能形成的 \(1\) 的个数的乘积。
所以就直接做数位的 DP 即可。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int MOD = 10000007;
#define ll long long
const int MAXN = 50;
int len = 0, a[MAXN];
ll k;
ll f[MAXN][200][2];ll dp(int pos, int sum, bool lim){if(pos == len){return max(sum, 1) % MOD;}if(~f[pos][sum][lim]){return f[pos][sum][lim] % MOD;}ll ans = 1;int maxx = lim ? a[pos] : 1;for(int i = 0;i <= maxx;i ++){ans = (ans * dp(pos + 1, sum + (i == 1), lim && (i == maxx))) % MOD;}return f[pos][sum][lim] = ans;
}ll solve(ll x){memset(f, -1, sizeof(f));len = 0;while(x){a[len ++] = x % 2;x /= 2;}reverse(a, a + len);return dp(0, 0, 1) % MOD;
}int main(){cin >> k;cout << solve(k) % MOD<< '\n';return 0;
}