[关闭]
@qq290637843 2021-05-09T11:42:19.000000Z 字数 23178 阅读 445

2019南昌

题目见https://www.jisuanke.com/contest/12755/challenges。

A、9102

先解决没有回溯要求的问题。由于要求能删点，所以并查集的写法要加一些虚点，让实点绝对不会成为父节点，而只有实点才会被删除，所以就保证了算法的正确性。
接着，先把操作离线，得到一个版本树，于是就是在这棵树上深度优先搜索，然后可持久化数组。因为该问题实际是用三个数组维护并查集，所以就是对该三数组的版本信息保存，存法就是数组中每个元素实际上是一个栈。本题空间要求比较死，所以用前向链表实现栈。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxm = 1e6;
  10. const ul maxn = 1e6;
  12. class node {
  13. public:
  14.     ul next = 0;
  15.     ul val = 0;
  16. };
  18. ul tot = 0;
  19. ul remain = 0;
  21. node nodes[4 * maxn + 6 * maxm + 1];
  23. ul stack[4 * maxn + 6 * maxm + 1];
  25. void push_front(ul& a, ul b)
  26. {
  27.     ul tmp;
  28.     if (remain) {
  29.         tmp = stack[remain];
  30.         --remain;
  31.     } else {
  32.         ++tot;
  33.         tmp = tot;
  34.     }
  35.     nodes[tmp].next = a;
  36.     nodes[tmp].val = b;
  37.     a = tmp;
  38. }
  40. void pop_front(ul& a)
  41. {
  42.     ++remain;
  43.     stack[remain] = a;
  44.     a = nodes[a].next;
  45. }
  47. ul n, m;
  49. ul query(const ul v[], ul index)
  50. {
  51.     return nodes[v[index]].val;
  52. }
  54. void change(ul v[], ul index, ul val, ul& changes)
  55. {
  56.     push_front(v[index], val);
  57.     push_front(changes, index);
  58. }
  60. ul op[maxm + 1];
  61. ul k[maxm + 1];
  62. ul a[maxm + 1];
  63. ul b[maxm + 1];
  64. ul fa[maxn + maxn + 1];
  65. ul rk[maxn + 1];
  66. ul sz[maxn + 1];
  68. ul sons[maxm + 1];
  70. ul ans[maxm + 1];
  72. ul getfather(ul x)
  73. {
  74.     if (!x) {
  75.         return x;
  76.     }
  77.     ul f = query(fa, x);
  78.     return f == x ? x : getfather(f);
  79. }
  81. void connect(ul x, ul y, ul& fac, ul& rkc, ul& szc)
  82. {
  83.     x = getfather(x);
  84.     y = getfather(y);
  85.     if (x == y || x == 0 || y == 0) {
  86.         return;
  87.     }
  88.     ul rkx = query(rk, x);
  89.     ul rky = query(rk, y);
  90.     if (rkx < rky) {
  91.         change(fa, x, y, fac);
  92.         change(sz, y, query(sz, x) + query(sz, y), szc);
  93.     } else if (rkx > rky) {
  94.         change(fa, y, x, fac);
  95.         change(sz, x, query(sz, x) + query(sz, y), szc);
  96.     } else {
  97.         change(fa, x, y, fac);
  98.         change(sz, y, query(sz, x) + query(sz, y), szc);
  99.         change(rk, y, rky + 1, rkc);
  100.     }
  101. }
  103. void search(ul curr)
  104. {
  105.     ul fac = 0;
  106.     ul rkc = 0;
  107.     ul szc = 0;
  108.     if (curr == 0) {
  109.         for (ul i = 1; i <= n; ++i) {
  110.             push_front(fa[i + n], i);
  111.             push_front(fa[i], i);
  112.             push_front(rk[i], 1);
  113.             push_front(sz[i], 1);
  114.         }
  115.     } else {
  116.         ul i = curr;
  117.         if (op[i] == 1) {
  118.             connect(a[i] + n, b[i] + n, fac, rkc, szc);
  119.         } else if (op[i] == 2) {
  120.             ul ta = getfather(a[i] + n);
  121.             if (ta) {
  122.                 change(sz, ta, query(sz, ta) - 1, szc);
  123.                 change(fa, a[i] + n, 0,  fac);
  124.             }
  125.         } else if (op[i] == 3) {
  126.             ul ta = getfather(a[i] + n);
  127.             ul tb = getfather(b[i] + n);
  128.             if (ta && tb && ta != tb) {
  129.                 change(sz, ta, query(sz, ta) - 1, szc);
  130.                 change(sz, tb, query(sz, tb) + 1, szc);
  131.                 change(fa, a[i] + n, tb, fac);
  132.             }
  133.         } else if (op[i] == 4) {
  134.             ul ta = getfather(a[i] + n);
  135.             ul tb = getfather(b[i] + n);
  136.             ans[i] = ta && tb && ta == tb ? 1 : 0;
  137.         } else if (op[i] == 5) {
  138.             ul ta = getfather(a[i] + n);
  139.             if (!ta) {
  140.                 ans[i] = 0;
  141.             } else {
  142.                 ans[i] = query(sz, ta);
  143.             }
  144.         }
  145.     }
  146.     for (ul eid = sons[curr]; eid; eid = nodes[eid].next) {
  147.         ul next = nodes[eid].val;
  148.         search(next);
  149.     }
  150.     if (curr != 0) {
  151.         while (fac) {
  152.             pop_front(fa[nodes[fac].val]);
  153.             pop_front(fac);
  154.         }
  155.         while (rkc) {
  156.             pop_front(rk[nodes[rkc].val]);
  157.             pop_front(rkc);
  158.         }
  159.         while (szc) {
  160.             pop_front(sz[nodes[szc].val]);
  161.             pop_front(szc);
  162.         }
  163.     }
  164. }
  166. int main()
  167. {
  168.     std::scanf("%u%u", &n, &m);
  169.     for (ul i = 1; i <= m; ++i) {
  170.         std::scanf("%u%u", &op[i], &k[i]);
  171.         push_front(sons[k[i]], i);
  172.         if (op[i] == 1 || op[i] == 3 || op[i] == 4) {
  173.             std::scanf("%u%u", &a[i], &b[i]);
  174.         } else {
  175.             std::scanf("%u", &a[i]);
  176.         }
  177.     }
  178.     search(0);
  179.     for (ul i = 1; i <= m; ++i) {
  180.         if (op[i] == 4) {
  181.             std::printf(ans[i] ? "Yes\n" : "No\n");
  182.         } else if (op[i] == 5) {
  183.             std::printf("%u\n", ans[i]);
  184.         }
  185.     }
  186.     return 0;
  187. }

