[关闭]
@qq290637843 2020-12-01T22:33:49.000000Z 字数 29281 阅读 400

2020杭电第五场

A、Tetrahedron 6814

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul base = 998244353;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < base ? a + b : a + b - base;
  17. }
  19. ul mul(ul a, ul b)
  20. {
  21.     return ull(a) * ull(b) % base;
  22. }
  24. const ul maxn = 6e6;
  26. ul T;
  28. ul n;
  30. ul inv[maxn + 1];
  32. ul sum[maxn + 1];
  34. int main()
  35. {
  36.     std::ios::sync_with_stdio(false);
  37.     std::cin.tie(0);
  38.     iss.tie(0);
  39.     oss.tie(0);
  40.     std::getline(std::cin, instr, char(0));
  41.     iss.str(instr);
  42.     inv[1] = 1;
  43.     sum[1] = 1;
  44.     for (ul i = 2; i <= maxn; ++i) {
  45.         inv[i] = ull(base - base / i) * inv[base % i] % base;
  46.         sum[i] = plus(sum[i - 1], mul(inv[i], inv[i]));
  47.     }
  48.     iss >> T;
  49.     for (ul Case = 1; Case <= T; ++Case) {
  50.         iss >> n;
  51.         oss << mul(mul(sum[n], 3), inv[n]) << '\n';
  52.     }
  53.     std::cout << oss.str();
  54.     return 0;
  55. }

B、Funny String 6815

如果这个题没有像这样卡空间，其实直接后缀树就行了。
官方题解如下：
image.png-334.7kB
image.png-344kB
image.png-241.3kB

  1. #pragma GCC target ("pclmul")
  2. #include <bits/stdc++.h>
  3. #include <emmintrin.h>
  4. #include <wmmintrin.h>
  6. using ul = std::uint32_t;
  7. using li = std::int32_t;
  8. using ull = std::uint64_t;
  9. using ll = std::int64_t;
  10. using pulul = std::pair<ul, ul>;
  12. ul T;
  13. ul n, m, q;
  15. const ul maxn = 1e6;
  17. ul s[maxn + 1];
  19. ul tim;
  21. ul rk[maxn + 2];
  22. ul sa[maxn + 2];
  23. ul fa[maxn + 1];
  24. std::vector<ul> son[maxn + 2];
  26. std::vector<pulul> cnt[maxn + 2];
  28. class node {
  29. public:
  30.     ul left = 0;
  31.     ul right = 0;
  32.     ul val = 0;
  33.     node()=default;
  34. };
  36. std::vector<node> segtree(maxn * 21);
  37. ul currroot;
  39. void change(ul pos, ul val, ul l, ul r, ul& nid)
  40. {
  41.     auto tmpnode = segtree[nid];
  42.     tmpnode.val += val;
  43.     if (l != r) {
  44.         ul midl = l + r >> 1;
  45.         ul midr = midl + 1;
  46.         if (pos <= midl) {
  47.             change(pos, val, l, midl, tmpnode.left);
  48.         } else {
  49.             change(pos, val, midr, r, tmpnode.right);
  50.         }
  51.     }
  52.     segtree.push_back(tmpnode);
  53.     nid = segtree.size() - 1;
  54. }
  56. ul query(ul l, ul r, ul nl, ul nr, ul nid)
  57. {
  58.     if (nl >= l && nr <= r) {
  59.         return segtree[nid].val;
  60.     }
  61.     ul ret = 0;
  62.     ul midl = nl + nr >> 1;
  63.     ul midr = midl + 1;
  64.     if (l <= midl && segtree[nid].left) {
  65.         ret += query(l, r, nl, midl, segtree[nid].left);
  66.     }
  67.     if (r >= midr && segtree[nid].right) {
  68.         ret += query(l, r, midr, nr, segtree[nid].right);
  69.     }
  70.     return ret;
  71. }
  73. ul head[maxn + 2];
  75. void search(ul curr)
  76. {
  77.     cnt[curr].resize(0);
  78.     ++tim;
  79.     ul prevroot = currroot;
  80.     if (curr != n + 1) {
  81.         change(s[curr + n + 1 - fa[curr]], 1, 1, m, currroot);
  82.     }
  83.     head[curr] = currroot;
  84.     ul atim = tim;
  85.     std::sort(son[curr].begin(), son[curr].end(), [&](ul a, ul b){return s[a + n + 1 - curr] < s[b + n + 1 - curr];});
  86.     for (ul next : son[curr]) {
  87.         search(next);
  88.         if (cnt[curr].empty() || cnt[curr].back().first != s[next + n + 1 - curr]) {
  89.             cnt[curr].push_back(pulul(s[next + n + 1 - curr], 0));
  90.         }
  91.         cnt[curr].back().second = tim - atim;
  92.     }
  93.     if (curr != n + 1) {
  94.         currroot = prevroot;
  95.     }
  96. }
  98. ul t, c, i;
  100. ul s2[maxn + 1], t1[maxn + 1], t2[maxn + 1], cc[maxn + 1];
  102. int main()
  103. {
  104.     std::scanf("%u", &T);
  105.     ul last = 0;
  106.     for (ul Case = 1; Case <= T; ++Case) {
  107.         std::scanf("%u%u%u", &n, &m, &q);
  108.         for (ul i = 1; i <= n; ++i) {
  109.             std::scanf("%u", &s[i]);
  110.             son[i].resize(0);
  111.         }
  112.         son[n + 1].resize(0);
  113.         for (ul i = 1; i <= n; ++i) {
  114.             s2[i] = s[i];
  115.         }
  116.         std::sort(s2 + 1, s2 + n + 1);
  117.         ul newm = std::unique(s2 + 1, s2 + n + 1) - s2 - 1;
  118.         for (ul i = 1; i <= newm; ++i) {
  119.             t1[s2[i]] = i;
  120.         }
  121.         for (ul i = 1; i <= n; ++i) {
  122.             s2[i] = t1[s[i]];
  123.         }
  124.         ul *x = t1, *y = t2;
  125.         std::memset(cc + 1, 0, newm * sizeof(ul));
  126.         for (ul i = 1; i <= n; ++i) {
  127.             ++cc[x[i] = s2[i]];
  128.         }
  129.         for (ul i = 1; i <= newm; ++i) {
  130.             cc[i] += cc[i - 1];
  131.         }
  132.         for (ul i = n; i >= 1; --i) {
  133.             sa[cc[x[i]]] = i;
  134.             --cc[x[i]];
  135.         }
  136.         for (ul k = 1; k <= n; k <<= 1) {
  137.             ul p = 1;
  138.             for (ul i = n - k + 1; i <= n; ++i) {
  139.                 y[p] = i;
  140.                 ++p;
  141.             }
  142.             for (ul i = 1; i <= n; ++i) {
  143.                 if (sa[i] > k) {
  144.                     y[p] = sa[i] - k;
  145.                     ++p;
  146.                 }
  147.             }
  148.             std::memset(cc + 1, 0, newm * sizeof(ul));
  149.             for (ul i = 1; i <= n; ++i) {
  150.                 ++cc[x[y[i]]];
  151.             }
  152.             for (ul i = 1; i <= newm; ++i) {
  153.                 cc[i] += cc[i - 1];
  154.             }
  155.             for (ul i = n; i >= 1; --i) {
  156.                 sa[cc[x[y[i]]]] = y[i];
  157.                 --cc[x[y[i]]];
  158.             }
  159.             std::swap(x, y);
  160.             p = 2;
  161.             x[sa[1]] = 1;
  162.             for (ul i = 2; i <= n; ++i) {
  163.                 x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
  164.             }
  165.             if (p >= n) break;
  166.             newm = p;
  167.         }
  168.         for (ul i = 1; i <= n; ++i) {
  169.             rk[sa[i]] = i;
  170.         }
  171.         rk[n + 1] = 0;
  172.         sa[0] = n + 1;
  173.         fa[n] = n + 1;
  174.         son[n + 1].push_back(n);
  175.         for (ul i = n - 1; i >= 1; --i) {
  176.             ul t;
  177.             for (t = fa[i + 1]; t != n + 1 && s[t - 1] != s[i]; t = fa[t]);
  178.             fa[i] = s[t - 1] == s[i] ? t - 1 : t;
  179.             son[fa[i]].push_back(i);
  180.         }
  181.         tim = 0;
  182.         segtree.resize(0);
  183.         segtree.resize(1);
  184.         currroot = 0;
  185.         search(n + 1);
  186.         last = 0;
  187.         for (ul qid = 1; qid <= q; ++qid) {
  188.             std::scanf("%u%u%u", &t, &c, &i);
  189.             c ^= last;
  190.             i ^= last;
  191.             if (t == 1) {
  192.                 --i;
  193.                 if (i) {
  194.                     bool less;
  195.                     if (c != s[i]) {
  196.                         less = c < s[i];
  197.                     } else {
  198.                         less = rk[1] < rk[i + 1];
  199.                     }
  200.                     if (less) {
  201.                         last = rk[i] + 1;
  202.                     } else {
  203.                         last = rk[i];
  204.                     }
  205.                 } else {
  206.                     ul l = 0, r = n + 1;
  207.                     while (l + 1 != r) {
  208.                         ul mid = l + r >> 1;
  209.                         i = sa[mid];
  210.                         bool less;
  211.                         if (c != s[i]) {
  212.                             less = c < s[i];
  213.                         } else {
  214.                             less = rk[1] < rk[i + 1];
  215.                         }
  216.                         (less ? r : l) = mid;
  217.                     }
  218.                     last = r;
  219.                 }
  220.             } else {
  221.                 ul tmp = rk[i] + 1;
  222.                 tmp -= query(1, c - 1, 1, m, head[i]);
  223.                 auto it = std::lower_bound(cnt[i].begin(), cnt[i].end(), pulul(c, 0));
  224.                 if (it != cnt[i].begin()) {
  225.                     tmp += std::prev(it)->second;
  226.                 }
  227.                 last = tmp;
  228.             }
  229.             std::printf("%u\n", last);
  230.         }
  231.         for (ul i = 1; i <= n + 1; ++i) {
  232.             son[i].clear();
  233.             cnt[i].clear();
  234.         }
  235.     }
  236.     return 0;
  237. }

