网站运营方案策划技巧-大眼的网站运营知识分享博客

网站运营

网站运营技巧策划方案分享
网站运营知识分享

bzoj3209: 花神的网站运营技巧数论题(数位DP)

bzoj3209: 花神的数论题(数位DP) 题目:

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
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

首页   建站经验   网站运营策划   网站运营方案   网站运营技巧   关于本站   地图