B、A Funny Bipartite Graph

暴搜就能过。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxn = 18;
  10. ul T;
  12. ul n;
  14. char str[maxn + 1];
  16. ul a[maxn];
  18. ul g[maxn];
  20. std::vector<ul> rg[maxn];
  22. ul m[maxn][4];
  24. ul rdeg[maxn];
  26. const ul inf = 1e9;
  28. ul ans;
  30. ul ord[maxn];
  32. ul reach[1 << maxn];
  34. ul ldeg[maxn];
  36. void search(ul i, ul remainl, ul cans, ul alr)
  37. {
  38.     if ((alr | reach[remainl]) != (1 << n) - 1) {
  39.         return;
  40.     }
  41.     if (ans <= cans) {
  42.         return;
  43.     }
  44.     if (i == n) {
  45.         ans = cans;
  46.         return;
  47.     }
  48.     ul v = ord[i];
  49.     for (ul u : rg[v]) {
  50.         if (!(1 << u & remainl)) {
  51.             continue;
  52.         }
  53.         ul nans = cans - m[u][ldeg[u]];
  54.         ++ldeg[u];
  55.         nans += m[u][ldeg[u]];
  56.         search(i + 1, remainl & ~a[u], nans, alr | 1 << v);
  57.         --ldeg[u];
  58.     }
  59. }
  61. int main()
  62. {
  63.     std::scanf("%u", &T);
  64.     for (ul Case = 1; Case <= T; ++Case) {
  65.         std::scanf("%u", &n);
  66.         for (ul i = 0; i <= n - 1; ++i) {
  67.             rdeg[i] = 0;
  68.             ldeg[i] = 0;
  69.             ord[i] = i;
  70.             rg[i].resize(0);
  71.         }
  72.         for (ul i = 0; i <= n - 1; ++i) {
  73.             std::scanf("%s", str);
  74.             g[i] = 0;
  75.             for (ul j = 0; j <= n - 1; ++j) {
  76.                 g[i] |= ul(str[j] - '0') << j;
  77.                 rdeg[j] += ul(str[j] - '0');
  78.                 if (str[j] - '0') {
  79.                     rg[j].push_back(i);
  80.                 }
  81.             }
  82.         }
  83.         for (ul i = 1; i < (1 << n); ++i) {
  84.             ul t = 31 - __builtin_clz(i);
  85.             reach[i] = reach[i & ~(1 << t)] | g[t];
  86.         }
  87.         for (ul i = 0; i <= n - 1; ++i) {
  88.             std::scanf("%s", str);
  89.             a[i] = 0;
  90.             for (ul j = 0; j <= n - 1; ++j) {
  91.                 a[i] |= ul(str[j] - '0') << j;
  92.             }
  93.         }
  94.         for (ul i = 0; i <= n - 1; ++i) {
  95.             std::scanf("%u", &m[i][1]);
  96.             m[i][2] = m[i][1] * m[i][1];
  97.             m[i][3] = m[i][2] * m[i][1];
  98.         }
  99.         ans = inf;
  100.         std::sort(ord, ord + n, [&](ul a, ul b){return rdeg[a] < rdeg[b];});
  101.         search(0, (1 << n) - 1, 0, 0);
  102.         if (ans != inf) {
  103.             std::printf("%u\n", ans);
  104.         } else {
  105.             std::printf("-1\n");
  106.         }
  107.     }
  108.     return 0;
  109. }

C、And and Pair

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. const ul mod = 1e9 + 7;
  12. const ul maxlen = 1e5;
  14. char s[maxlen + 2];
  16. ul plus(ul a, ul b)
  17. {
  18.     return a + b < mod ? a + b : a + b - mod;
  19. }
  21. ul minus(ul a, ul b)
  22. {
  23.     return a < b ? a + mod - b : a - b;
  24. }
  26. ul mul(ul a, ul b)
  27. {
  28.     return ull(a) * ull(b) % mod;
  29. }
  31. int main()
  32. {
  33.     std::scanf("%u", &T);
  34.     for (ul Case = 1; Case <= T; ++Case) {
  35.         ul tmp = 1;
  36.         ul sum = 1;
  37.         std::scanf("%s", s + 1);
  38.         ul len = std::strlen(s + 1);
  39.         for (ul i = len; i; --i) {
  40.             if (s[i] == '1') {
  41.                 sum = plus(sum, tmp);
  42.                 tmp = mul(tmp, 3);
  43.             } else {
  44.                 tmp = mul(tmp, 2);
  45.             }
  46.         }
  47.         std::printf("%u\n", sum);
  48.     }
  49.     return 0;
  50. }

D、Bitwise Tree