C、Boring Game 6816

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T, n, k;
  14. const ul maxk = 10;
  16. std::vector<ul> stack[(1 << maxk) + 1];
  18. std::vector<ul> out;
  20. int main()
  21. {
  22.     std::ios::sync_with_stdio(false);
  23.     std::cin.tie(0);
  24.     iss.tie(0);
  25.     oss.tie(0);
  26.     std::getline(std::cin, instr, char(0));
  27.     iss.str(instr);
  28.     iss >> T;
  29.     for (ul Case = 1; Case <= T; ++Case) {
  30.         iss >> n >> k;
  31.         stack[1 << k].resize(0);
  32.         for (ul i = 1; i <= (n << k + 1); ++i) {
  33.             ul tmp;
  34.             iss >> tmp;
  35.             stack[1 << k].push_back(tmp);
  36.         }
  37.         std::reverse(stack[1 << k].begin(), stack[1 << k].end());
  38.         for (ul a = 1; a <= k; ++a) {
  39.             for (ul s = 1 << k, t = (1 << k) - (1 << a) + 1; s > t; --s, ++t) {
  40.                 stack[t].resize(0);
  41.                 while (stack[s].size() > stack[t].size()) {
  42.                     stack[t].push_back(stack[s].back());
  43.                     stack[s].pop_back();
  44.                 }
  45.             }
  46.         }
  47.         out.resize(0);
  48.         while (stack[1].size()) {
  49.             for (ul i = 1; i <= (1 << k); ++i) {
  50.                 out.push_back(stack[i].back());
  51.                 stack[i].pop_back();
  52.             }
  53.         }
  54.         for (ul i = 0; i != out.size(); ++i) {
  55.             if (i) {
  56.                 oss << ' ';
  57.             }
  58.             oss << out[i];
  59.         }
  60.         oss << '\n';
  61.     }
  62.     std::cout << oss.str();
  63.     return 0;
  64. }

D、Expression 6817

实际问题一并不需要，只需要，注意到


