题目：
3209: 花神的数论题
解析：
二进制的数位DP 因为\([1,n]\)中每一个数对应的二进制数是唯一的，我们枚举\(1\)的个数\(k\)，计算有多少个数的二进制中有\(k\)个\(1\) 设\(n\)的二进制一共有\(num\)位，有\(sum[i]\)个数的二进制中有\(k\)个\(1\)， 答案就是\(\prod_{i=1}^{num}i^{sum[i]}\)
用数位DP搞一下就好了 设\(f[i][j]\)表示到第\(i\)位有\(j\)个\(1\)时有多少个数 枚举\(k\)，记搜一下。
由于可能会有很多数的二进制中有\(k\)个\(1\)，所以用快速幂维护一下
相似思路的题还有1799: [Ahoi2009]self 同类分布
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 60;
const int mod = 10000007;
int n, m, num;
int digit[N], f[N][N];
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans % mod;
}
int dfs(int pos, int sum, int cnt, int limit) {
if (pos == -1) return sum == cnt;
if (cnt > sum) return 0;
if (!limit && ~f[pos][cnt]) return f[pos][cnt];
int up = limit ? digit[pos] : 1;
int ans = 0;
for (int i = 0; i <= up; ++i)
ans = ans + dfs(pos - 1, sum, cnt + i, limit && i == up);
if (!limit) f[pos][cnt] = ans;
return ans;
}
int divide(int x) {
int num = 0, ans = 1;
for ( ; x; x /= 2) digit[num++] = x % 2;
for (int i = 1; i <= num; ++i) {
memset(f, -1, sizeof f);
ans = (ans * qpow(i, dfs(num - 1, i, 0, 1))) % mod;
}
return ans % mod;
}
signed main() {
cin >> n;
cout << divide(n);
}
转载于:https://www.cnblogs.com/lykkk/p/11358494.html
相关资源：JAVA上百实例源码以及开源项目