用uint64_t f[2]来表示一个从到的映射，当输入为的时候，输出的第位等于f[t >> i & 1] >> i。于是考虑映射和复合的时候应该等于什么。那么有如下结果：
①对于：g[0] = f[0]; g[1] = f[0] & ~a ^ f[1] & a;
②对于：g[1] = f[1]; g[0] = f[0] & ~a ^ f[1] & a;
③对于：b = (f[0] ^ f[1]) & a; g[0] = f[0] ^ b; g[1] = f[1] ^ b;
于是可以完成一个映射和一个半截运算的复合，于是时间复杂度为。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using uss = std::uint8_t;
  9. const ul maxn = 1e5;
  11. ul n;
  13. ul q;
  15. const ul maxq = 1e5;
  17. ull a[maxn + 1];
  19. ul totedge;
  21. ul totedge0;
  23. class edge_t {
  24. public:
  25.     ul next = 0;
  26.     ul to = 0;
  27. };
  29. ul s[maxn + 1];
  31. edge_t sons[maxn];
  33. edge_t sons0[maxn];
  35. ul head0[maxn + 1];
  37. ul head[maxn + 1];
  39. void addedge0(ul a, ul b)
  40. {
  41.     ++totedge0;
  42.     sons0[totedge0].to = b;
  43.     sons0[totedge0].next = head0[a];
  44.     head0[a] = totedge0;
  45. }
  47. void addedge(ul a, ul b)
  48. {
  49.     ++totedge;
  50.     sons[totedge].to = b;
  51.     sons[totedge].next = head[a];
  52.     head[a] = totedge;
  53. }
  55. const ull full = ~ull(0);
  57. ull tmpans[maxn + 1][3][2];
  58. ul tim;
  59. ul already[maxn + 1];
  61. ull ans[maxq + 1][3];
  63. class query_t {
  64. public:
  65.     ul d = 0;
  66.     ul u = 0;
  67.     ul id = 0;
  68. };
  70. query_t querys[maxq + 1];
  72. ull f(ul s, ull a, ull b)
  73. {
  74.     return s == 0 ? (a | b) : (s == 1 ? (a & b) : (a ^ b));
  75. }
  77. ul d, pos;
  79. void search0(ul curr)
  80. {
  81.     for (ul eid = head0[curr]; eid; eid = sons0[eid].next) {
  82.         ul next = sons0[eid].to;
  83.         addedge(curr, next);
  84.         search0(next);
  85.     }
  86. }
  88. void deal(const ull from[], ul s, ull to[], ull a)
  89. {
  90.     if (s == 0) {
  91.         to[1] = from[1];
  92.         to[0] = from[0] & ~a ^ from[1] & a;
  93.     } else if (s == 1) {
  94.         to[0] = from[0];
  95.         to[1] = from[0] & ~a ^ from[1] & a;
  96.     } else {
  97.         ull b = (from[0] ^ from[1]) & a;
  98.         to[0] = from[0] ^ b;
  99.         to[1] = from[1] ^ b;
  100.     }
  101. }
  103. ull calc(const ull f[], ull a)
  104. {
  105.     return f[0] & ~a ^ f[1] & a;
  106. }
  108. void search(ul curr)
  109. {
  110.     ull cn[2];
  111.     ull tn[3][2];
  112.     if (already[curr] == tim) {
  113.         return;
  114.     }
  115.     already[curr] = tim;
  116.     auto c = tmpans[curr];
  117.     c[0][0] = 0;
  118.     c[0][1] = 0;
  119.     c[1][0] = ~ull(0);
  120.     c[1][1] = ~ull(0);
  121.     c[2][0] = 0;
  122.     c[2][1] = 0;
  123.     for (ul eid = head[curr]; eid; eid = sons[eid].next) {
  124.         ul next = sons[eid].to;
  125.         cn[0] = f(s[next], 0, a[next] + next * d);
  126.         cn[1] = f(s[next], ~ull(0), a[next] + next * d);
  127.         c[0][0] |= cn[0];
  128.         c[0][1] |= cn[1];
  129.         c[1][0] &= cn[0];
  130.         c[1][1] &= cn[1];
  131.         c[2][0] ^= cn[0];
  132.         c[2][1] ^= cn[1];
  133.         search(next);
  134.         auto n = tmpans[next];
  135.         for (ul i = 0; i <= 2; ++i) {
  136.             deal(n[i], s[next], tn[i], a[next] + next * d);
  137.         }
  138.         c[0][0] |= tn[0][0];
  139.         c[0][1] |= tn[0][1];
  140.         c[1][0] &= tn[1][0];
  141.         c[1][1] &= tn[1][1];
  142.         c[2][0] ^= tn[2][0];
  143.         c[2][1] ^= tn[2][1];
  144.     }
  145. }
  147. int main()
  148. {
  149.     std::scanf("%u%u", &n, &q);
  150.     for (ul i = 1; i <= n; ++i) {
  151.         std::scanf("%llu", &a[i]);
  152.     }
  153.     for (ul i = 2; i <= n; ++i) {
  154.         ul f;
  155.         std::scanf("%u%u", &f, &s[i]);
  156.         addedge0(f, i);
  157.     }
  158.     search0(1);
  159.     for (ul i = 1; i <= q; ++i) {
  160.         std::scanf("%u%u", &querys[i].d, &querys[i].u);
  161.         querys[i].id = i;
  162.     }
  163.     std::sort(querys + 1, querys + q + 1, [](const query_t& a, const query_t& b){return a.d < b.d;});
  164.     for (ul i = 1, j = 1; i <= q; i = j) {
  165.         for (j = i; j <= q && querys[j].d == querys[i].d; ++j);
  166.         d = querys[i].d;
  167.         ++tim;
  168.         for (ul k = i; k != j; ++k) {
  169.             ul u = querys[k].u;
  170.             search(u);
  171.             ull alpha = a[u] + u * d;
  172.             auto c = tmpans[u];
  173.             auto d = ans[querys[k].id];
  174.             d[0] = calc(c[0], alpha);
  175.             d[1] = calc(c[1], alpha);
  176.             d[2] = calc(c[2], alpha);
  177.         }
  178.     }
  179.     for (ul i = 1; i <= q; ++i) {
  180.         std::printf("%llu %llu %llu\n", ans[i][0], ans[i][1], ans[i][2]);
  181.     }
  182.     return 0;
  183. }

E、Bob's Problem

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul n, k, m;
  12. const ul maxm = 5e5;
  13. const ul maxn = 5e4;
  15. class edge_t {
  16. public:
  17.     ul u = 0;
  18.     ul v = 0;
  19.     ul w = 0;
  20.     ul c = 0;
  21. };
  23. edge_t edges[maxm + 1];
  25. ul fa[maxn + 1];
  26. ul rk[maxn + 1];
  28. ul tot;
  30. ul stack[maxm + 1];
  32. ul getfather(ul a)
  33. {
  34.     return fa[a] == a ? a : fa[a] = getfather(fa[a]);
  35. }
  37. bool connect(ul a, ul b)
  38. {
  39.     a = getfather(a);
  40.     b = getfather(b);
  41.     if (a == b) {
  42.         return false;
  43.     }
  44.     if (rk[a] < rk[b]) {
  45.         fa[a] = b;
  46.     } else if (rk[a] > rk[b]) {
  47.         fa[b] = a;
  48.     } else {
  49.         fa[a] = b;
  50.         ++rk[b];
  51.     }
  52.     return true;
  53. }
  55. int main()
  56. {
  57.     std::scanf("%u", &T);
  58.     for (ul Case = 1; Case <= T; ++Case) {
  59.         std::scanf("%u%u%u", &n, &m, &k);
  60.         for (ul i = 1; i <= n; ++i) {
  61.             rk[i] = 0;
  62.             fa[i] = i;
  63.         }
  64.         for (ul i = 1; i <= m; ++i) {
  65.             std::scanf("%u%u%u%u", &edges[i].u, &edges[i].v, &edges[i].w, &edges[i].c);
  66.         }
  67.         std::sort(edges + 1, edges + m + 1, [](const edge_t& a, const edge_t& b){return a.c != b.c ? a.c < b.c : a.w > b.w;});
  68.         tot = 0;
  69.         ull sum = 0;
  70.         for (ul i = 1; i <= m; ++i) {
  71.             if (edges[i].c) {
  72.                 if (!k) {
  73.                     break;
  74.                 }
  75.                 if (connect(edges[i].u, edges[i].v)) {
  76.                     --n;
  77.                     --k;
  78.                     sum += edges[i].w;
  79.                 } else {
  80.                     ++tot;
  81.                     stack[tot] = i;
  82.                 }
  83.             } else {
  84.                 n -= connect(edges[i].u, edges[i].v);
  85.                 sum += edges[i].w;
  86.             }
  87.         }
  88.         if (n != 1) {
  89.             std::printf("-1\n");
  90.             continue;
  91.         }
  92.         for (ul i = 1; i <= k && i <= tot; ++i) {
  93.             sum += edges[stack[i]].w;
  94.         }
  95.         std::printf("%llu\n", sum);
  96.     }
  97.     return 0;
  98. }