关于问题二，自己证明下方算法的正确性吧。注意每个变量只出现一次，这意味着每个变量的次数为一。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul mod = 998244353;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + mod - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % mod;
  27. }
  29. void exgcd(li a, li b, li& x, li& y)
  30. {
  31.     if (b) {
  32.         exgcd(b, a % b, y, x);
  33.         y -= a / b * x;
  34.     } else {
  35.         x = 1;
  36.         y = 0;
  37.     }
  38. }
  40. ul inverse(ul a)
  41. {
  42.     li x, y;
  43.     exgcd(a, mod, x, y);
  44.     return x < 0 ? x + li(mod) : x;
  45. }
  47. ul T;
  49. const ul maxn = 1e4;
  51. ul n, L;
  53. class node {
  54. public:
  55.     char op = 0;
  56.     ul left = 0;
  57.     ul right = 0;
  58.     node()=default;
  59.     node(char op, ul left, ul right): op(op), left(left), right(right) {}
  60. };
  62. std::vector<node> tree(maxn + maxn);
  64. std::vector<char> charstack;
  65. std::vector<ul> valstack;
  67. ul build(ul left, char op, ul right)
  68. {
  69.     tree.push_back(node(op, left, right));
  70.     return tree.size() - 1;
  71. }
  73. void onceout()
  74. {
  75.     ul right = valstack.back();
  76.     valstack.pop_back();
  77.     ul left = valstack.back();
  78.     valstack.pop_back();
  79.     char op = charstack.back();
  80.     charstack.pop_back();
  81.     valstack.push_back(build(left, op, right));
  82. }
  84. ul ans[6][maxn + maxn];
  86. ul al[6][maxn + maxn];
  87. ul altim;
  89. ul head;
  91. ul bi[6][6];
  93. ul calc(ul t, ul id)
  94. {
  95.     if (al[t][id] == altim) {
  96.         return ans[t][id];
  97.     }
  98.     al[t][id] = altim;
  99.     if (tree[id].op == '+') {
  100.         return ans[t][id] = plus(calc(t, tree[id].left), calc(t, tree[id].right));
  101.     } else if (tree[id].op == '-') {
  102.         return ans[t][id] = minus(calc(t, tree[id].left), calc(t, tree[id].right));
  103.     } else {
  104.         ans[t][id] = 0;
  105.         for (ul i = 0; i <= t; ++i) {
  106.             ans[t][id] = plus(ans[t][id], mul(mul(bi[t][i], calc(i, tree[id].left)), calc(t - i, tree[id].right)));
  107.         }
  108.         return ans[t][id];
  109.     }
  110. }
  112. class num {
  113. public:
  114.     ul v = 1;
  115.     ul cnt0 = 0;
  116.     num(ul x = 1): v(x ? x : ul(1)), cnt0(!x) {}
  117.     num(ul x, ul y): v(x), cnt0(y) {}
  118. };
  120. num operator*(const num& a, const num& b)
  121. {
  122.     return num(mul(a.v, b.v), a.cnt0 + b.cnt0);
  123. }
  125. num f[maxn + maxn];
  126. num g[maxn + maxn];
  127. ul dfn[maxn + maxn];
  129. ul stleft[maxn + maxn][16];
  130. ul stright[maxn + maxn][16];
  132. ul tim = 0;
  134. void search(ul curr)
  135. {
  136.     if (tree[curr].left) {
  137.         if (tree[curr].op == '+' || tree[curr].op == '-') {
  138.             f[tree[curr].left] = 1;
  139.         } else {
  140.             f[tree[curr].left] = calc(0, tree[curr].right);
  141.         }
  142.         g[tree[curr].left] = g[curr] * f[tree[curr].left];
  143.         search(tree[curr].left);
  144.     }
  145.     ++tim;
  146.     dfn[curr] = tim;
  147.     stleft[tim][0] = curr;
  148.     stright[tim][0] = curr;
  149.     if (tree[curr].right) {
  150.         if (tree[curr].op == '+') {
  151.             f[tree[curr].right] = 1;
  152.         } else if (tree[curr].op == '-') {
  153.             f[tree[curr].right] = mod - 1;
  154.         } else {
  155.             f[tree[curr].right] = calc(0, tree[curr].left);
  156.         }
  157.         g[tree[curr].right] = g[curr] * f[tree[curr].right];
  158.         search(tree[curr].right);
  159.     }
  160. }
  162. ul lca(ul a, ul b)
  163. {
  164.     a = dfn[a];
  165.     b = dfn[b];
  166.     if (a > b) {
  167.         std::swap(a, b);
  168.     }
  169.     return std::max(stright[a][31 - __builtin_clz(b - a + 1)], stleft[b][31 - __builtin_clz(b - a + 1)]);
  170. }
  172. const ul maxt = 30;
  174. ul is[maxt + 1];
  176. int main()
  177. {
  178.     std::ios::sync_with_stdio(false);
  179.     std::cin.tie(0);
  180.     iss.tie(0);
  181.     oss.tie(0);
  182.     std::getline(std::cin, instr, char(0));
  183.     iss.str(instr);
  184.     for (ul i = 0; i <= 5; ++i) {
  185.         bi[i][0] = 1;
  186.         for (ul j = 1; j <= i; ++j) {
  187.             bi[i][j] = plus(bi[i - 1][j - 1], bi[i - 1][j]);
  188.         }
  189.     }
  190.     iss >> T;
  191.     for (ul Case = 1; Case <= T; ++Case) {
  192.         iss >> L >> n;
  193.         iss >> instr;
  194.         charstack.resize(0);
  195.         valstack.resize(0);
  196.         tree.resize(0);
  197.         tree.resize(n + 1);
  198.         for (auto ch : instr) {
  199.             if (ch == '[') {
  200.                 valstack.push_back(0);
  201.             } else if (ch <= '9' && ch >= '0') {
  202.                 valstack.back() *= 10;
  203.                 valstack.back() += ch - '0';
  204.             } else if (ch == ']') {
  205.             } else if (ch == '(') {
  206.                 charstack.push_back('(');
  207.             } else if (ch == ')') {
  208.                 while (charstack.back() != '(') {
  209.                     onceout();
  210.                 }
  211.                 charstack.pop_back();
  212.             } else if (ch == '*') {
  213.                 while (charstack.size() && charstack.back() == '*') {
  214.                     onceout();
  215.                 }
  216.                 charstack.push_back(ch);
  217.             } else {
  218.                 while (charstack.size() && (charstack.back() == '*' || charstack.back() == '+' || charstack.back() == '-')) {
  219.                     onceout();
  220.                 }
  221.                 charstack.push_back(ch);
  222.             }
  223.         }
  224.         while (charstack.size()) {
  225.             onceout();
  226.         }
  227.         head = valstack.back();
  228.         ++altim;
  229.         for (ul i = 1; i <= n; ++i) {
  230.             li tmp;
  231.             iss >> tmp;
  232.             ans[0][i] = (tmp % li(mod) + mod) % mod;
  233.             al[0][i] = altim;
  234.             ans[1][i] = 1;
  235.             al[1][i] = altim;
  236.             for (ul j = 2; j <= 5; ++j) {
  237.                 ans[j][i] = 0;
  238.                 al[j][i] = altim;
  239.             }
  240.         }
  241.         for (ul i = 0; i <= 5; ++i) {
  242.             if (i) {
  243.                 oss << ' ';
  244.             }
  245.             oss << calc(i, head);
  246.         }
  247.         oss << '\n';
  248.         tim = 0;
  249.         g[head] = 1;
  250.         search(head);
  251.         for (ul i = 1; i <= head; ++i) {
  252.             for (ul k = 1; (1 << k) <= i; ++k) {
  253.                 stleft[i][k] = std::max(stleft[i][k - 1], stleft[i - (1 << k - 1)][k - 1]);
  254.             }
  255.         }
  256.         for (ul i = head; i >= 1; --i) {
  257.             for (ul k = 1; i + (1 << k) - 1 <= head; ++k) {
  258.                 stright[i][k] = std::max(stright[i][k - 1], stright[i + (1 << k - 1)][k - 1]);
  259.             }
  260.         }
  261.         ul m;
  262.         iss >> m;
  263.         for (ul qid = 1; qid <= m; ++qid) {
  264.             ul t;
  265.             iss >> t;
  266.             for (ul i = 1; i <= t; ++i) {
  267.                 iss >> is[i];
  268.             }
  269.             std::sort(is + 1, is + t + 1, [](ul a, ul b){return dfn[a] < dfn[b];});
  270.             num ans1, ans2;
  271.             for (ul i = 1; i <= t; ++i) {
  272.                 ans1 = ans1 * g[is[i]];
  273.             }
  274.             bool flag = true;
  275.             for (ul i = 1, j = 2; j <= t; ++i, ++j) {
  276.                 ul l = lca(is[i], is[j]);
  277.                 if (tree[l].op != '*') {
  278.                     flag = false;
  279.                     break;
  280.                 }
  281.                 ans2 = ans2 * g[l] * f[tree[l].left] * f[tree[l].right];
  282.             }
  283.             ul ans;
  284.             if (!flag || ans1.cnt0 != ans2.cnt0) {
  285.                 ans = 0;
  286.             } else {
  287.                 ans = mul(ans1.v, inverse(ans2.v));
  288.             }
  289.             oss << ans << '\n';
  290.         }
  291.     }
  292.     std::cout << oss.str();
  293.     return 0;
  294. }

E、Array Repairing 6818

首先，构成一个个点的有向基环树森林，可以发现，当时，消耗就是减去连通块的数量，而时，消耗就是减去连通块的数量加上叶子的数量。证明很容易，只需要说明两个对应概念在两种操作下的减小量和单步消耗的比值不超过一，且能达到。

叶子数量的期望值很容易求，现在考虑求连通块数量的期望值。用表示中满足连通块数量刚好是的数列的数量（），用表示中所有数列的数量。那么显然，其中。
于是和有如下关系：

于是

