Code666 (代码贴、代码片段)

[C] 2013腾讯马拉松初赛 ACM 吉哥系列故事——恨7不成妻 →→→→→进入此内容的聊天室

来自 , 2021-02-25, 写在 C, 查看 108 次.
URL http://www.code666.cn/view/add21793
  1. /*
  2.  
  3. 2013腾讯马拉松初赛第1场
  4.  
  5. 1003 吉哥系列故事——恨7不成妻
  6.  
  7. Time Limit: 0.5 Seconds   Memory Limit: 65536K
  8.  
  9. 单身!
  10. 依然单身！
  11. 吉哥依然单身！
  12. DS级码农吉哥依然单身！
  13. 所以，他生平最恨情人节，不管是214还是77，他都讨厌！
  14. 吉哥观察了214和77这两个数，发现：
  15. 2+1+4=7
  16. 7+7=7*2
  17. 77=7*11
  18. 最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！
  19. 什么样的数和7有关呢？
  20. 如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
  21. 1.整数中某一位是7；
  22. 2.整数的每一位加起来的和是7的整数倍；
  23. 3.这个整数是7的整数倍；
  24.  
  25. 现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
  26.  
  27. Input
  28. 输入数据的第一行是case数T(1 <= T <= 50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。
  29.  
  30. Output
  31. 请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。
  32.  
  33. Sample Input
  34. 3
  35. 1 9
  36. 10 11
  37. 17 17
  38.  
  39. Sample Output
  40. 236
  41. 221
  42. 0
  43.  
  44. */
  45.  
  46. /*
  47. 解题报告：
  48.  
  49. 这题的数据范围很大，如果直接模拟的话肯定超时，还有这题时限好像还是500MS的，故意搞不这样就是不让一般的暴力方法过这题。
  50.  
  51. 这题和以前不一样的地方在他要求的是平方和，而不是和。以前求和还是好做的。
  52.  
  53. 一般这种题目的话肯定是数位DP了。
  54. 第一种想法，上面有三个条件，我们可以先用上面的条件求出至少符合一个条件的数字平方和。这个要用一下容斥原理。比较麻烦。
  55.  
  56. 我是直接把7这一位数字去掉，然后再加两维状态保存当前数字对7取余的结果，和每一位之和对7取余的结果。
  57.  
  58. 下面说一下我的做法。
  59. dp[i][j][p][q]表示长度为i的以j为首位的数字每一位数字之和对7取余是p,整个数字对7取余是q的平方和。
  60.  
  61. 现问题的关键是如何通过dp[i-1][k][a][b]推出来dp[i][j][p][q]
  62.  
  63. 我们可以观察，假设dp[i-1][k][a][b]里面的数字是
  64. n1,n2,...n[T]     dp[i-1][k][a][b]这个状态下有T个数字是合法的
  65.  
  66. 那么dp[i][j][p][q]状态下的数字就是
  67. j*ten[i-1]+n1,j*ten[i-1]+n2，...j*ten[i-1]+n[T]
  68. ten[i]代表10的i次方
  69. 他们的平方和就是
  70. (j*ten[i-1]+n1)^2+(j*ten[i-1]+n2)^2+...+(j*ten[i-1]+n[T])^2
  71. 展开一下
  72. T*(j*ten[i-1])^2+2*j*ten[i-1]*(n1+n2+...+n[T])+n1^2+n2^2+n3^2+...+n[T]^2
  73.  
  74. 从上面的式子可以看出，要计算出平方和，还需要统计一下合法数字的个数，还有，这些合法数字的总和。
  75.  
  76. 所以我们要分三步DP。
  77. dp复杂度是O(20*10*10*7*7),对于50个数据还是可以接受的。
  78. 来自：chenwenwen0210 的百度空间
  79. */
  80.  
  81. #include<stdio.h>
  82. #include<time.h>
  83. #include<algorithm>
  84. #include<string.h>
  85. using namespace std;
  86. typedef __int64 lld;
  87. const int MAX = 510000;
  88. const int INF = 1000000000;
  89. const lld MOD = 1000000007;
  90.  
  91. lld dp[20][10][7][7] = {0};
  92. lld cnt[20][10][7][7] = {0};
  93. lld sum[20][10][7][7] = {0};
  94. lld multi[10][10];
  95. lld add[10][10];
  96. lld ten[20];
  97. lld tp[20];
  98. void init() {
  99.     lld i, j, p, q, k;
  100.     lld a, b;
  101.  
  102.     cnt[0][0][0][0] = 1;
  103.     //计算个数
  104.     for(i = 1; i < 20; i++) {
  105.         for(j = 0; j < 10; j++) {
  106.             if(j == 7)continue;
  107.             for(a = 0; a < 7; a++) {
  108.                 for(b = 0; b < 7; b++) {
  109.                     if(cnt[i - 1][j][a][b] == 0)continue;
  110.  
  111.                     for(k = 0; k < 10; k++) {
  112.                         if(k == 7)continue;
  113.                         p = add[k][a]; //加起来对7取余
  114.  
  115.                         q = multi[k][ten[i - 1]]; //乘起来对7取余
  116.                         q = add[q][b];
  117.  
  118.                         cnt[i][k][p][q] += cnt[i - 1][j][a][b];
  119.                         if(cnt[i][k][p][q] >= MOD)cnt[i][k][p][q] -= MOD;
  120.  
  121.                     }
  122.                 }
  123.             }
  124.         }
  125.     }
  126.  
  127.     //计算和
  128.     for(i = 1; i < 20; i++) {
  129.         for(j = 0; j < 10; j++) {
  130.             if(j == 7)continue;
  131.             for(a = 0; a < 7; a++) {
  132.                 for(b = 0; b < 7; b++) {
  133.  
  134.                     for(k = 0; k < 10; k++) {
  135.                         if(k == 7)continue;
  136.                         p = add[k][a];
  137.  
  138.                         q = multi[k][ten[i - 1]];
  139.                         q = add[q][b];
  140.                         lld z = k * tp[i - 1] % MOD;
  141.                         sum[i][k][p][q] += cnt[i - 1][j][a][b] * z + sum[i - 1][j][a][b];
  142.                         if(sum[i][k][p][q] >= MOD)sum[i][k][p][q] %= MOD;
  143.  
  144.                     }
  145.                 }
  146.             }
  147.         }
  148.     }
  149.  
  150.     //计算平方和
  151.     for(i = 1; i < 20; i++) {
  152.         for(j = 0; j < 10; j++) {
  153.             if(j == 7)continue;
  154.             for(a = 0; a < 7; a++) {
  155.                 for(b = 0; b < 7; b++) {
  156.  
  157.                     for(k = 0; k < 10; k++) {
  158.                         if(k == 7)continue;
  159.                         p = add[k][a];
  160.  
  161.                         q = multi[k][ten[i - 1]];
  162.                         q = add[q][b];
  163.                         lld z = k * tp[i - 1] % MOD;
  164.                         dp[i][k][p][q] += cnt[i - 1][j][a][b] * z % MOD * z + dp[i - 1][j][a][b] + 2 * z * sum[i - 1][j][a][b];
  165.                         if(dp[i][k][p][q] >= MOD)dp[i][k][p][q] %= MOD;
  166.  
  167.                     }
  168.                 }
  169.             }
  170.         }
  171.     }
  172.  
  173. }
  174. lld split(lld bit[], lld n) {
  175.     int i = 0;
  176.     for(i = 0; n; i++) {
  177.         bit[i] = n % 10;
  178.         n /= 10;
  179.     }
  180.     return i;
  181. }
  182. bool ok(lld n) {
  183.     if(n % 7 == 0)return false;
  184.     lld sum = 0;
  185.     while(n) {
  186.         if(n % 10 == 7)return false;
  187.         sum += n % 10;
  188.         n /= 10;
  189.     }
  190.     if(sum % 7 == 0)return false;
  191.     return true;
  192. }
  193. lld calc(lld n) {
  194.     if(n == 0)return 0;
  195.     lld bit[22], len;
  196.     lld ret = 0;
  197.     lld i, j, k, p, q, a, b;
  198.     len = split(bit, n);
  199.  
  200.     if(ok(n))ret += n % MOD * (n % MOD) % MOD;
  201.  
  202.     for(i = 1; i < len; i++) {
  203.         for(j = 1; j < 10; j++) {
  204.             if(j == 7)continue;
  205.             for(p = 1; p < 7; p++) {
  206.                 for(q = 1; q < 7; q++) {
  207.                     ret += dp[i][j][p][q];
  208.                     if(ret >= MOD)ret -= MOD;
  209.                 }
  210.             }
  211.         }
  212.     }
  213.  
  214.     lld presum = 0; //前面各位和对7取余
  215.     lld premod7 = 0; //前面组成数字对7取余
  216.     lld pre = 0; //前面组成数字对MOD取余
  217.     for(i = len; i >= 1; i--) {
  218.         j = 0;
  219.         if(i == len)j++;
  220.         for(; j < bit[i - 1]; j++) {
  221.             if(j == 7)continue;
  222.             for(k = 0; k < 10; k++) {
  223.                 if(k == 7)continue;
  224.                 for(a = 0; a < 7; a++) {
  225.                     for(b = 0; b < 7; b++) {
  226.                         p = add[presum][j];
  227.                         p = add[p][a];
  228.                         if(p == 0)continue;
  229.  
  230.                         q = multi[premod7][10 - 7];
  231.                         q = add[q][j];
  232.                         q = multi[q][ten[i - 1]];
  233.                         q = add[q][b];
  234.  
  235.                         if(q == 0)continue;
  236.                         lld z = (pre * 10 + j) * tp[i - 1] % MOD;
  237.                         ret += z * z % MOD * cnt[i - 1][k][a][b] + dp[i - 1][k][a][b] + 2 * z * sum[i - 1][k][a][b];
  238.                         ret %= MOD;
  239.                     }
  240.                 }
  241.             }
  242.         }
  243.  
  244.         if(bit[i - 1] == 7)break;
  245.  
  246.         pre = (pre * 10 + bit[i - 1]) % MOD;
  247.  
  248.         presum = add[presum][bit[i - 1]];
  249.  
  250.         premod7 = multi[premod7][10 - 7];
  251.         premod7 = add[premod7][bit[i - 1]];
  252.     }
  253.  
  254.     return ret;
  255. }
  256.  
  257. int main() {
  258.     lld n, m;
  259.     int i, j;
  260.  
  261.     int T = 0;
  262.     for(i = 0; i < 10; i++) {
  263.         for(j = 0; j < 10; j++) {
  264.             add[i][j] = (i + j) % 7;
  265.             multi[i][j] = i * j % 7;
  266.         }
  267.     }
  268.     ten[0] = 1;
  269.     tp[0] = 1;
  270.     for(i = 1; i < 20; i++) {
  271.         ten[i] = ten[i - 1] * 10 % 7;
  272.         tp[i] = tp[i - 1] * 10 % MOD;
  273.     }
  274.  
  275.     init();
  276.  
  277.     scanf("%d", &T);
  278.     while(T--) {
  279.         scanf("%I64d%I64d", &n, &m);
  280.  
  281.         lld ans = 0;
  282.         ans += calc(m);
  283.         ans -= calc(n - 1);
  284.         if(ans < 0)ans += MOD;
  285.         printf("%I64d\n", ans);
  286.     }
  287.     return 0;
  288. }
  289.  

回复 "2013腾讯马拉松初赛 ACM 吉哥系列故事——恨7不成妻"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666