F、Dynamic Suffix Array

考虑整个字符串的后缀树，然后求出后缀树的深搜序，接着，每当砍掉后边一部分，那么一个后缀在后缀树上就会移动到其原始位置的某个祖先那里，所以只需要随着长度减小维护这个即可。注意字符串是随机的，那么公共子串的长度一定不长，这意味着任何节点到根的路径上的节点数不多。再注意到一点，任何两个存在的后缀在长度减小的过程中一定不会处于同一个节点上，请自己证明。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul q;
  10. const ul maxq = 1e6;
  12. class query_t {
  13. public:
  14.     ul len = 0;
  15.     ul k = 0;
  16.     ul ans = 0;
  17. };
  19. ul len;
  20. ul tot;
  22. char str[2];
  24. char s[maxq + 1];
  26. query_t querys[maxq + 1];
  28. class sam_t {
  29. public:
  30.     ul las;
  31.     class node {
  32.     public:
  33.         ul ch[26];
  34.         ul len = 0;
  35.         ul fa = 0;
  36.         node() {
  37.             std::memset(ch, 0, sizeof(ch));
  38.         }
  39.     };
  40.     std::vector<node> st = std::vector<node>(maxq + maxq);
  41.     void add(ul c)
  42.     {
  43.         ul p = las;
  44.         ul np = las = st.size();
  45.         st.push_back(node());
  46.         st[np].len = st[p].len + 1;
  47.         for ( ; p && !st[p].ch[c]; p = st[p].fa) {
  48.             st[p].ch[c] = np;
  49.         }
  50.         if (!p) {
  51.             st[np].fa = 1;
  52.         } else {
  53.             ul q = st[p].ch[c];
  54.             if (st[q].len == st[p].len + 1) {
  55.                 st[np].fa = q;
  56.             } else {
  57.                 ul nq = st.size();
  58.                 st.push_back(node());
  59.                 st[nq] = st[q];
  60.                 st[nq].len = st[p].len + 1;
  61.                 st[q].fa = st[np].fa = nq;
  62.                 for ( ; p && st[p].ch[c] == q; p = st[p].fa) {
  63.                     st[p].ch[c] = nq;
  64.                 }
  65.             }
  66.         }
  67.     }
  68.     void init() {
  69.         las = 1;
  70.         st.resize(0);
  71.         st.resize(2);
  72.     }
  73. };
  75. sam_t sam;
  77. class listnode {
  78. public:
  79.     ul next = 0;
  80.     ul val = 0;
  81. };
  83. ul listtot;
  85. listnode listnodes[maxq + maxq];
  87. ul listremain;
  88. ul listrestack[maxq + maxq];
  90. void push_front(ul& x, ul v)
  91. {
  92.     ul tmp;
  93.     if (listremain) {
  94.         tmp = listrestack[listremain];
  95.         --listremain;
  96.     } else {
  97.         ++listtot;
  98.         tmp = listtot;
  99.     }
  100.     listnodes[tmp].val = v;
  101.     listnodes[tmp].next = x;
  102.     x = tmp;
  103. }
  105. void pop_front(ul& x)
  106. {
  107.     ++listremain;
  108.     listrestack[listremain] = x;
  109.     x = listnodes[x].next;
  110. }
  112. void moveto(ul& y, ul& x)
  113. {
  114.     ul z = listnodes[y].next;
  115.     listnodes[y].next = x;
  116.     x = y;
  117.     y = z;
  118. }
  120. ul pos[maxq + maxq];
  122. void sort(ul len, ul& x, bool dir)
  123. {
  124.     if (listnodes[x].next == 0) {
  125.         return;
  126.     }
  127.     ul y = x, b = listnodes[x].next;
  128.     while (listnodes[b].next) {
  129.         y = listnodes[y].next;
  130.         b = listnodes[b].next;
  131.         b = listnodes[b].next;
  132.     }
  133.     ul py = y;
  134.     y = listnodes[y].next;
  135.     listnodes[py].next = 0;
  136.     sort(len, x, !dir);
  137.     sort(len, y, !dir);
  138.     ul z = 0;
  139.     while (x || y) {
  140.         if (x && y) {
  141.             if ((s[pos[listnodes[x].val] + len] > s[pos[listnodes[y].val] + len]) == dir) {
  142.                 moveto(x, z);
  143.             } else {
  144.                 moveto(y, z);
  145.             }
  146.         } else if (x) {
  147.             moveto(x, z);
  148.         } else {
  149.             moveto(y, z);
  150.         }
  151.     }
  152.     x = z;
  153. }
  155. ul sons[maxq + maxq];
  157. ul at[maxq + 1];
  159. ul dfn[maxq + maxq];
  161. ul tim;
  163. void search1(ul curr)
  164. {
  165.     for (ul eid = sons[curr]; eid; eid = listnodes[eid].next) {
  166.         ul next = listnodes[eid].val;
  167.         search1(next);
  168.         pos[curr] = std::max(pos[curr], pos[next]);
  169.     }
  170. }
  172. void search2(ul curr) 
  173. {
  174.     ++tim;
  175.     dfn[curr] = tim;
  176.     sort(sam.st[curr].len, sons[curr], 1);
  177.     while (sons[curr]) {
  178.         ul next = listnodes[sons[curr]].val;
  179.         pop_front(sons[curr]);
  180.         search2(next);
  181.     }
  182. }
  184. ul stack[maxq + 1];
  186. const ul sz = 1 << 21;
  188. ul tree[sz << 1];
  190. void change(ul pos, ul x)
  191. {
  192.     for (tree[pos |= sz] += x, pos >>= 1; pos; pos >>= 1) {
  193.         tree[pos] = tree[pos << 1] + tree[pos << 1 | 1];
  194.     }
  195. }
  197. ul getsum(ul l, ul r)
  198. {
  199.     ul ret = 0;
  200.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  201.         if (~l & 1) {
  202.             ret += tree[l ^ 1];
  203.         }
  204.         if (r & 1) {
  205.             ret += tree[r ^ 1];
  206.         }
  207.     }
  208.     return ret;
  209. }
  211. int main()
  212. {
  213.     std::scanf("%u", &q);
  214.     for (ul i = 1; i <= q; ++i) {
  215.         ul t;
  216.         std::scanf("%u", &t);
  217.         if (t == 1) {
  218.             std::scanf("%s", str);
  219.             ++len;
  220.             s[len] = str[0];
  221.         } else {
  222.             ++tot;
  223.             std::scanf("%u", &querys[tot].k);
  224.             querys[tot].len = len;
  225.         }
  226.     }
  227.     sam.init();
  228.     for (ul i = len; i >= 1; --i) {
  229.         sam.add(s[i] - 'a');
  230.         at[i] = sam.las;
  231.         pos[sam.las] = i;
  232.     }
  233.     for (ul i = 2; i != sam.st.size(); ++i) {
  234.         push_front(sons[sam.st[i].fa], i);
  235.     }
  236.     pos[1] = len + 1;
  237.     search1(1);
  238.     search2(1);
  239.     for (ul i = 1; i <= len; ++i) {
  240.         push_front(stack[i + sam.st[sam.st[at[i]].fa].len - 1], i);
  241.         change(dfn[at[i]], 1);
  242.     }
  243.     ul currlen = len;
  244.     for (ul i = tot; i; --i) {
  245.         while (currlen > querys[i].len) {
  246.             --currlen;
  247.             while (stack[currlen]) {
  248.                 ul t = listnodes[stack[currlen]].val;
  249.                 pop_front(stack[currlen]);
  250.                 change(dfn[at[t]], -1);
  251.                 at[t] = sam.st[at[t]].fa;
  252.                 if (at[t] != 1) {
  253.                     change(dfn[at[t]], 1);
  254.                     push_front(stack[t + sam.st[sam.st[at[t]].fa].len - 1], t);
  255.                 }
  256.             }
  257.         }
  258.         querys[i].ans = getsum(1, dfn[at[querys[i].k]]);
  259.     }
  260.     for (ul i = 1; i <= tot; ++i) {
  261.         std::printf("%u\n", querys[i].ans);
  262.     }
  263.     return 0;
  264. }