于是连通块数量期望值就是

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  11. using vul = std::vector<ul>;
  13. const ul base = 998244353;
  15. ul plus(ul a, ul b)
  16. {
  17.     return a + b < base ? a + b : a + b - base;
  18. }
  20. ul minus(ul a, ul b)
  21. {
  22.     return a < b ? a + base - b : a - b;
  23. }
  25. ul mul(ul a, ul b)
  26. {
  27.     return ull(a) * ull(b) % base;
  28. }
  30. void exgcd(li a, li b, li& x, li& y)
  31. {
  32.     if (b) {
  33.         exgcd(b, a % b, y, x);
  34.         y -= x * (a / b);
  35.     } else {
  36.         x = 1;
  37.         y = 0;
  38.     }
  39. }
  41. ul inverse(ul a)
  42. {
  43.     li x, y;
  44.     exgcd(a, base, x, y);
  45.     return x < 0 ? x + li(base) : x;
  46. }
  48. ul pow(ul a, ul b)
  49. {
  50.     ul ret = 1;
  51.     ul temp = a;
  52.     while (b) {
  53.         if (b & 1) {
  54.             ret = mul(ret, temp);
  55.         }
  56.         temp = mul(temp, temp);
  57.         b >>= 1;
  58.     }
  59.     return ret;
  60. }
  62. class polynomial : public vul {
  63. public:
  64.     void clearzero() {
  65.         while (size() && !back()) {
  66.             pop_back();
  67.         }
  68.     }
  69.     polynomial()=default;
  70.     polynomial(const vul& a): vul(a) { }
  71.     polynomial(vul&& a): vul(std::move(a)) { }
  72.     ul degree() const {
  73.         return size() - 1;
  74.     }
  75.     ul operator()(ul x) const {
  76.         ul ret = 0;
  77.         for (ul i = size() - 1; ~i; --i) {
  78.             ret = mul(ret, x);
  79.             ret = plus(ret, vul::operator[](i));
  80.         }
  81.         return ret;
  82.     }
  83. };
  85. polynomial& operator+=(polynomial& a, const polynomial& b)
  86. {
  87.     a.resize(std::max(a.size(), b.size()), 0);
  88.     for (ul i = 0; i != b.size(); ++i) {
  89.         a[i] = plus(a[i], b[i]);
  90.     }
  91.     a.clearzero();
  92.     return a;
  93. }
  95. polynomial operator+(const polynomial& a, const polynomial& b)
  96. {
  97.     polynomial ret = a;
  98.     return ret += b;
  99. }
  101. polynomial& operator-=(polynomial& a, const polynomial& b)
  102. {
  103.     a.resize(std::max(a.size(), b.size()), 0);
  104.     for (ul i = 0; i != b.size(); ++i) {
  105.         a[i] = minus(a[i], b[i]);
  106.     }
  107.     a.clearzero();
  108.     return a;
  109. }
  111. polynomial operator-(const polynomial& a, const polynomial& b)
  112. {
  113.     polynomial ret = a;
  114.     return ret -= b;
  115. }
  117. class ntt_t {
  118. public:
  119.     static const ul lgsz = 20;
  120.     static const ul sz = 1 << lgsz;
  121.     static const ul g = 3;
  122.     ul w[sz + 1];
  123.     ul leninv[lgsz + 1];
  124.     ntt_t() {
  125.         ul wn = pow(g, (base - 1) >> lgsz);
  126.         w[0] = 1;
  127.         for (ul i = 1; i <= sz; ++i) {
  128.             w[i] = mul(w[i - 1], wn);
  129.         }
  130.         leninv[lgsz] = inverse(sz);
  131.         for (ul i = lgsz - 1; ~i; --i) {
  132.             leninv[i] = plus(leninv[i + 1], leninv[i + 1]);
  133.         }
  134.     }
  135.     void operator()(vul& v, ul& n, bool inv) {
  136.         ul lgn = 0;
  137.         while ((1 << lgn) < n) {
  138.             ++lgn;
  139.         }
  140.         n = 1 << lgn;
  141.         v.resize(n, 0);
  142.         for (ul i = 0, j = 0; i != n; ++i) {
  143.             if (i < j) {
  144.                 std::swap(v[i], v[j]);
  145.             }
  146.             ul k = n >> 1;
  147.             while (k & j) {
  148.                 j &= ~k;
  149.                 k >>= 1;
  150.             }
  151.             j |= k;
  152.         }
  153.         for (ul lgmid = 0; (1 << lgmid) != n; ++lgmid) {
  154.             ul mid = 1 << lgmid;
  155.             ul len = mid << 1;
  156.             for (ul i = 0; i != n; i += len) {
  157.                 for (ul j = 0; j != mid; ++j) {
  158.                     ul t0 = v[i + j];
  159.                     ul t1 = mul(w[inv ? (len - j << lgsz - lgmid - 1) : (j << lgsz - lgmid - 1)], v[i + j + mid]);
  160.                     v[i + j] = plus(t0, t1);
  161.                     v[i + j + mid] = minus(t0, t1);
  162.                 }
  163.             }
  164.         }
  165.         if (inv) {
  166.             for (ul i = 0; i != n; ++i) {
  167.                 v[i] = mul(v[i], leninv[lgn]);
  168.             }
  169.         }
  170.     }
  171. } ntt;
  173. polynomial& operator*=(polynomial& a, const polynomial& b)
  174. {
  175.     if (!b.size() || !a.size()) {
  176.         a.resize(0);
  177.         return a;
  178.     }
  179.     polynomial temp = b;
  180.     ul npmp1 = a.size() + b.size() - 1;
  181.     if (ull(a.size()) * ull(b.size()) <= ull(npmp1) * ull(50)) {
  182.         temp.resize(0);
  183.         temp.resize(npmp1, 0);
  184.         for (ul i = 0; i != a.size(); ++i) {
  185.             for (ul j = 0; j != b.size(); ++j) {
  186.                 temp[i + j] = plus(temp[i + j], mul(a[i], b[j]));
  187.             }
  188.         }
  189.         a = temp;
  190.         a.clearzero();
  191.         return a;
  192.     }
  193.     ntt(a, npmp1, false);
  194.     ntt(temp, npmp1, false);
  195.     for (ul i = 0; i != npmp1; ++i) {
  196.         a[i] = mul(a[i], temp[i]);
  197.     }
  198.     ntt(a, npmp1, true);
  199.     a.clearzero();
  200.     return a;
  201. }
  203. polynomial operator*(const polynomial& a, const polynomial& b)
  204. {
  205.     polynomial ret = a;
  206.     return ret *= b;
  207. }
  209. polynomial& operator*=(polynomial& a, ul b)
  210. {
  211.     if (!b) {
  212.         a.resize(0);
  213.         return a;
  214.     }
  215.     for (ul i = 0; i != a.size(); ++i) {
  216.         a[i] = mul(a[i], b);
  217.     }
  218.     return a;
  219. }
  221. polynomial operator*(const polynomial& a, ul b)
  222. {
  223.     polynomial ret = a;
  224.     return ret *= b;
  225. }
  227. polynomial inverse(const polynomial& a, ul lgdeg)
  228. {
  229.     polynomial ret({inverse(a[0])});
  230.     polynomial temp;
  231.     polynomial tempa;
  232.     for (ul i = 0; i != lgdeg; ++i) {
  233.         tempa.resize(0);
  234.         tempa.resize(1 << i << 1, 0);
  235.         for (ul j = 0; j != tempa.size() && j != a.size(); ++j) {
  236.             tempa[j] = a[j];
  237.         }
  238.         temp = ret * (polynomial({2}) - tempa * ret);
  239.         if (temp.size() > (1 << i << 1)) {
  240.             temp.resize(1 << i << 1, 0);
  241.         }
  242.         temp.clearzero();
  243.         std::swap(temp, ret);
  244.     }
  245.     return ret;
  246. }
  248. polynomial diffrential(const polynomial& a)
  249. {
  250.     if (!a.size()) {
  251.         return a;
  252.     }
  253.     polynomial ret(vul(a.size() - 1, 0));
  254.     for (ul i = 1; i != a.size(); ++i) {
  255.         ret[i - 1] = mul(a[i], i);
  256.     }
  257.     return ret;
  258. }
  260. polynomial integral(const polynomial& a)
  261. {
  262.     polynomial ret(vul(a.size() + 1, 0));
  263.     for (ul i = 0; i != a.size(); ++i) {
  264.         ret[i + 1] = mul(a[i], inverse(i + 1));
  265.     }
  266.     return ret;
  267. }
  269. polynomial ln(const polynomial& a, ul lgdeg)
  270. {
  271.     polynomial da = diffrential(a);
  272.     polynomial inva = inverse(a, lgdeg);
  273.     polynomial ret = integral(da * inva);
  274.     if (ret.size() > (1 << lgdeg)) {
  275.         ret.resize(1 << lgdeg);
  276.         ret.clearzero();
  277.     }
  278.     return ret;
  279. }
  281. const ul maxn = 5e5;
  283. ul fac[maxn + 1];
  284. ul fiv[maxn + 1];
  286. int main()
  287. {
  288.     std::ios::sync_with_stdio(false);
  289.     std::cin.tie(0);
  290.     iss.tie(0);
  291.     oss.tie(0);
  292.     std::getline(std::cin, instr, char(0));
  293.     iss.str(instr);
  294.     ul n;
  295.     iss >> n;
  296.     fac[0] = 1;
  297.     for (ul i = 1; i <= n; ++i) {
  298.         fac[i] = mul(fac[i - 1], i);
  299.     }
  300.     fiv[n] = inverse(fac[n]);
  301.     for (ul i = n; i >= 1; --i) {
  302.         fiv[i - 1] = mul(fiv[i], i);
  303.     }
  304.     polynomial g(vul(n + 1));
  305.     g[0] = 1;
  306.     for (ul i = 1; i <= n; ++i) {
  307.         g[i] = mul(fiv[i], pow(i, i));
  308.     }
  309.     polynomial f = ln(g, 32 - __builtin_clz(n));
  310.     f.resize(n + 1);
  311.     polynomial h = f * g;
  312.     h.resize(n + 1);
  313.     for (ul i = 1; i <= n; ++i) {
  314.         ul tmp = mul(h[i], fac[i]);
  315.         ul tmp2 = inverse(mul(g[i], fac[i]));
  316.         oss << "0 " << minus(i, mul(tmp, tmp2)) << ' ' << plus(minus(i, mul(tmp, tmp2)), mul(mul(pow(i - 1, i), tmp2), i)) << '\n';
  317.     }
  318.     std::cout << oss.str();
  319.     return 0;
  320. }

F、Alice and Bob 6819

