经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
BZOJ4513: [Sdoi2016]储能表(数位dp)
来源:cnblogs  作者:自为风月马前卒  时间:2018/12/7 9:33:30  对本文有异议

题意

题目链接

Sol

一点思路都没有,只会暴力,没想到标算是数位dp??Orz

首先答案可以分成两部分来统计

\[ f_{i,j}= \begin{aligned} i\oplus j &\left( i\oplus j >k\right) \\ 0 &\left( i\oplus j <=k\right) \end{aligned} \]

那么我们要求的就是

\[\sum_{i=0}^{n - 1} \sum_{j = 0}^{m - 1} f(i, j) - k * \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} [f(i, j)]\]

也就是说,我们要统计出满足条件的数的异或和以及满足条件的数的对数

考虑直接在二进制下数位dp,注意这里我们要记三维状态

\(f[len][0/1][0/1][0/1]\)表示此时到第\(len\)位,是否顶着\(n\)的上界,是否顶着\(m\)的上界,是否顶着\(k\)的下界

然后直接dp就可以了

  1. // luogu-judger-enable-o2
  2. #include<bits/stdc++.h>
  3. #define Pair pair<LL, LL>
  4. #define MP make_pair
  5. #define fi first
  6. #define se second
  7. #define LL long long
  8. #define int long long
  9. using namespace std;
  10. const int MAXN = 233;
  11. inline LL read() {
  12. char c = getchar(); int x = 0, f = 1;
  13. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  14. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  15. return x * f;
  16. }
  17. LL N, M, K, mod, Lim, vis[MAXN][2][2][2];
  18. Pair f[MAXN][2][2][2];
  19. void add2(LL &x, LL y) {
  20. if(x + y < 0) x = (x + y + mod);
  21. else x = (x + y >= mod ? x + y - mod : x + y);
  22. }
  23. LL add(LL x, LL y) {
  24. if(x + y < 0) return x + y + mod;
  25. return x + y >= mod ? x + y - mod : x + y;
  26. }
  27. LL mul(LL x, LL y) {
  28. return 1ll * x % mod * y % mod;
  29. }
  30. int Get(LL x) {
  31. int len = 0; while(x) x >>= 1, len++; return len;
  32. }
  33. Pair dfs(int now, int f1, int f2, int f3) {
  34. if(now > Lim) return MP(0, 1);
  35. if(vis[now][f1][f2][f3]) return f[now][f1][f2][f3];
  36. vis[now][f1][f2][f3] = 1;
  37. Pair ans = MP(0, 0);
  38. int L1 = (N >> Lim - now) & 1, L2 = (M >> Lim - now) & 1, L3 = (K >> Lim - now) & 1;
  39. //cout << (f1 &&(!L1)) << endl;
  40. for(int i = 0; i <= (f1 ? L1 : 1); i++) {
  41. for(int j = 0; j <= (f2 ? L2 : 1); j++) {
  42. if(f3 && ((i ^ j) < L3)) continue;
  43. Pair nxt = dfs(now + 1, f1 && (i == L1), f2 && (j == L2), f3 && ((i ^ j) == L3));
  44. add2(ans.se, nxt.se);
  45. add2(ans.fi, add(nxt.fi, mul(nxt.se, mul((i ^ j), (1ll << Lim - now)))));
  46. }
  47. }
  48. return f[now][f1][f2][f3] = ans;
  49. }
  50. int solve() {
  51. memset(vis, 0, sizeof(vis));
  52. memset(f, 0, sizeof(f));
  53. Lim = 0;
  54. N = read(); M = read(); K = read(); mod = read(); N--; M--;
  55. Lim = max(Get(N), max(Get(K), Get(M)));
  56. Pair ans = dfs(1, 1, 1, 1);
  57. return add(ans.fi, -mul(K, ans.se));
  58. }
  59. signed main() {
  60. for(int T = read(); T; T--, printf("%lld\n", solve()));
  61. return 0;
  62. }
  63. /*
  64. 5000
  65. 504363800392059286 554192717354508770 21453916680846604 401134357
  66. */
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号