G、Eating Plan

模数的最大质因子为

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n, m;
  10. const ul maxtot = 2802;
  12. ul tot;
  14. const ul t = 998857459;
  16. ul fac[maxtot + 1];
  18. ul val[maxtot + 1];
  20. ul pos[maxtot + 1];
  22. ul tot2;
  24. std::pair<ul, ul> stack[(maxtot * (maxtot + 1) >> 1) + 1];
  26. ul tot3;
  28. std::pair<ul, ul> stack2[(maxtot * (maxtot + 1) >> 1) + 1];
  30. int main()
  31. {
  32.     fac[0] = 1;
  33.     for (ul i = 1; i <= maxtot; ++i) {
  34.         fac[i] = ull(fac[i - 1]) * ull(i) % t;
  35.     }
  36.     std::scanf("%u%u", &n, &m);
  37.     for (ul i = 1; i <= n; ++i) {
  38.         ul a;
  39.         std::scanf("%u", &a);
  40.         if (a > maxtot) {
  41.             continue;
  42.         }
  43.         ++tot;
  44.         val[tot] = fac[a];
  45.         pos[tot] = i;
  46.     }
  47.     for (ul i = 1; i <= tot; ++i) {
  48.         ul sum = 0;
  49.         for (ul j = i; j <= tot; ++j) {
  50.             sum = sum + val[j] < t ? sum + val[j] : sum + val[j] - t;
  51.             ++tot2;
  52.             stack[tot2].first = sum;
  53.             stack[tot2].second = pos[j] - pos[i] + 1;
  54.         }
  55.     }
  56.     std::sort(stack + 1, stack + tot2 + 1, [](const std::pair<ul, ul>& a, const std::pair<ul, ul>& b){return a.first != b.first ? a.first < b.first : a.second > b.second;});
  57.     for (ul i = 1; i <= tot2; ++i) {
  58.         while (tot3 && stack2[tot3].second >= stack[i].second) {
  59.             --tot3;
  60.         }
  61.         ++tot3;
  62.         stack2[tot3] = stack[i];
  63.     }
  64.     for (ul i = 1; i <= m; ++i) {
  65.         ul k;
  66.         std::scanf("%u", &k);
  67.         auto it = std::lower_bound(stack2 + 1, stack2 + tot3 + 1, std::pair<ul, ul>(k, 0)) - stack2;
  68.         if (it == tot3 + 1) {
  69.             std::printf("-1\n");
  70.         } else {
  71.             std::printf("%u\n", stack2[it].second);
  72.         }
  73.     }
  74.     return 0;
  75. }

H、Powers of Two

的开头正好是当且仅当：。注意只有当是零的时候才有可能出现“刚好相等”的问题，于是将的情况单独处理，那么该表达式的大于和大于等于可以换一下。故该问题实际就是最小化满足以下条件的：