官方题解如下，很清楚：
无标题.png-248kB

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul maxn = 1e5;
  14. ul T;
  16. ul n, v, q, k;
  18. ul stack[maxn + 1];
  19. ul cnt;
  21. ul num[maxn + 1];
  23. ul al[maxn + 1];
  25. int main()
  26. {
  27.     std::ios::sync_with_stdio(false);
  28.     std::cin.tie(0);
  29.     iss.tie(0);
  30.     oss.tie(0);
  31.     std::getline(std::cin, instr, char(0));
  32.     iss.str(instr);
  33.     iss >> T;
  34.     for (ul Case = 1; Case <= T; ++Case) {
  35.         iss >> n >> v >> q >> k;
  36.         cnt = 0;
  37.         for (ul i = 1; i <= q; ++i) {
  38.             ul tmp;
  39.             iss >> tmp;
  40.             al[tmp] = Case;
  41.             ul it = std::lower_bound(stack + 1, stack + cnt + 1, tmp) - stack;
  42.             cnt = std::max(cnt, it);
  43.             stack[it] = tmp;
  44.         }
  45.         std::memset(num + 1, 0, k * sizeof(ul));
  46.         for (ul i = 1; i <= n; ++i) {
  47.             if (al[i] != Case) {
  48.                 ul it = std::lower_bound(stack + 1, stack + cnt + 1, i) - stack;
  49.                 ++num[it];
  50.             }
  51.         }
  52.         if (v == 1) {
  53.             if (num[k] > 0) {
  54.                 oss << "YES " << num[k] << '\n';
  55.             } else {
  56.                 ul sum = 0;
  57.                 for (ul i = 1; i + 1 <= k; ++i) {
  58.                     sum += num[i];
  59.                 }
  60.                 if (sum & 1) {
  61.                     oss << "YES " << sum - num[k - 1] + (num[k - 1] > 0) << '\n';
  62.                 } else {
  63.                     oss << "NO\n";
  64.                 }
  65.             }
  66.         } else {
  67.             if (num[k - 1] >= 2) {
  68.                 oss << "YES 1\n";
  69.             } else {
  70.                 ul sum = 0;
  71.                 for (ul i = 1; i + 1 <= k; ++i) {
  72.                     sum += num[i];
  73.                 }
  74.                 if (sum & 1) {
  75.                     oss << "YES " << (num[k - 1] ? 1 + (num[k - 2] > 0) : (num[k - 2] > 0) + (num[k - 2] > 1)) + sum - num[k - 1] - num[k - 2] << '\n';
  76.                 } else {
  77.                     oss << "NO\n";
  78.                 }
  79.             }
  80.         }
  81.     }
  82.     std::cout << oss.str();
  83.     return 0;
  84. }

G、Tree 6820

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  11. using pullull = std::pair<ull, ull>;
  13. const ul maxn = 2e5;
  15. ul T;
  17. ul n, k;
  19. class edge_t {
  20. public:
  21.     ul to = 0;
  22.     ul d = 0;
  23.     edge_t()=default;
  24.     edge_t(ul a, ul b): to(a), d(b) {}
  25. };
  27. std::vector<edge_t> edge[maxn + 1];
  29. ull ans[maxn + 1][5];
  31. ull outans;
  33. void search(ul curr, ul prev)
  34. {
  35.     static std::vector<pullull> stack;
  36.     for (const auto& e : edge[curr]) {
  37.         ul next = e.to;
  38.         if (next == prev) {
  39.             continue;
  40.         }
  41.         search(next, curr);
  42.     }
  43.     stack.resize(0);
  44.     for (const auto& e : edge[curr]) {
  45.         ul next = e.to;
  46.         if (next == prev) {
  47.             continue;
  48.         }
  49.         stack.push_back(pullull(e.d + ans[next][0], e.d + ans[next][6]));
  50.     }
  51.     std::sort(stack.rbegin(), stack.rend());
  52.     ans[curr][0] = ans[curr][7] = ans[curr][8] = ans[curr][9] = 0;
  53.     for (ul i = 0; i + 1 < k && i != stack.size(); ++i) {
  54.         ans[curr][0] += stack[i].first;
  55.     }
  56.     for (ul i = 0; i < k && i != stack.size(); ++i) {
  57.         ans[curr][10] += stack[i].first;
  58.     }
  59.     if (k >= 1) {
  60.         for (ul i = 0; i != stack.size(); ++i) {
  61.             ans[curr][11] += stack[i].first;
  62.             ans[curr][12] += stack[i].first;
  63.         }
  64.     }
  65.     if (k >= 2) {
  66.         ull tmp = 0;
  67.         for (ul i = 0; i != k - 2 && i != stack.size(); ++i) {
  68.             tmp += stack[i].first;
  69.         }
  70.         ull tmp2 = 0;
  71.         for (ul i = k - 2; i < stack.size(); ++i) {
  72.             tmp2 = std::max(tmp2, stack[i].second);
  73.         }
  74.         tmp += tmp2;
  75.         tmp2 = 0;
  76.         ull tmp3 = 0;
  77.         for (ul i = 0; i != k - 1 && i != stack.size(); ++i) {
  78.             tmp2 += stack[i].first;
  79.             tmp3 = std::max(tmp3, stack[i].second - stack[i].first);
  80.         }
  81.         tmp = std::max(tmp, tmp3 + tmp2);
  82.         ans[curr][13] = std::max(ans[curr][14], tmp);
  83.     }
  84.     if (k >= 1) {
  85.         ull tmp = 0;
  86.         for (ul i = 0; i != k - 1 && i != stack.size(); ++i) {
  87.             tmp += stack[i].first;
  88.         }
  89.         ull tmp2 = 0;
  90.         for (ul i = k - 1; i < stack.size(); ++i) {
  91.             tmp2 = std::max(tmp2, stack[i].second);
  92.         }
  93.         tmp += tmp2;
  94.         tmp2 = 0;
  95.         ull tmp3 = 0;
  96.         for (ul i = 0; i != k && i != stack.size(); ++i) {
  97.             tmp2 += stack[i].first;
  98.             tmp3 = std::max(tmp3, stack[i].second - stack[i].first);
  99.         }
  100.         tmp = std::max(tmp, tmp3 + tmp2);
  101.         ans[curr][15] = std::max(ans[curr][16], tmp);
  102.     }
  103.     outans = std::max(outans, ans[curr][17]);
  104.     outans = std::max(outans, ans[curr][18]);
  105. }
  107. int main()
  108. {
  109.     std::ios::sync_with_stdio(false);
  110.     std::cin.tie(0);
  111.     iss.tie(0);
  112.     oss.tie(0);
  113.     std::getline(std::cin, instr, char(0));
  114.     iss.str(instr);
  115.     iss >> T;
  116.     for (ul Case = 1; Case <= T; ++Case) {
  117.         iss >> n >> k;
  118.         for (ul i = 1; i <= n; ++i) {
  119.             edge[i].resize(0);
  120.         }
  121.         for (ul i = 1; i <= n - 1; ++i) {
  122.             ul u, v, d;
  123.             iss >> u >> v >> d;
  124.             edge[u].push_back(edge_t(v, d));
  125.             edge[v].push_back(edge_t(u, d));
  126.         }
  127.         if (!k) {
  128.             oss << "0\n";
  129.             continue;
  130.         }
  131.         outans = 0;
  132.         search(1, 0);
  133.         oss << outans << '\n';
  134.     }
  135.     std::cout << oss.str();
  136.     return 0;
  137. }

H、Set2 6821

设表示在有个数的情况，存活的概率，递推即可。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul mod = 998244353;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + mod - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % mod;
  27. }
  29. void exgcd(li a, li b, li& x, li& y)
  30. {
  31.     if (b) {
  32.         exgcd(b, a % b, y, x);
  33.         y -= a / b * x;
  34.     } else {
  35.         x = 1;
  36.         y = 0;
  37.     }
  38. }
  40. ul inverse(ul a)
  41. {
  42.     li x, y;
  43.     exgcd(a, mod, x, y);
  44.     return x < 0 ? x + li(mod) : x;
  45. }
  47. const ul maxn = 5e3;
  48. ul T, n, k;
  50. ul fac[maxn + 1];
  51. ul fiv[maxn + 1];
  53. ul ans[maxn + 1][maxn + 1];
  55. ul bi(ul a, ul b)
  56. {
  57.     return mul(fac[a], mul(fiv[a - b], fiv[b]));
  58. }
  60. ul biv(ul a, ul b)
  61. {
  62.     return mul(fiv[a], mul(fac[a - b], fac[b]));
  63. }
  65. int main()
  66. {
  67.     std::ios::sync_with_stdio(false);
  68.     std::cin.tie(0);
  69.     iss.tie(0);
  70.     oss.tie(0);
  71.     std::getline(std::cin, instr, char(0));
  72.     iss.str(instr);
  73.     fac[0] = 1;
  74.     for (ul i = 1; i <= maxn; ++i) {
  75.         fac[i] = mul(fac[i - 1], i);
  76.     }
  77.     fiv[maxn] = inverse(fac[maxn]);
  78.     for (ul i = maxn; i >= 1; --i) {
  79.         fiv[i - 1] = mul(fiv[i], i);
  80.     }
  81.     iss >> T;
  82.     for (ul Case = 1; Case <= T; ++Case) {
  83.         iss >> n >> k;
  84.         ul alpha = n % (k + 1);
  85.         for (ul i = 1; i <= alpha; ++i) {
  86.             ans[alpha][i] = 1;
  87.         }
  88.         for (ul r = alpha + k + 1; r <= n; r += k + 1) {
  89.             ans[r][19] = 0;
  90.             ul tmp = biv(r - 1, k);
  91.             for (ul i = 2; i <= r; ++i) {
  92.                 ans[r][i] = 0;
  93.                 for (ul j = std::max(k + i, r) - r; j <= std::min(k, i - 2); ++j) {
  94.                     ans[r][i] = plus(ans[r][i], mul(ans[r - k - 1][i - j - 1], mul(bi(i - 2, j), bi(r - i, k - j))));
  95.                 }
  96.                 ans[r][i] = mul(ans[r][i], tmp);
  97.             }
  98.         }
  99.         for (ul i = 1; i <= n; ++i) {
  100.             if (i != 1) {
  101.                 oss << ' ';
  102.             }
  103.             oss << ans[n][i];
  104.         }
  105.         oss << '\n';
  106.     }
  107.     std::cout << oss.str();
  108.     return 0;
  109. }

I、Paperfolding 6822

倒着考虑，每当上下展开的时候，行数变为原先两倍减一，每当左右展开的时候，列数变为原先两倍减一。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul mod = 998244353;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + mod - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % mod;
  27. }
  29. void exgcd(li a, li b, li& x, li& y)
  30. {
  31.     if (b) {
  32.         exgcd(b, a % b, y, x);
  33.         y -= a / b * x;
  34.     } else {
  35.         x = 1;
  36.         y = 0;
  37.     }
  38. }
  40. ul inverse(ul a)
  41. {
  42.     li x, y;
  43.     exgcd(a, mod, x, y);
  44.     return x < 0 ? x + li(mod) : x;
  45. }
  47. ul pow(ul a, ul b)
  48. {
  49.     ul ret = 1;
  50.     while (b) {
  51.         if (b & 1) {
  52.             ret = mul(ret, a);
  53.         }
  54.         a = mul(a, a);
  55.         b >>= 1;
  56.     }
  57.     return ret;
  58. }
  60. ul inv2 = inverse(2);
  62. ul T;
  63. ull n;
  65. int main()
  66. {
  67.     std::ios::sync_with_stdio(false);
  68.     std::cin.tie(0);
  69.     iss.tie(0);
  70.     oss.tie(0);
  71.     std::getline(std::cin, instr, char(0));
  72.     iss.str(instr);
  73.     iss >> T;
  74.     for (ul Case = 1; Case <= T; ++Case) {
  75.         iss >> n;
  76.         n %= mod - 1;
  77.         oss << plus(plus(pow(2, ul(n)), mul(mul(pow(3, ul(n)), 2), pow(inv2, ul(n)))), 1) << '\n';
  78.     }
  79.     std::cout << oss.str();
  80.     return 0;
  81. }

J、Function 6823

题意实际就是要求作为的线性变换，其若当型中所有若当块形如。
于是构造就很容易了。关键是检查，检查详细步骤会在代码中注释出来，关于此检查步骤的必要性和充分性请自己证明。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T;
  13. ul n, m;
  14. const ul maxd = 60;
  15. const ul maxm = 2e5;
  17. std::vector<ull> base;
  19. char op[20];
  21. char so[40];
  23. class xy {
  24. public:
  25.     ull x = 0;
  26.     ll y = 0;
  27. };
  29. std::vector<xy> base2;
  30. std::vector<xy> base3;
  32. xy s;
  34. std::vector<ull> tmp;
  35. std::vector<ull> base4;
  37. int main()
  38. {
  39.     std::ios::sync_with_stdio(false);
  40.     std::cin.tie(0);
  41.     iss.tie(0);
  42.     oss.tie(0);
  43.     std::getline(std::cin, instr, char(0));
  44.     iss.str(instr);
  45.     iss >> T;
  46.     for (ul Case = 1; Case <= T; ++Case) {
  47.         iss >> n;
  48.         base.resize(0);
  49.         for (ul i = 1; i <= n; ++i) {
  50.             ull a;
  51.             iss >> a;
  52.             for (auto v : base) {
  53.                 a = std::min(a, a ^ v);
  54.             }
  55.             if (a) {
  56.                 base.push_back(a);
  57.             }
  58.         }
  59.         iss >> op + 1;
  60.         if (op[2] == 'o') {
  61.             if (base.size() & 1) {
  62.                 oss << "NoSolution\n";
  63.                 iss >> m;
  64.                 for (ul c = 1; c <= m; ++c) {
  65.                     ull x;
  66.                     iss >> x;
  67.                 }
  68.                 continue;
  69.             } else {
  70.                 oss << "HaveSolution\n";
  71.                 iss >> m;
  72.                 ul t = base.size() >> 1;
  73.                 for (ul c = 1; c <= m; ++c) {
  74.                     ull x;
  75.                     ull y = 0;
  76.                     iss >> x;
  77.                     for (ul i = 0; i != t; ++i) {
  78.                         if ((x ^ base[i]) < x) {
  79.                             x ^= base[i];
  80.                             y ^= base[i + t];
  81.                         }
  82.                     }
  83.                     for (ul i = t; i != base.size(); ++i) {
  84.                         x = std::min(x, x ^ base[i]);
  85.                     }
  86.                     if (x) {
  87.                         oss << "-1\n";
  88.                     } else {
  89.                         oss << y << '\n';
  90.                     }
  91.                 }
  92.             }
  93.         } else {
  94.             iss >> so + 1;
  95.             if (base.size() & 1) {//如果S(a)维度为奇数，显然不可行
  96.                 if (so[1] == 'N') {
  97.                     oss << "Yes\n";
  98.                     continue;
  99.                 } else {
  100.                     oss << "No\n";
  101.                     iss >> m;
  102.                     for (ul c = 1; c <= m; ++c) {
  103.                         ull x;
  104.                         ll y;
  105.                         iss >> x >> y;
  106.                     }
  107.                     continue;
  108.                 }
  109.             } else {
  110.                 if (so[1] == 'N') {//如果维度为偶数，显然可行
  111.                     oss << "No\n";
  112.                     continue;
  113.                 } else {
  114.                     iss >> m;
  115.                     ul t = base.size() >> 1;
  116.                     bool flag = true;
  117.                     base2.resize(0);
  118.                     for (ul c = 1; c <= m; ++c) {
  119.                         iss >> s.x >> s.y;
  120.                         if (!flag) {
  121.                             continue;
  122.                         }
  123.                         if (s.y == -1) {//确认x是不是确实在S(a)外
  124.                             for (auto v : base) {
  125.                                 s.x = std::min(s.x ^ v, s.x);
  126.                             }
  127.                             if (s.x == 0) {
  128.                                 flag = false;
  129.                             }
  130.                             continue;
  131.                         }
  132.                         for (const auto& v : base2) {//保证不丢失信息的情况下，检查f的线性性
  133.                             if ((s.x ^ v.x) < s.x) {
  134.                                 s.x ^= v.x;
  135.                                 s.y ^= v.y;
  136.                             }
  137.                         }
  138.                         if (s.x == 0 && s.y != 0) {
  139.                             flag = false;
  140.                             continue;
  141.                         }
  142.                         if (s.x) {
  143.                             base2.push_back(s);
  144.                         }
  145.                     }
  146.                     if (!flag) {
  147.                         oss << "No\n";
  148.                         continue;
  149.                     }
  150.                     for (auto s : base2) {//检查是否所有插值点的输入和输出都在S(a)中
  151.                         for (auto v : base) {
  152.                             s.x = std::min(s.x, s.x ^ v);
  153.                         }
  154.                         for (auto v : base) {
  155.                             s.y = std::min(ull(s.y), s.y ^ v);
  156.                         }
  157.                         if (s.x || s.y) {
  158.                             flag = false;
  159.                             break;
  160.                         }
  161.                     }
  162.                     if (!flag) {
  163.                         oss << "No\n";
  164.                         continue;
  165.                     }
  166.                     base3.resize(0);
  167.                     tmp.resize(0);
  168.                     for (auto s : base2) {//在不丢失信息的情况下，求出y所张成的子空间（也就是插值点间接提供的核子空间，由于要求f(y)=0），并确认插值点直接提供的核子空间
  169.                         for (auto v : base3) {
  170.                             if ((s.y ^ v.y) < s.y) {
  171.                                 s.y ^= v.y;
  172.                                 s.x ^= v.x;
  173.                             }
  174.                         }
  175.                         if (s.y) {
  176.                             base3.push_back(s);
  177.                         } else {
  178.                             tmp.push_back(s.x);
  179.                         }
  180.                     }
  181.                     base4.resize(0);
  182.                     for (auto s : base3) {//接下来两个for将使得base4就是插值点直接以及间接给出的核子空间
  183.                         base4.push_back(s.y);
  184.                     }
  185.                     for (auto s : tmp) {
  186.                         for (auto v : base4) {
  187.                             s = std::min(s, s ^ v);
  188.                         }
  189.                         if (s) {
  190.                             base4.push_back(s);
  191.                         }
  192.                     }
  193.                     if (base4.size() * 2 > base.size()) {//如果核子空间的维度大于了S(a)维度的一半，肯定不行
  194.                         flag = false;
  195.                     }
  196.                     if (!flag) {
  197.                         oss << "No\n";
  198.                         continue;
  199.                     }
  200.                     for (auto s : base3) {//最后，再检查那些x和y是否独立（这是关键要完成的证明，必要性就是说明这些如果不独立则肯定不行，充分性就是说明这些如果独立就一定能张出合适的f）
  201.                         for (auto v : base4) {
  202.                             s.x = std::min(s.x, s.x ^ v);
  203.                         }
  204.                         if (s.x) {
  205.                             base4.push_back(s.x);
  206.                         } else {
  207.                             flag = false;
  208.                             break;
  209.                         }
  210.                     }
  211.                     if (!flag) {
  212.                         oss << "No\n";
  213.                         continue;
  214.                     }
  215.                     oss << "Yes\n";
  216.                 }
  217.             }
  218.         }
  219.     }
  220.     std::cout << oss.str();
  221.     return 0;
  222. }