二分并类欧几里得即可。

  1. def getsum(a, b, c, n):
  2.     if n <= 0 :
  3.         return 0
  4.     if a >= c or b >= c :
  5.         return getsum(a % c, b % c, c, n) + n * (n + 1) // 2 * (a // c) + n * (b // c)
  6.     if a == 0 :
  7.         return 0
  8.     if a * n + b < c :
  9.         return 0
  10.     return n * ((a * n + b) // c) - (c - b - 1) // a - getsum(c, c - b - 1, a, (a * n + b) // c - 1)
  12. import decimal
  13. from decimal import Decimal
  14. decimal.getcontext().prec = 1000
  15. two = Decimal("2")
  16. ten = Decimal("10")
  17. instr = input()
  18. p = int(instr.split(' ')[0])
  19. p0 = Decimal(p);
  20. p1 = Decimal(p + 1)
  21. k = int(instr.split(' ')[1])
  22. for i in range(0, 101) :
  23.     if p == 2 ** i :
  24.         k = k - 1
  26. alpha = 500
  27. a = int(ten.ln() / two.ln() * (10 ** alpha))
  28. c = 10 ** alpha
  29. b1 = int(p1.ln() / two.ln() * (10 ** alpha))
  30. b0 = int(p0.ln() / two.ln() * (10 ** alpha))
  32. l = -1
  33. r = 161173615628205990885158576527746324
  34. mid = 0
  36. while l + 1 != r :
  37.     mid = (l + r) // 2
  38.     if getsum(a, b1, c, mid) - getsum(a, b0, c, mid) >= k :
  39.         r = mid
  40.     else :
  41.         l = mid
  43. if r == 0 :
  44.     for i in range(0, 101):
  45.         if p == 2 ** i :
  46.             print(i)
  47. else :
  48.     print((r * a + b0) // c + 1)

I、

J、Summon

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 998244353;
  10. ul plus(ul a, ul b)
  11. {
  12.     return a + b < mod ? a + b : a + b - mod;
  13. }
  15. ul minus(ul a, ul b)
  16. {
  17.     return a < b ? a + mod - b : a - b;
  18. }
  20. ul mul(ul a, ul b)
  21. {
  22.     return ull(a) * ull(b) % mod;
  23. }
  25. void exgcd(li a, li b, li& x, li& y)
  26. {
  27.     if (b) {
  28.         exgcd(b, a % b, y, x);
  29.         y -= a / b * x;
  30.     } else {
  31.         x = 1;
  32.         y = 0;
  33.     }
  34. }
  36. ul inverse(ul a)
  37. {
  38.     li x, y;
  39.     exgcd(a, mod, x, y);
  40.     return x < 0 ? x + li(mod) : x;
  41. }
  43. ul n, m;
  45. const ul maxn = 1e5;
  47. std::vector<bool> ban(256, false);
  49. ul trans[64][64];
  51. void mul(const ul a[][64], const ul b[][64], ul c[][64])
  52. {
  53.     for (ul i = 0; i != 64; ++i) {
  54.         for (ul j = 0; j != 64; ++j) {
  55.             c[i][j] = 0;
  56.             for (ul k = 0; k != 64; ++k) {
  57.                 c[i][j] = plus(c[i][j], mul(a[i][k], b[k][j]));
  58.             }
  59.         }
  60.     }
  61. }
  63. void pow(const ul ina[][64], ul b, ul c[][64])
  64. {
  65.     static ul a[64][64];
  66.     static ul tmp[64][64];
  67.     std::memcpy(a, ina, sizeof(ul) << 12);
  68.     for (ul i = 0; i != 64; ++i) {
  69.         for (ul j = 0; j != 64; ++j) {
  70.             c[i][j] = i == j;
  71.         }
  72.     }
  73.     while (b) {
  74.         if (b & 1) {
  75.             mul(a, c, tmp);
  76.             std::memcpy(c, tmp, sizeof(ul) << 12);
  77.         }
  78.         b >>= 1;
  79.         mul(a, a, tmp);
  80.         std::memcpy(a, tmp, sizeof(ul) << 12);
  81.     }
  82. }
  84. ul totprime;
  85. ul prime[maxn + 1];
  86. std::vector<bool> notprime(maxn + 1, false);
  87. ul phi[maxn + 1];
  89. ul ans = 0;
  91. ul curr[64][64];
  93. bool able[64][64];
  95. int main()
  96. {
  97.     phi[1] = 1;
  98.     for (ul i = 2; i <= maxn; ++i) {
  99.         if (!notprime[i]) {
  100.             ++totprime;
  101.             prime[totprime] = i;
  102.             phi[i] = i - 1;
  103.         }
  104.         for (ul pid = 1; pid <= totprime; ++pid) {
  105.             ul p = prime[pid];
  106.             if (i * p > maxn) {
  107.                 break;
  108.             }
  109.             notprime[i * p] = true;
  110.             if (i % p == 0) {
  111.                 phi[i * p] = phi[i] * p;
  112.                 break;
  113.             } else {
  114.                 phi[i * p] = phi[i] * (p - 1);
  115.             }
  116.         }
  117.     }
  118.     std::scanf("%u%u", &n, &m);
  119.     for (ul i = 1; i <= m; ++i) {
  120.         ul a, b, c, d;
  121.         std::scanf("%u%u%u%u", &a, &b, &c, &d);
  122.         ban[a << 0 | b << 2 | c << 4 | d << 6] = true;
  123.     }
  124.     for (ul from = 0; from != 64; ++from) {
  125.         for (ul a : {0, 1, 2, 3}) {
  126.             if (ban[from << 2 | a]) {
  127.                 continue;
  128.             }
  129.             trans[from][(from << 2 | a) & 63] = 1;
  130.         }
  131.     }
  132.     for (ul i = 0; i != 64; ++i) {
  133.         for (ul j = 0; j != 64; ++j) {
  134.             able[i][j] = !(ban[(j << 2 | i >> 4) & 255] || ban[(j << 4 | i >> 2) & 255] || ban[(j << 6 | i >> 0) & 255]);
  135.         }
  136.     }
  137.     for (ul d = 1; d <= n; ++d) {
  138.         if (n % d != 0) {
  139.             continue;
  140.         }
  141.         ul tmp = 0;
  142.         if (d == 1) {
  143.             for (ul i = 0; i != 4; ++i) {
  144.                 if (!ban[i << 0 | i << 2 | i << 4 | i << 6]) {
  145.                     tmp = plus(tmp, 1);
  146.                 }
  147.             }
  148.         } else if (d == 2) {
  149.             for (ul i = 0; i != 16; ++i) {
  150.                 if (!ban[i << 0 | i << 4] && !ban[(i >> 2 | i << 2 | i << 6) & 255]) {
  151.                     tmp = plus(tmp, 1);
  152.                 }
  153.             }
  154.         } else {
  155.             pow(trans, d - 3, curr);
  156.             for (ul i = 0; i != 64; ++i) {
  157.                 for (ul j = 0; j != 64; ++j) {
  158.                     if (able[i][j]) {
  159.                         tmp = plus(tmp, curr[i][j]);
  160.                     }
  161.                 }
  162.             }
  163.         }
  164.         ans = plus(ans, mul(phi[n / d], tmp));
  165.     }
  166.     std::printf("%u\n", mul(ans, inverse(n)));
  167.     return 0;
  168. }

K、Tree

启发式合并套树套树。
注意， is up to 是指。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxn = 1e5;
  10. ul n, k;
  12. ul v[maxn + 1];
  14. class listnode {
  15. public:
  16.     ul val = 0;
  17.     ul next = 0;
  18. };
  20. ul listtot;
  21. listnode listnodes[maxn];
  23. void push_front(ul& x, ul v)
  24. {
  25.     ++listtot;
  26.     listnodes[listtot].val = v;
  27.     listnodes[listtot].next = x;
  28.     x = listtot;
  29. }
  31. ul sons[maxn + 1];
  33. std::mt19937_64 rnd;
  35. class node {
  36. public:
  37.     ul key = 0;
  38.     ul val = 0;
  39.     ul cnt = 0;
  40.     ul sum = 0;
  41.     ul lson = 0;
  42.     ul rson = 0;
  43.     ull weight = 0;
  44.     node() {
  45.         weight = rnd();
  46.     }
  47. };
  49. ul tot = 0;
  50. ul remain = 0;
  52. ul stack[1 << 22];
  54. node tree[1 << 22];
  56. void update(ul x)
  57. {
  58.     tree[x].sum = tree[x].cnt + tree[tree[x].lson].sum + tree[tree[x].rson].sum;
  59. }
  61. void lrotate(ul& x)
  62. {
  63.     ul y = tree[x].rson;
  64.     tree[x].rson = tree[y].lson;
  65.     tree[y].lson = x;
  66.     update(x);
  67.     update(y);
  68.     x = y;
  69. }
  71. void rrotate(ul& x)
  72. {
  73.     ul y = tree[x].lson;
  74.     tree[x].lson = tree[y].rson;
  75.     tree[y].rson = x;
  76.     update(x);
  77.     update(y);
  78.     x = y;
  79. }
  81. ul insert(ul& x, ul key, ul val)
  82. {
  83.     if (!x) {
  84.         if (remain) {
  85.             x = stack[remain];
  86.             --remain;
  87.         } else {
  88.             ++tot;
  89.             x = tot;
  90.         }
  91.         tree[x] = node();
  92.         tree[x].key = key;
  93.         tree[x].val = val;
  94.         tree[x].cnt = 1;
  95.         update(x);
  96.         return x;
  97.     }
  98.     if (tree[x].key == key) {
  99.         ++tree[x].cnt;
  100.         update(x);
  101.         return x;
  102.     } else if (tree[x].key < key) {
  103.         ul ret = insert(tree[x].rson, key, val);
  104.         update(x);
  105.         if (tree[x].weight < tree[tree[x].rson].weight) {
  106.             lrotate(x);
  107.         }
  108.         return ret;
  109.     } else if (tree[x].key > key) {
  110.         ul ret = insert(tree[x].lson, key, val);
  111.         update(x);
  112.         if (tree[x].weight < tree[tree[x].lson].weight) {
  113.             rrotate(x);
  114.         }
  115.         return ret;
  116.     }
  117. }
  119. ul find(ul x, ul key)
  120. {
  121.     if (!x) {
  122.         return 0;
  123.     }
  124.     if (tree[x].key == key) {
  125.         return x;
  126.     } else if (tree[x].key < key) {
  127.         return find(tree[x].rson, key);
  128.     } else {
  129.         return find(tree[x].lson, key);
  130.     }
  131. }
  133. void kill(ul x)
  134. {
  135.     ++remain;
  136.     stack[remain] = x;
  137. }
  139. ul getsum(ul x, ul t)
  140. {
  141.     if (!x) {
  142.         return 0;
  143.     }
  144.     if (tree[x].key > t) {
  145.         return getsum(tree[x].lson, t);
  146.     } else if (tree[x].key == t) {
  147.         return tree[x].sum - tree[tree[x].rson].sum;
  148.     } else if (tree[x].key < t) {
  149.         return tree[x].sum - tree[tree[x].rson].sum + getsum(tree[x].rson, t);
  150.     }
  151. }
  153. ul tot2;
  154. ul stack2[maxn + maxn + 1];
  156. ul tot3;
  157. ul stack3[maxn + maxn + 1];
  159. ull ans = 0;
  161. void search(ul curr, ul depth, ul& blob, ul& sz)
  162. {
  163.     blob = 0;
  164.     sz = 0;
  165.     for (ul eid = sons[curr]; eid; eid = listnodes[eid].next) {
  166.         ul next = listnodes[eid].val;
  167.         ul nextblob;
  168.         ul nextsz;
  169.         search(next, depth + 1, nextblob, nextsz);
  170.         if (sz < nextsz) {
  171.             std::swap(blob, nextblob);
  172.         }
  173.         sz += nextsz;
  174.         ++tot2;
  175.         stack2[tot2] = nextblob;
  176.         while (tot2) {
  177.             ul it2 = stack2[tot2];
  178.             --tot2;
  179.             if (!it2) {
  180.                 continue;
  181.             }
  182.             ++tot2;
  183.             stack2[tot2] = tree[it2].rson;
  184.             ++tot2;
  185.             stack2[tot2] = tree[it2].lson;
  186.             auto currit2 = find(blob, v[curr] + v[curr] - tree[it2].key);
  187.             if (!currit2) {
  188.                 continue;
  189.             }
  190.             ++tot3;
  191.             stack3[tot3] = tree[it2].val;
  192.             while (tot3) {
  193.                 ul it3 = stack3[tot3];
  194.                 --tot3;
  195.                 if (!it3) {
  196.                     continue;
  197.                 }
  198.                 ++tot3;
  199.                 stack3[tot3] = tree[it3].rson;
  200.                 ++tot3;
  201.                 stack3[tot3] = tree[it3].lson;
  202.                 ull data = getsum(tree[currit2].val, std::max(depth + depth + k, tree[it3].key) - tree[it3].key);
  203.                 ans += 2 * tree[it3].cnt * data;
  204.             }
  205.         }
  206.         ++tot2;
  207.         stack2[tot2] = nextblob;
  208.         while (tot2) {
  209.             ul it2 = stack2[tot2];
  210.             --tot2;
  211.             if (!it2) {
  212.                 continue;
  213.             }
  214.             ++tot2;
  215.             stack2[tot2] = tree[it2].rson;
  216.             ++tot2;
  217.             stack2[tot2] = tree[it2].lson;
  218.             auto currit2 = insert(blob, tree[it2].key, 0);
  219.             ++tot3;
  220.             stack3[tot3] = tree[it2].val;
  221.             while (tot3) {
  222.                 ul it3 = stack3[tot3];
  223.                 --tot3;
  224.                 if (!it3) {
  225.                     continue;
  226.                 }
  227.                 ++tot3;
  228.                 stack3[tot3] = tree[it3].rson;
  229.                 ++tot3;
  230.                 stack3[tot3] = tree[it3].lson;
  231.                 for (ul i = 1; i <= tree[it3].cnt; ++i) {
  232.                     insert(tree[currit2].val, tree[it3].key, 0);
  233.                 }
  234.                 kill(it3);
  235.             }
  236.             kill(it2);
  237.         }
  238.     }
  239.     ++sz;
  240.     auto currit2 = insert(blob, v[curr], 0);
  241.     insert(tree[currit2].val, depth, 0);
  242. }
  244. int main()
  245. {
  246.     rnd.seed(std::time(0));
  247.     std::scanf("%u%u", &n, &k);
  248.     for (ul i = 1; i <= n; ++i) {
  249.         std::scanf("%u", &v[i]);
  250.     }
  251.     for (ul i = 2; i <= n; ++i) {
  252.         ul f;
  253.         std::scanf("%u", &f);
  254.         push_front(sons[f], i);
  255.     }
  256.     ul blob, sz;
  257.     search(1, 0, blob, sz);
  258.     std::printf("%llu\n", ans);
  259.     return 0;
  260. }

L、Who is the Champion

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxn = 100;
  10. ul n;
  12. ul a[maxn + 1][maxn + 1];
  14. std::pair<ul, li> score[maxn + 1];
  16. int main()
  17. {
  18.     std::scanf("%u", &n);
  19.     for (ul i = 1; i <= n; ++i) {
  20.         for (ul j = 1; j <= n; ++j) {
  21.             std::scanf("%u", &a[i][j]);
  22.         }
  23.     }
  24.     for (ul i = 1; i <= n; ++i) {
  25.         for (ul j = 1; j <= n; ++j) {
  26.             if (i == j) {
  27.                 continue;
  28.             }
  29.             if (a[i][j] > a[j][i]) {
  30.                 score[i].first += 3;
  31.             } else if (a[i][j] == a[j][i]) {
  32.                 score[i].first += 1;
  33.             }
  34.             score[i].second += a[i][j];
  35.             score[i].second -= a[j][i];
  36.         }
  37.     }
  38.     ul mxid;
  39.     ul mxcnt;
  40.     std::pair<ul, li> mx(0, -1e9);
  41.     for (ul i = 1; i <= n; ++i) {
  42.         if (mx < score[i]) {
  43.             mxid = i;
  44.             mxcnt = 0;
  45.             mx = score[i];
  46.         }
  47.         if (mx == score[i]) {
  48.             ++mxcnt;
  49.         }
  50.     }
  51.     if (mxcnt == 1) {
  52.         std::printf("%u\n", mxid);
  53.     } else {
  54.         std::printf("play-offs\n");
  55.     }
  56.     return 0;
  57. }

M、XOR Sum

首先

故
于是
每一个表达式都可以插值得到答案。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 1e9 + 7;
  10. ul plus(ul a, ul b)
  11. {
  12.     return a + b < mod ? a + b : a + b - mod;
  13. }
  15. ul minus(ul a, ul b)
  16. {
  17.     return a < b ? a + mod - b : a - b;
  18. }
  20. ul mul(ul a, ul b)
  21. {
  22.     return ull(a) * ull(b) % mod;
  23. }
  25. void exgcd(li a, li b, li& x, li& y)
  26. {
  27.     if (b) {
  28.         exgcd(b, a % b, y, x);
  29.         y -= a / b * x;
  30.     } else {
  31.         x = 1;
  32.         y = 0;
  33.     }
  34. }
  36. ul inverse(ul a)
  37. {
  38.     li x, y;
  39.     exgcd(a, mod, x, y);
  40.     return x < 0 ? x + li(mod) : x;
  41. }
  43. ul pow(ul a, ul b)
  44. {
  45.     ul ret = 1;
  46.     while (b) {
  47.         if (b & 1) {
  48.             ret = mul(ret, a);
  49.         }
  50.         a = mul(a, a);
  51.         b >>= 1;
  52.     }
  53.     return ret;
  54. }
  56. ul t;
  57. ll x, y;
  59. const ul maxt = 1e5;
  61. ul f0(ul q)
  62. {
  63.     ul fourq = mul(4, q);
  64.     if (fourq == 1) {
  65.         return t;
  66.     }
  67.     return mul(minus(pow(fourq, t + 1), fourq), inverse(minus(fourq, 1)));
  68. }
  70. ul f1(ul q)
  71. {
  72.     return t;
  73. }
  75. ul f2(ul q)
  76. {
  77.     ul fourqp2 = plus(mul(4, q), 2);
  78.     if (fourqp2 == 1) {
  79.         return plus(t, 1);
  80.     }
  81.     return plus(mul(minus(pow(fourqp2, t + 1), fourqp2), inverse(minus(fourqp2, 1))), 1);
  82. }
  84. ul f3(ul q)
  85. {
  86.     return mul(minus(plus(mul(2, t), pow(minus(0, 1), t)), 1), inverse(4));
  87. }
  89. ul fac[maxt + 2];
  90. ul fiv[maxt + 2];
  91. ul facm[maxt + 2];
  92. ul fivm[maxt + 2];
  94. ul calc(const ul g[], ul deg, ul x)
  95. {
  96.     static ul xmjpre[maxt + 3];
  97.     static ul xmjsuf[maxt + 3];
  98.     xmjpre[0] = x;
  99.     for (ul j = 1; j <= deg; ++j) {
  100.         xmjpre[j] = mul(xmjpre[j - 1], minus(x, j));
  101.     }
  102.     xmjsuf[deg + 1] = 1;
  103.     for (ul j = deg; ~j; --j) {
  104.         xmjsuf[j] = mul(xmjsuf[j + 1], minus(x, j));
  105.     }
  106.     ul ans = 0;
  107.     for (ul i = 1; i <= deg; ++i) {
  108.         ans = plus(ans, mul(g[i], mul(mul(xmjpre[i - 1], xmjsuf[i + 1]), mul(fiv[i], fivm[deg - i]))));
  109.     }
  110.     return ans;
  111. }
  113. ul getans(ll lq, ll rq, ul (*f)(ul), ul deg)
  114. {
  115.     static ul g[maxt + 2];
  116.     g[0] = 0;
  117.     for (ul i = 1; i <= deg; ++i) {
  118.         g[i] = plus(g[i - 1], f((lq + i - 1) % mod));
  119.     }
  120.     return calc(g, deg, (rq - lq + 1) % mod);
  121. }
  123. ll ceil(ll a)
  124. {
  125.     return a > 0 ? (a + 3) / 4 : a / 4;
  126. }
  128. ll floor(ll a)
  129. {
  130.     return a < 0 ? (a - 3) / 4 : a / 4;
  131. }
  133. int main()
  134. {
  135.     fac[0] = 1;
  136.     facm[0] = 1;
  137.     for (ul i = 1; i <= maxt + 1; ++i) {
  138.         fac[i] = mul(fac[i - 1], i);
  139.         facm[i] = mul(facm[i - 1], minus(0, i));
  140.     }
  141.     fiv[maxt + 1] = inverse(fac[maxt + 1]);
  142.     fivm[maxt + 1] = inverse(facm[maxt + 1]);
  143.     for (ul i = maxt + 1; i; --i) {
  144.         fiv[i - 1] = mul(fiv[i], i);
  145.         fivm[i - 1] = mul(fivm[i], minus(0, i));
  146.     }
  147.     std::scanf("%u%lld%lld", &t, &x, &y);
  148.     std::printf("%u\n", plus(plus(getans(ceil(x), floor(y), f0, t + 1), getans(ceil(x - 1), floor(y - 1), f1, 1)), plus(getans(ceil(x - 2), floor(y - 2), f2, t + 1), getans(ceil(x - 3), floor(y - 3), f3, 1))));
  149.     return 0;
  150. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注