K、Exam 6824

2SAT，线段树建图

  1. #include <bits/stdc++.h>
  3. namespace fast_pool {
  4.     constexpr size_t const size = 481 << 20;
  5.     unsigned char data[size];
  6.     unsigned char* ptr = data;
  7.     void clear() {ptr = data;}
  8.     void* fast_alloc(size_t n) {ptr += n; return ptr - n;}
  9. };
  11. template<class T>
  12. class myallocator {
  13. public:
  14.     typedef T value_type;
  15.     typedef value_type* pointer;
  16.     typedef value_type& reference;
  17.     typedef value_type const* const_pointer;
  18.     typedef value_type const& const_reference;
  19.     typedef size_t size_type;
  20.     typedef ptrdiff_t difference_type;
  21.     pointer allocate(size_t n, const T* pHint = 0) {
  22.         return (pointer)(fast_pool::fast_alloc(n * sizeof(T)));
  23.     }
  24.     void deallocate(pointer p, size_type n) {}
  25.     void destroy(T* p) {p->~T();}
  26.     void construct(T* p, const T& val) {::new((void *)p) T(val);}
  27.     size_t max_size() const throw() {
  28.         return (fast_pool::size + fast_pool::data - fast_pool::ptr) / sizeof(T);
  29.     }
  30.     T* address(T& val) const {return &val;}
  31.     const T* address(const T& val) const {return &val;}
  32.     myallocator() throw() {}
  33.     myallocator(const T* p) throw() {}
  34.     ~myallocator() throw() {}
  35.     template <typename _other> struct rebind { typedef myallocator<_other> other; };
  36. };
  38. std::stringstream iss;
  39. std::stringstream oss;
  40. std::string instr;
  42. using ul = std::uint32_t;
  43. using li = std::int32_t;
  44. using ull = std::uint64_t;
  45. using ll = std::int64_t;
  47. ul T;
  48. ul n;
  50. const ul maxn = 25000;
  52. class seg_t {
  53. public:
  54.     ul l = 0;
  55.     ul r = 0;
  56.     seg_t()=default;
  57. };
  59. class exam_t {
  60. public:
  61.     seg_t a;
  62.     seg_t b;
  63.     exam_t()=default;
  64. };
  66. exam_t exam[maxn + 1];
  68. std::pair<seg_t, ul> props[maxn * 2 + 1];
  70. const ul maxsz = 1 << 16;
  72. ul sz;
  74. ul cnt;
  76. ul down[maxsz << 1];
  77. ul up[maxsz << 1];
  79. std::vector<ul, myallocator<ul>> edges[199959];
  81. void addedge(ul l, ul r, ul pid)
  82. {
  83.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  84.         if (~l & 1) {
  85.             edges[up[l ^ 1]].push_back(pid * 2);
  86.             edges[pid * 2 - 1].push_back(down[l ^ 1]);
  87.         }
  88.         if (r & 1) {
  89.             edges[up[r ^ 1]].push_back(pid * 2);
  90.             edges[pid * 2 - 1].push_back(down[r ^ 1]);
  91.         }
  92.     }
  93. }
  95. ul low[199959];
  96. ul dfn[199959];
  97. std::vector<ul, myallocator<ul>> stack(199958);
  98. std::vector<bool> instack(199959);
  100. ul tim;
  101. void search(ul v, const std::vector<ul, myallocator<ul>> edges[], std::vector<std::vector<ul, myallocator<ul>>, myallocator<std::vector<ul, myallocator<ul>>>>& sccs)
  102. {
  103.     low[v] = dfn[v] = ++tim;
  104.     stack.push_back(v);
  105.     instack[v] = true;
  106.     for (ul w : edges[v]) {
  107.         if (!dfn[w]) {
  108.             search(w, edges, sccs);
  109.             low[v] = std::min(low[v], low[w]);
  110.         } else if (dfn[w] < dfn[v]) {
  111.             if (instack[w]) {
  112.                 low[v] = std::min(low[v], dfn[w]);
  113.             }
  114.         }
  115.     }
  116.     if (low[v] == dfn[v]) {
  117.         sccs.push_back(std::vector<ul, myallocator<ul>>());
  118.         while (stack.size() && dfn[stack.back()] >= dfn[v]) {
  119.             instack[stack.back()] = false;
  120.             sccs.back().push_back(stack.back());
  121.             stack.pop_back();
  122.         }
  123.     }
  124. }
  126. void scc(const std::vector<ul, myallocator<ul>> edges[], ul sz, std::vector<std::vector<ul, myallocator<ul>>, myallocator<std::vector<ul, myallocator<ul>>>>& sccs)
  127. {
  128.     sccs.resize(0);
  129.     tim = 0;
  130.     stack.resize(0);
  131.     instack.resize(0);
  132.     instack.resize(sz + 1, false);
  133.     std::memset(dfn + 1, 0, sz * sizeof(ul));
  134.     for (ul w = 1; w <= sz; ++w) {
  135.         if (!dfn[w]) {
  136.             search(w, edges, sccs);
  137.         }
  138.     }
  139. }
  141. std::vector<std::vector<ul, myallocator<ul>>, myallocator<std::vector<ul, myallocator<ul>>>> sccs;
  143. ul already[maxn + maxn + maxn + maxn + 1];
  144. ul altim = 0;
  146. int main()
  147. {
  148.     std::ios::sync_with_stdio(false);
  149.     std::cin.tie(0);
  150.     iss.tie(0);
  151.     oss.tie(0);
  152.     std::getline(std::cin, instr, char(0));
  153.     iss.str(instr);
  154.     iss >> T;
  155.     for (ul Case = 1; Case <= T; ++Case) {
  156.         iss >> n;
  157.         ul mx = 0, mn = 0;
  158.         for (ul i = 1; i <= n; ++i)  {
  159.             iss >> exam[i].a.l >> exam[i].a.r >> exam[i].b.l >> exam[i].b.r;
  160.             exam[i].a.r += exam[i].a.l;
  161.             exam[i].b.r += exam[i].b.l;
  162.             mx = std::max(mx, std::max(exam[i].a.r, exam[i].b.r));
  163.             mn = std::max(mn, std::min(exam[i].a.r, exam[i].b.r));
  164.             props[i * 2 - 1] = std::pair<seg_t, ul>(exam[i].a, i * 2 - 1);
  165.             props[i * 2] = std::pair<seg_t, ul>(exam[i].b, i * 2);
  166.         }
  167.         std::sort(props + 1, props + 2 * n + 1, [](const std::pair<seg_t, ul>& a, const std::pair<seg_t, ul>& b){return a.first.l < b.first.l;});
  168.         sz = 1;
  169.         ul lgsz = 0;
  170.         while (n * 2 + 2 > sz) {
  171.             sz <<= 1;
  172.             ++lgsz;
  173.         }
  174.         cnt = n * 4;
  175.         std::memset(down, 0, (sz << 1) * sizeof(ul));
  176.         std::memset(up, 0, (sz << 1) * sizeof(ul));
  177.         for (ul depth = 0; (1 << depth) < sz; ++depth) {
  178.             for (ul i = 0; i != (1 << depth); ++i) {
  179.                 ul l = i << lgsz - depth;
  180.                 ul r = (i + 1 << lgsz - depth) - 1;
  181.                 if (l < 1 || r > 2 * n) {
  182.                     continue;
  183.                 }
  184.                 ++cnt;
  185.                 down[1 << depth | i] = cnt;
  186.                 ++cnt;
  187.                 up[1 << depth | i] = cnt;
  188.             }
  189.         }
  190.         for (ul i = 1; i <= n + n; ++i) {
  191.             down[sz | i] = props[i].second * 2;
  192.             up[sz | i] = props[i].second * 2 - 1;
  193.         }
  194.         for (ul i = 1; i <= cnt; ++i) {
  195.             edges[i].resize(0);
  196.         }
  197.         for (ul i = 1; i <= n; ++i) {
  198.             edges[i * 4 - 2].push_back(i * 4 - 1);
  199.             edges[i * 4].push_back(i * 4 - 3);
  200.         }
  201.         for (ul i = 1; i != sz; ++i) {
  202.             if (!down[i]) {
  203.                 continue;
  204.             }
  205.             edges[down[i]].push_back(down[i << 1]);
  206.             edges[down[i]].push_back(down[i << 1 | 1]);
  207.             edges[up[i << 1]].push_back(up[i]);
  208.             edges[up[i << 1 | 1]].push_back(up[i]);
  209.         }
  210.         for (ul i = 1; i <= n + n; ++i) {
  211.             ul it1 = std::lower_bound(props + 1, props + i, props[i], [](const std::pair<seg_t, ul>& a, const std::pair<seg_t, ul>& b){return a.first.l < b.first.l;}) - props;
  212.             auto tmp = props[i];
  213.             tmp.first.l = tmp.first.r;
  214.             ul it2 = std::upper_bound(props + i + 1, props + n + n + 1, tmp, [](const std::pair<seg_t, ul>& a, const std::pair<seg_t, ul>& b){return a.first.l < b.first.l;}) - props - 1;
  215.             addedge(it1, i - 1, props[i].second);
  216.             addedge(i + 1, it2, props[i].second);
  217.         }
  218.         ul l = mn - 1, r = mx + 1;
  219.         while (l + 1 != r) {
  220.             ul mid = l + r >> 1;
  221.             for (ul i = 1; i <= n + n; ++i) {
  222.                 if (props[i].first.r > mid) {
  223.                     edges[props[i].second * 2 - 1].push_back(props[i].second * 2);
  224.                 }
  225.             }
  226.             scc(edges, cnt, sccs);
  227.             bool flag = true;
  228.             for (auto& scc : sccs) {
  229.                 ++altim;
  230.                 for (auto v : scc) {
  231.                     if (v > n * 4) {
  232.                         continue;
  233.                     }
  234.                     if ((v & 1) && already[v + 1] == altim || (~v & 1) && already[v - 1] == altim) {
  235.                         flag = false;
  236.                         break;
  237.                     }
  238.                     already[v] = altim;
  239.                 }
  240.                 if (!flag) {
  241.                     break;
  242.                 }
  243.             }
  244.             if (flag) {
  245.                 r = mid;
  246.             } else {
  247.                 l = mid;
  248.             }
  249.             for (ul i = 1; i <= n + n; ++i) {
  250.                 if (props[i].first.r > mid) {
  251.                     edges[props[i].second * 2 - 1].pop_back();
  252.                 }
  253.             }
  254.         }
  255.         oss << (r != mx + 1 ? li(r) : li(-1)) << '\n';
  256.     }
  257.     std::cout << oss.str();
  258.     return 0;
  259. }

L、Set1 6825

官方题解如下：
无标题2.png-83.6kB
注意，图片中少除以了一样东西，很容易看出来。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T;
  13. ul n;
  15. const ul mod = 998244353;
  17. ul plus(ul a, ul b)
  18. {
  19.     return a + b < mod ? a + b : a + b - mod;
  20. }
  22. ul mul(ul a, ul b)
  23. {
  24.     return ull(a) * ull(b) % mod;
  25. }
  27. void exgcd(li a, li b, li& x, li& y)
  28. {
  29.     if (b) {
  30.         exgcd(b, a % b, y, x);
  31.         y -= a / b * x;
  32.     } else {
  33.         x = 1;
  34.         y = 0;
  35.     }
  36. }
  38. ul inverse(ul a)
  39. {
  40.     li x, y;
  41.     exgcd(a, mod, x, y);
  42.     return x < 0 ? x + li(mod) : x;
  43. }
  45. const ul maxn = 5e6;
  47. ul fac[maxn + 1];
  48. ul fiv[maxn + 1];
  49. ul twopow[maxn + 1];
  50. ul twopowinv[maxn + 1];
  52. int main()
  53. {
  54.     std::ios::sync_with_stdio(false);
  55.     std::cin.tie(0);
  56.     iss.tie(0);
  57.     oss.tie(0);
  58.     std::getline(std::cin, instr, char(0));
  59.     iss.str(instr);
  60.     fac[0] = 1;
  61.     twopow[0] = 1;
  62.     for (ul i = 1; i <= maxn; ++i) {
  63.         fac[i] = mul(fac[i - 1], i);
  64.         twopow[i] = plus(twopow[i - 1], twopow[i - 1]);
  65.     }
  66.     fiv[maxn] = inverse(fac[maxn]);
  67.     twopowinv[maxn] = inverse(twopow[maxn]);
  68.     for (ul i = maxn; i >= 1; --i) {
  69.         fiv[i - 1] = mul(fiv[i], i);
  70.         twopowinv[i - 1] = plus(twopowinv[i], twopowinv[i]);
  71.     }
  72.     iss >> T;
  73.     for (ul Case = 1; Case <= T; ++Case) {
  74.         iss >> n;
  75.         ul lambda = mul(fiv[n >> 1], twopowinv[n >> 1]);
  76.         ul sum = 0;
  77.         for (ul i = 1; i <= n; ++i) {
  78.             if (i != 1) {
  79.                 oss << ' ';
  80.             }
  81.             if (n - i > i - 1) {
  82.                 oss << '0';
  83.                 continue;
  84.             }
  85.             oss << mul(mul(mul(fac[i - 1], twopowinv[i - (n + 1 >> 1)]), fiv[i - (n + 1 >> 1)]), lambda);
  86.         }
  87.         oss << '\n';
  88.     }
  89.     std::cout << oss.str();
  90.     return 0;
  91. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注