[关闭]
@qq290637843 2020-12-21T14:23:30.000000Z 字数 21363 阅读 291

2020杭电第三场

A、Tokitsukaze, CSL and Palindrome Game 6791

先考虑对一个字符串，要出现的期望步数问题。将第一次出现时，的长度记为随机变量。
设，设。于是显然，期望值等于。
现在考虑“的长为的前缀中没有出现，而的到这个子串正好是”这一事件。其概率显然为。现在考虑在此中，第一次出现的位置的尾部的下标。于是必定满足（将记为），故上述引号中事件的概率还可以描述为：

于是
于是
于是

根据以上结论，直接在回文树上比较即可。

  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 uss = std::uint8_t;
  13. const ul maxn = 1e5;
  15. class pam_t {
  16. public:
  17.     ul las;
  18.     class node {
  19.     public:
  20.         ul ch[26];
  21.         ul len = 0;
  22.         ul fa = 0;
  23.         node()=default;
  24.         node(ul a, ul b): len(a), fa(b) {
  25.             std::memset(ch, 0, sizeof(ch));
  26.         }
  27.     };
  28.     std::vector<node> st = std::vector<node>(maxn + 2);
  29.     std::vector<uss> str = std::vector<uss>(maxn + 1);
  30.     ul newnode(ul len, ul fail = 0) {
  31.         st.push_back(node(len, fail));
  32.         return st.size() - 1;
  33.     }
  34.     ul getfail(ul x, ul n) {
  35.         while (str[n - st[x].len - 1] != str[n]) {
  36.             x = st[x].fa;
  37.         }
  38.         return x;
  39.     }
  40.     bool add(ul c) {
  41.         ul i = str.size();
  42.         str.push_back(c);
  43.         ul cur = getfail(las, i);
  44.         bool flag = false;
  45.         if (!st[cur].ch[c]) {
  46.             ul nw = newnode(st[cur].len + 2, st[getfail(st[cur].fa, i)].ch[c]);
  47.             st[cur].ch[c] = nw;
  48.             flag = true;
  49.         }
  50.         las = st[cur].ch[c];
  51.         return flag;
  52.     }
  53.     void init() {
  54.         str.resize(0);
  55.         str.resize(1, 26);
  56.         st.resize(0);
  57.         newnode(0, 1);
  58.         newnode(-1, 0);
  59.         las = 0;
  60.     }
  61. };
  63. ul las[maxn + 1];
  65. pam_t pam;
  67. ul T;
  68. ul n;
  70. char s[maxn + 2];
  72. ul head[maxn + 2];
  74. using pulul = std::pair<ul, ul>;
  76. void getlen(ul l, ul r, std::vector<pulul>& v)
  77. {
  78.     v.resize(0);
  79.     ul cur = las[r];
  80.     while (pam.st[head[cur]].len > r - l + 1) {
  81.         cur = pam.st[head[cur]].fa;
  82.     }
  83.     v.push_back(pulul(r - l + 1, pam.st[cur].len - pam.st[pam.st[cur].fa].len));
  84.     cur = pam.st[head[cur]].fa;
  85.     while (cur) {
  86.         v.push_back(pulul(pam.st[cur].len, pam.st[cur].len - pam.st[pam.st[cur].fa].len));
  87.         cur = pam.st[head[cur]].fa;
  88.     }
  89. }
  91. std::vector<pulul> vs[2];
  93. int main()
  94. {
  95.     std::ios::sync_with_stdio(false);
  96.     std::cin.tie(0);
  97.     iss.tie(0);
  98.     oss.tie(0);
  99.     std::getline(std::cin, instr, char(0));
  100.     iss.str(instr);
  101.     iss >> T;
  102.     for (ul Case = 1; Case <= T; ++Case) {
  103.         iss >> n >> s + 1;
  104.         pam.init();
  105.         for (ul i = 1; i <= n; ++i) {
  106.             pam.add(s[i] - 'a');
  107.             las[i] = pam.las;
  108.         }
  109.         for (ul i = 2; i != pam.st.size(); ++i) {
  110.             if (!pam.st[i].fa || pam.st[i].len + pam.st[pam.st[pam.st[i].fa].fa].len != (pam.st[pam.st[i].fa].len << 1)) {
  111.                 head[i] = i;
  112.             } else {
  113.                 head[i] = head[pam.st[i].fa];
  114.             }
  115.         }
  116.         ul q;
  117.         iss >> q;
  118.         for (ul t = 1; t <= q; ++t) {
  119.             ul a, b, c, d;
  120.             iss >> a >> b >> c >> d;
  121.             if (b - a != d - c) {
  122.                 oss << (d - c > b - a ? "sjfnb\n" : "cslnb\n");
  123.                 continue;
  124.             }
  125.             getlen(a, b, vs[0]);
  126.             getlen(c, d, vs[1]);
  127.             bool flag = false;
  128.             for (ul i = 0; i != vs[0].size() && i != vs[1].size(); ++i) {
  129.                 if (vs[0][i].first != vs[1][i].first) {
  130.                     oss << (vs[0][i].first > vs[1][i].first ? "cslnb\n" : "sjfnb\n");
  131.                     flag = true;
  132.                     break;
  133.                 }
  134.                 if (vs[0][i].second != vs[1][i].second) {
  135.                     oss << (vs[0][i].second < vs[1][i].second ? "cslnb\n" : "sjfnb\n");
  136.                     flag = true;
  137.                     break;
  138.                 }
  139.             }
  140.             if (!flag) {
  141.                 oss << "draw\n";
  142.             }
  143.         }
  144.     }
  145.     std::cout << oss.str();
  146.     return 0;
  147. }

C、Tokitsukaze and Colorful Tree 6793

官方题解如下：
image.png-173kB

  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;
  14. class changer {
  15. public:
  16.     ul time = 0;
  17.     li change = 0;
  18.     ul val = 0;
  19.     ul nid = 0;
  20.     changer()=default;
  21.     changer(ul a, li b, ul c, ul d): time(a), change(b), val(c), nid(d) {}
  22. };
  24. const ul maxn = 1e5;
  26. std::vector<changer> changes[maxn + 1];
  28. ul n;
  30. ul col[maxn + 1];
  31. ul val[maxn + 1];
  33. const ul maxq = 1e5;
  35. ul q;
  37. std::vector<ul> edges[maxn + 1];
  39. ll ans[maxq + 2];
  41. ul ldfn[maxn + 1];
  42. ul rdfn[maxn + 1];
  44. ul tim = 0;
  45. void search(ul curr, ul prev)
  46. {
  47.     ++tim;
  48.     ldfn[curr] = tim;
  49.     for (ul next : edges[curr]) {
  50.         if (next == prev) {
  51.             continue;
  52.         }
  53.         search(next, curr);
  54.     }
  55.     rdfn[curr] = tim;
  56. }
  58. li cnt[2];
  60. const ul sz = 1 << 17;
  62. li treeup[2][sz << 1];
  63. li treedown[2][sz << 1];
  65. void insert(ul l, ul r, li v, li tree[])
  66. {
  67.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  68.         if (~l & 1) {
  69.             tree[l ^ 1] += v;
  70.         }
  71.         if (r & 1) {
  72.             tree[r ^ 1] += v;
  73.         }
  74.     }
  75. }
  77. li query(ul l, ul r, const li tree[])
  78. {
  79.     li ret = 0;
  80.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  81.         if (~l & 1) {
  82.             ret += tree[l ^ 1];
  83.         }
  84.         if (r & 1) {
  85.             ret += tree[r ^ 1];
  86.         }
  87.     }
  88.     return ret;
  89. }
  91. void insert(ul pos, li v, li tree[])
  92. {
  93.     for (tree[pos |= sz] += v, pos >>= 1; pos; pos >>= 1) {
  94.         tree[pos] += v;
  95.     }
  96. }
  98. li query(ul pos, const li tree[])
  99. {
  100.     li ret = tree[pos |= sz];
  101.     for (pos >>= 1; pos; pos >>= 1) {
  102.         ret += tree[pos];
  103.     }
  104.     return ret;
  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;
  118.         for (ul i = 1; i <= n; ++i) {
  119.             edges[i].resize(0);
  120.             iss >> col[i];
  121.         }
  122.         for (ul i = 1; i <= n; ++i) {
  123.             iss >> val[i];
  124.             changes[col[i]].push_back(changer(0, 1, val[i], i));
  125.         }
  126.         for (ul i = 1; i <= n - 1; ++i) {
  127.             ul u, v;
  128.             iss >> u >> v;
  129.             edges[u].push_back(v);
  130.             edges[v].push_back(u);
  131.         }
  132.         iss >> q;
  133.         for (ul t = 1; t <= q; ++t) {
  134.             ul a, b, c;
  135.             iss >> a >> b >> c;
  136.             changes[col[b]].push_back(changer(t, -1, val[b], b));
  137.             if (a == 1) {
  138.                 val[b] = c;
  139.             } else {
  140.                 col[b] = c;
  141.             }
  142.             changes[col[b]].push_back(changer(t, 1, val[b], b));
  143.         }
  144.         for (ul i = 1; i <= q + 1; ++i) {
  145.             ans[i] = 0;
  146.         }
  147.         tim = 0;
  148.         search(1, 0);
  149.         for (ul c = 1; c <= n; ++c) {
  150.             for (ul it = 0; it != 20; ++it) {
  151.                 for (const auto& change : changes[c]) {
  152.                     ul type = change.val >> it & 1;
  153.                     ans[change.time + 1] += ll(change.change) * (ll(cnt[type ^ 1]) << it);
  154.                     ans[change.time + 1] -= ll(change.change) * (ll(query(ldfn[change.nid] + 1, rdfn[change.nid], treeup[type ^ 1])) << it);
  155.                     ans[change.time + 1] -= ll(change.change) * (ll(query(ldfn[change.nid], treedown[type ^ 1])) << it);
  156.                     cnt[type] += change.change;
  157.                     insert(ldfn[change.nid], change.change, treeup[type]);
  158.                     insert(ldfn[change.nid] + 1, rdfn[change.nid], change.change, treedown[type]);
  159.                 }
  160.                 for (const auto& change : changes[c]) {
  161.                     ul type = change.val >> it & 1;
  162.                     cnt[type] -= change.change;
  163.                     insert(ldfn[change.nid], -change.change, treeup[type]);
  164.                     insert(ldfn[change.nid] + 1, rdfn[change.nid], -change.change, treedown[type]);
  165.                 }
  166.             }
  167.             changes[c].resize(0);
  168.         }
  169.         for (ul i = 1; i <= q; ++i) {
  170.             ans[i + 1] += ans[i];
  171.         }
  172.         for (ul i = 1; i <= q + 1; ++i) {
  173.             oss << ans[i] << '\n';
  174.         }
  175.     }
  176.     std::cout << oss.str();
  177.     return 0;
  178. }

D、Tokitsukaze and Multiple 6794

简单题

  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;
  14. ul n, p;
  16. ul a;
  18. const ul maxn = 1e5;
  20. ul sa[maxn + 1];
  22. const ul maxp = 1e5;
  24. li ans[maxp];
  26. int main()
  27. {
  28.     std::ios::sync_with_stdio(false);
  29.     std::cin.tie(0);
  30.     iss.tie(0);
  31.     oss.tie(0);
  32.     std::getline(std::cin, instr, char(0));
  33.     iss.str(instr);
  34.     for (ul i = 1; i != maxp; ++i) {
  35.         ans[i] = -1e9;
  36.     }
  37.     iss >> T;
  38.     for (ul Case = 1; Case <= T; ++Case) {
  39.         iss >> n >> p;
  40.         sa[0] = 0;
  41.         ans[0] = 0;
  42.         for (ul i = 1; i <= n; ++i) {
  43.             iss >> a;
  44.             sa[i] = (a + sa[i - 1]) % p;
  45.             ans[sa[i]] = std::max(ans[sa[i]] + 1, ans[sa[i - 1]]);
  46.         }
  47.         oss << ans[sa[n]] << '\n';
  48.         for (ul i = 1; i <= n; ++i) {
  49.             ans[sa[i]] = -1e9;
  50.         }
  51.     }
  52.     std::cout << oss.str();
  53.     return 0;
  54. }

E、Little W and Contest 6795

简单题

  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;
  14. ul n;
  16. const ul maxn = 1e5;
  18. ul fa[maxn + 1];
  20. ul rk[maxn + 1];
  22. ull cnt[maxn + 1][2];
  24. ull c[3];
  26. ull ans;
  28. ull bi2(ull a)
  29. {
  30.     return a * (a - 1) >> 1;
  31. }
  33. ull bi3(ull a)
  34. {
  35.     return a * (a - 1) * (a - 2) / 6;
  36. }
  38. ul getfather(ul a)
  39. {
  40.     return a == fa[a] ? a : fa[a] = getfather(fa[a]);
  41. }
  43. void connect(ul a, ul b)
  44. {
  45.     if (rk[a] < rk[b]) {
  46.         std::swap(a, b);
  47.     }
  48.     fa[b] = a;
  49.     cnt[a][3] += cnt[b][4];
  50.     cnt[a][5] += cnt[b][6];
  51.     if (rk[a] == rk[b]) {
  52.         ++rk[a];
  53.     }
  54. }
  56. int main()
  57. {
  58.     std::ios::sync_with_stdio(false);
  59.     std::cin.tie(0);
  60.     iss.tie(0);
  61.     oss.tie(0);
  62.     std::getline(std::cin, instr, char(0));
  63.     iss.str(instr);
  64.     iss >> T;
  65.     for (ul Case = 1; Case <= T; ++Case) {
  66.         iss >> n;
  67.         c[1] = c[2] = 0;
  68.         for (ul i = 1; i <= n; ++i) {
  69.             rk[i] = 0;
  70.             fa[i] = i;
  71.             ul tmp;
  72.             iss >> tmp;
  73.             cnt[i][3 ^ tmp] = 0;
  74.             cnt[i][tmp] = 1;
  75.             ++c[tmp];
  76.         }
  77.         ans = bi2(c[2]) * c[1] + bi3(c[2]);
  78.         oss << ans % ul(1e9 + 7) << '\n';
  79.         for (ul i = 1; i <= n - 1; ++i) {
  80.             ul u, v;
  81.             iss >> u >> v;
  82.             u = getfather(u);
  83.             v = getfather(v);
  84.             ans -= cnt[u][7] * cnt[v][8] * (c[2] - cnt[u][9] - cnt[v][10]) + cnt[u][11] * cnt[v][12] * (c[2] - cnt[u][13] - cnt[v][14]) + cnt[u][15] * cnt[v][16] * (c[1] - cnt[u][17] - cnt[v][18]) + cnt[u][19] * cnt[v][20] * (c[2] - cnt[u][21] - cnt[v][22]);
  85.             connect(u, v);
  86.             oss << ans % ul(1e9 + 7) << '\n';
  87.         }
  88.     }
  89.     std::cout << oss.str();
  90.     return 0;
  91. }

F、X Number 6796

直接看代码吧，其中的排列组合说明非常复杂。

  1. #pragma GCC target ("pclmul")
  2. #include <bits/stdc++.h>
  3. #include <emmintrin.h>
  4. #include <wmmintrin.h>
  6. std::stringstream iss;
  7. std::stringstream oss;
  8. std::string instr;
  10. using ul = std::uint32_t;
  11. using ull = std::uint64_t;
  12. using li = std::int32_t;
  13. using ll = std::int64_t;
  15. inline ul mul(ul a, ul b) {
  16.     auto vc = _mm_clmulepi64_si128(_mm_cvtsi32_si128(a), _mm_cvtsi32_si128(b), 0);
  17.     auto vf = _mm_xor_si128(vc, _mm_clmulepi64_si128(_mm_srli_epi64(vc, 32), _mm_set_epi32(0, 0, 1, 141), 0));
  18.     return _mm_cvtsi128_si32(_mm_xor_si128(vf, _mm_clmulepi64_si128(_mm_srli_epi64(vf, 32), _mm_set_epi32(0, 0, 1, 141), 0)));
  19. }
  21. ul x, y;
  23. std::mt19937 rnd;
  25. ull n;
  27. ul a[10];
  28. ul b[10];
  30. ull fac[20];
  32. std::unordered_map<ul, ull> subans;
  34. ul cntb[20];
  35. ul cntb3[20];
  37. ul cntamb[20];
  39. ul cntambb[20][23];
  41. ull l, r;
  43. ull bi(ul a, ul b)
  44. {
  45.     return fac[a] / fac[b] / fac[a - b];
  46. }
  48. void search2(ul i, ul nct, ul sum, ull prod, ul hash, ul t1, ul t2, ul t3, ul cnt)
  49. {
  50.     if (i > nct) {
  51.         hash = mul(mul(hash, x) ^ a[0] - b[0], x) ^ sum;
  52.         ull tmp1 = fac[sum] / prod;
  53.         for (ul i = 1; i <= 19; ++i) {
  54.             tmp1 /= fac[cntb[i]];
  55.         }
  56.         ull tmp2 = bi(9 - t1 - t3, t2);
  57.         ull tmp3 = 1;
  58.         if (b[0]) {
  59.             tmp3 *= bi(cntb[b[0]], 1);
  60.         }
  61.         for (ul i = 1; i <= 19; ++i) {
  62.             tmp3 *= bi(cntb[i] - (b[0] == i), cntb3[i]) * fac[cntb3[i]];
  63.         }
  64.         ull tmp4 = fac[t2];
  65.         ull tmp5 = 1;
  66.         for (ul i = 1; i <= 19; ++i) {
  67.             if (cntamb[i]) {
  68.                 ull tmp6 = fac[cntamb[i]];
  69.                 for (ul j = 0; i + j <= 19; ++j) {
  70.                     tmp6 /= fac[cntambb[i][j]];
  71.                 }
  72.                 tmp5 *= tmp6;
  73.             }
  74.         }
  75.         subans[hash] += tmp1 * tmp2 * tmp3 * tmp4 * tmp5;
  76.         return;
  77.     }
  78.     for (b[i] = (i != 0 && a[i] == a[i - 1]) ? cnt : ul(0); b[i] <= a[i]; ++b[i]) {
  79.         ++cntb[b[i]];
  80.         if (i && b[i] != a[i] && b[i]) {
  81.             ++cntb3[b[i]];
  82.         }
  83.         if (i && b[i] != a[i]) {
  84.             ++cntamb[a[i] - b[i]];
  85.             ++cntambb[a[i] - b[i]][b[i]];
  86.         }
  87.         search2(i + 1, nct, sum + b[i], prod * fac[b[i]], i ? (a[i] == b[i] ? hash : mul(hash, a[i] - b[i] ^ y)) : ul(1), t1 + (i != 0 && b[i] == 0), t2 + (i != 0 && b[i] == a[i]), t3 + (i != 0 && b[i] != a[i] && b[i] != 0), b[i]);
  88.         --cntb[b[i]];
  89.         if (i && b[i] != a[i] && b[i]) {
  90.             --cntb3[b[i]];
  91.         }
  92.         if (i && b[i] != a[i]) {
  93.             --cntamb[a[i] - b[i]];
  94.             --cntambb[a[i] - b[i]][b[i]];
  95.         }
  96.     }
  97. }
  99. void search(ul i, ul cnt, ul sum)
  100. {
  101.     if (i > 9) {
  102.         return;
  103.     }
  104.     if (i == 0) {
  105.         for (a[0] = 1; a[0] <= 19; ++a[0]) {
  106.             search(1, 1, a[0]);
  107.             search2(0, i, 0, 1, 1, 0, 0, 0, 0);
  108.         }
  109.     } else {
  110.         for (a[i] = cnt; sum + a[i] <= 19 && a[i] < a[0]; ++a[i]) {
  111.             search(i + 1, a[i], sum + a[i]);
  112.             search2(0, i, 0, 1, 1, 0, 0, 0, 0);
  113.         }
  114.     }
  115. }
  117. ul d;
  119. ul cnt[10];
  121. bool check(ull x, ul d)
  122. {
  123.     static ul cnt[10];
  124.     std::memset(cnt, 0, sizeof(cnt));
  125.     while (x) {
  126.         ++cnt[x % 10];
  127.         x /= 10;
  128.     }
  129.     for (ul i = 0; i <= 9; ++i) {
  130.         if (cnt[i] >= cnt[d] && i != d) {
  131.             return false;
  132.         }
  133.     }
  134.     return true;
  135. }
  137. ull calc2(ull v, ul len, ul d)
  138. {
  139.     ull qv = v;
  140.     std::memset(cnt, 0, sizeof(cnt));
  141.     while (v) {
  142.         ++cnt[v % 10];
  143.         v /= 10;
  144.     }
  145.     ul hash = 1;
  146.     for (ul i = 0; i <= 9; ++i) {
  147.         if (i != d && cnt[i]) {
  148.             hash = mul(hash, y ^ cnt[i]);
  149.         }
  150.     }
  151.     hash = mul(mul(hash, x) ^ cnt[d], x) ^ len;
  152.     auto it = subans.find(hash);
  153.     return it != subans.end() ? it->second : ull(0);
  154. }
  156. ull calc(ull l, ull r, ul d)
  157. {
  158.     ull ans = 0;
  159.     ul len = 0;
  160.     for ( ; r >= l; ++len) {
  161.         if (l / 10 == r / 10 && (l % 10 != 0 || r % 10 != 9)) {
  162.             for (ull i = l; i <= r; ++i) {
  163.                 ans += calc2(i, len, d);
  164.             }
  165.             break;
  166.         }
  167.         if (l % 10 != 0) {
  168.             for (ull i = l; i / 10 == l / 10; ++i) {
  169.                 ans += calc2(i, len, d);
  170.             }
  171.             l = l / 10 + 1;
  172.         } else {
  173.             l = l / 10;
  174.         }
  175.         if (r % 10 != 9) {
  176.             for (ull i = r; i / 10 == r / 10; --i) {
  177.                 ans += calc2(i, len, d);
  178.             }
  179.             r = r / 10 - 1;
  180.         } else {
  181.             r = r / 10;
  182.         }
  183.     }
  184.     return ans;
  185. }
  187. ul T;
  189. int main()
  190. {
  191.     std::ios::sync_with_stdio(false);
  192.     std::cin.tie(0);
  193.     iss.tie(0);
  194.     oss.tie(0);
  195.     std::getline(std::cin, instr, char(0));
  196.     iss.str(instr);
  197.     rnd.seed(std::time(0));
  198.     x = rnd();
  199.     y = rnd();
  200.     fac[0] = 1;
  201.     for (ul i = 1; i <= 19; ++i) {
  202.         fac[i] = fac[i - 1] * i;
  203.     }
  204.     search(0, 0, 0);
  205.     for (ul len = 0; len <= 10; ++len) {
  206.         for (ull v = 1; v <= 999; ++v) {
  207.             calc2(v, len, 1);
  208.         }
  209.     }
  210.     iss >> T;
  211.     for (ul Case = 1; Case <= T; ++Case) {
  212.         iss >> l >> r >> d;
  213.         ull ans = 0;
  214.         for (ull i = 1; i <= 1e18; i *= 10) {
  215.             ull j = i * 10 - 1;
  216.             if (i <= r && j >= l) {
  217.                 ans += calc(std::max(i, l), std::min(j, r), d);
  218.             }
  219.         }
  220.         oss << ans << '\n';
  221.     }
  222.     std::cout << oss.str();
  223.     return 0;
  224. }

G、Tokitsukaze and Rescue 6797

官方题解如下：
image.png-169.5kB

  1. #pragma GCC target ("pclmul")
  2. #include <bits/stdc++.h>
  3. #include <emmintrin.h>
  4. #include <wmmintrin.h>
  6. std::stringstream iss;
  7. std::stringstream oss;
  8. std::string instr;
  10. using ul = std::uint32_t;
  11. using ull = std::uint64_t;
  12. using li = std::int32_t;
  13. using ll = std::int64_t;
  15. ul T;
  17. ul n, k;
  18. const ul maxn = 50;
  20. ul edge[maxn + 1][maxn + 1];
  22. ul dis1[6][maxn + 1];
  23. ul disn[6][maxn + 1];
  25. ul ans = 0;
  27. bool ban[maxn + 1][maxn + 1];
  29. ul tim;
  30. ul vis[maxn + 1];
  32. void search(ul cnt)
  33. {
  34.     for (ul i = 1; i <= n; ++i) {
  35.         dis1[cnt][i] = 1e9;
  36.         disn[cnt][i] = 1e9;
  37.     }
  38.     dis1[cnt][25] = 0;
  39.     ++tim;
  40.     while (true) {
  41.         ul tmp = 0;
  42.         for (ul i = 1; i <= n; ++i) {
  43.             if (vis[i] != tim) {
  44.                 if (!tmp || dis1[cnt][tmp] > dis1[cnt][i]) {
  45.                     tmp = i;
  46.                 }
  47.             }
  48.         }
  49.         if (!tmp) {
  50.             break;
  51.         }
  52.         vis[tmp] = tim;
  53.         for (ul i = 1; i <= n; ++i) {
  54.             if (!ban[tmp][i]) {
  55.                 dis1[cnt][i] = std::min(dis1[cnt][i], dis1[cnt][tmp] + edge[tmp][i]);
  56.             }
  57.         }
  58.     }
  59.     disn[cnt][n] = 0;
  60.     ++tim;
  61.     while (true) {
  62.         ul tmp = 0;
  63.         for (ul i = 1; i <= n; ++i) {
  64.             if (vis[i] != tim) {
  65.                 if (!tmp || disn[cnt][tmp] > disn[cnt][i]) {
  66.                     tmp = i;
  67.                 }
  68.             }
  69.         }
  70.         if (!tmp) {
  71.             break;
  72.         }
  73.         vis[tmp] = tim;
  74.         for (ul i = 1; i <= n; ++i) {
  75.             if (!ban[tmp][i]) {
  76.                 disn[cnt][i] = std::min(disn[cnt][i], disn[cnt][tmp] + edge[tmp][i]);
  77.             }
  78.         }
  79.     }
  80.     if (cnt == k) {
  81.         ans = std::max(dis1[cnt][n], ans);
  82.     } else {
  83.         for (ul a = 1; a + 1 <= n; ++a) {
  84.             for (ul b = a + 1; b <= n; ++b) {
  85.                 if (ban[a][b]) {
  86.                     continue;
  87.                 }
  88.                 if (dis1[cnt][a] + edge[a][b] + disn[cnt][b] == dis1[cnt][n] || dis1[cnt][b] + edge[b][a] + disn[cnt][a] == dis1[cnt][n]) {
  89.                     ban[a][b] = ban[b][a] = true;
  90.                     search(cnt + 1);
  91.                     ban[a][b] = ban[b][a] = false;
  92.                 }
  93.             }
  94.         }
  95.     }
  96. }
  98. int main()
  99. {
  100.     std::ios::sync_with_stdio(false);
  101.     std::cin.tie(0);
  102.     iss.tie(0);
  103.     oss.tie(0);
  104.     std::getline(std::cin, instr, char(0));
  105.     iss.str(instr);
  106.     iss >> T;
  107.     for (ul Case = 1; Case <= T; ++Case) {
  108.         iss >> n >> k;
  109.         for (ul i = 1; i + 1 <= n; ++i) {
  110.             for (ul j = i + 1; j <= n; ++j) {
  111.                 ul u, v, w;
  112.                 iss >> u >> v >> w;
  113.                 edge[v][u] = edge[u][v] = w;
  114.             }
  115.         }
  116.         ans = 0;
  117.         search(0);
  118.         oss << ans << '\n';
  119.     }
  120.     std::cout << oss.str();
  121.     return 0;
  122. }

H、Triangle Collision 6798

简单题

  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 lf = double;
  13. class vec {
  14. public:
  15.     lf x = 0;
  16.     lf y = 0;
  17.     vec()=default;
  18.     vec(lf a, lf b): x(a), y(b) {}
  19. };
  21. vec operator+(const vec& a, const vec& b)
  22. {
  23.     return vec(a.x + b.x, a.y + b.y);
  24. }
  26. vec operator-(const vec& a, const vec& b)
  27. {
  28.     return vec(a.x - b.x, a.y - b.y);
  29. }
  31. vec operator*(lf a, const vec& b)
  32. {
  33.     return vec(a * b.x, a * b.y);
  34. }
  36. lf operator*(const vec& a, const vec& b)
  37. {
  38.     return a.x * b.x + a.y * b.y;
  39. }
  41. ull cnt(lf a, lf b)
  42. {
  43.     return ll(std::floor(std::max(a, b))) - ll(std::ceil(std::min(a, b))) + 1;
  44. }
  46. lf l;
  48. const lf s3 = std::sqrt(lf(3));
  50. ull query(const vec& s, const vec& t)
  51. {
  52.     ull ret = 0;
  53.     ret += cnt(s * vec(0, 1) / s3 / l * lf(2), t * vec(0, 1) / s3 / l * lf(2));
  54.     ret += cnt(s * vec(s3 * lf(0.5), 0.5) / s3 / l * lf(2), t * vec(s3 * lf(0.5), 0.5) / s3 / l * lf(2));
  55.     ret += cnt(s * vec(-s3 * lf(0.5), 0.5) / s3 / l * lf(2), t * vec(-s3 * lf(0.5), 0.5) / s3 / l * lf(2));
  56.     return ret;
  57. }
  59. ul T;
  61. const lf eps = 1e-4;
  63. int main()
  64. {
  65.     std::ios::sync_with_stdio(false);
  66.     std::cin.tie(0);
  67.     iss.tie(0);
  68.     oss.tie(0);
  69.     std::getline(std::cin, instr, char(0));
  70.     iss.str(instr);
  71.     iss >> T;
  72.     for (ul Case = 1; Case <= T; ++Case) {
  73.         vec s, v;
  74.         ul k;
  75.         iss >> l >> s.x >> s.y >> v.x >> v.y >> k;
  76.         lf a = 0, b = k * l;
  77.         while (b - a > std::max(a, lf(1)) * eps) {
  78.             lf mid = (a + b) * lf(0.5);
  79.             vec t = mid * v + s;
  80.             ull cnt = query(s + vec(l * lf(0.5), 0), t + vec(l * lf(0.5), 0));
  81.             if (cnt >= k) {
  82.                 b = mid;
  83.             } else {
  84.                 a = mid;
  85.             }
  86.         }
  87.         oss << std::fixed << std::setprecision(6) << (a + b) * lf(0.5) << '\n';
  88.     }
  89.     std::cout << oss.str();
  90.     return 0;
  91. }

I、Parentheses Matching 6799

官方题解如下：
image.png-138.5kB

  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;
  14. const ul maxn = 1e5;
  16. char s[maxn + 2];
  18. char s2[maxn + 2];
  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 >> s + 1;
  31.         ul n = std::strlen(s + 1);
  32.         li cntstar = 0;
  33.         li pm = 0;
  34.         for (ul i = 1; i <= n; ++i) {
  35.             if (s[i] == '(') {
  36.                 ++pm;
  37.             } else if (s[i] == ')') {
  38.                 --pm;
  39.             } else {
  40.                 ++cntstar;
  41.             }
  42.         }
  43.         if (pm - cntstar > 0 || pm + cntstar < 0) {
  44.             oss << "No solution!\n";
  45.             continue;
  46.         }
  47.         if (pm < 0) {
  48.             for (ul i = 1; i <= n && pm; ++i) {
  49.                 if (s[i] == '*') {
  50.                     ++pm;
  51.                     --cntstar;
  52.                     s[i] = '(';
  53.                 }
  54.             }
  55.         }
  56.         if (pm > 0) {
  57.             for (ul i = n; i >= 1 && pm; --i) {
  58.                 if (s[i] == '*') {
  59.                     --pm;
  60.                     --cntstar;
  61.                     s[i] = ')';
  62.                 }
  63.             }
  64.         }
  65.         li l = -1, r = (cntstar >> 1) + 1;
  66.         while (l + 1 != r) {
  67.             li mid = l + (r - l >> 1);
  68.             std::memcpy(s2 + 1, s + 1, sizeof(char) * n);
  69.             li cnt = mid;
  70.             for (ul i = 1; i <= n && cnt; ++i) {
  71.                 if (s[i] == '*') {
  72.                     --cnt;
  73.                     s2[i] = '(';
  74.                 }
  75.             }
  76.             cnt = mid;
  77.             for (ul i = n; i >= 1 && cnt; --i) {
  78.                 if (s[i] == '*') {
  79.                     --cnt;
  80.                     s2[i] = ')';
  81.                 }
  82.             }
  83.             li state = 0;
  84.             for (ul i = 1; i <= n; ++i) {
  85.                 if (s2[i] == '(') {
  86.                     ++state;
  87.                 } else if (s2[i] == ')') {
  88.                     --state;
  89.                     if (state < 0) {
  90.                         break;
  91.                     }
  92.                 }
  93.             }
  94.             if (state == 0) {
  95.                 r = mid;
  96.             } else {
  97.                 l = mid;
  98.             }
  99.         }
  100.         if (r == (cntstar >> 1) + 1) {
  101.             oss << "No solution!\n";
  102.         } else {
  103.             std::memcpy(s2 + 1, s + 1, sizeof(char) * n);
  104.             li cnt = r;
  105.             for (ul i = 1; i <= n && cnt; ++i) {
  106.                 if (s[i] == '*') {
  107.                     --cnt;
  108.                     s2[i] = '(';
  109.                 }
  110.             }
  111.             cnt = r;
  112.             for (ul i = n; i >= 1 && cnt; --i) {
  113.                 if (s[i] == '*') {
  114.                     --cnt;
  115.                     s2[i] = ')';
  116.                 }
  117.             }
  118.             for (ul i = 1; i <= n; ++i) {
  119.                 if (s2[i] != '*') {
  120.                     oss << s2[i];
  121.                 }
  122.             }
  123.             oss << '\n';
  124.         }
  125.     }
  126.     std::cout << oss.str();
  127.     return 0;
  128. }

J、Play osu! on Your Tablet 6800

官方题解如下：
无标题.png-192.7kB
下方代码采用纯分治写法，不使用数据结构，故实际时间复杂度为。综合度很高的分治题。

  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;
  14. const li maxn = 1e5;
  16. li n;
  18. ll x[maxn + 1];
  19. ll y[maxn + 1];
  21. ll dis(ll a, ll b)
  22. {
  23.     return std::max(a, b) - std::min(a, b);
  24. }
  26. ll ans[maxn + 1];
  28. class node {
  29. public:
  30.     li i = 0;
  31.     bool query = false;
  32.     bool insert = false;
  33.     node()=default;
  34.     node(li i, bool query, bool insert): i(i), query(query), insert(insert) {}
  35.     ll xx() const {
  36.         return x[i + query];
  37.     }
  38.     ll yy() const {
  39.         return y[i + query];
  40.     }
  41. };
  43. const ll inf = 1e17;
  45. void cdqy(li l, li r, const std::vector<node>& vx, ll xdir)
  46. {
  47.     ll mn = inf;
  48.     for (li i = l; i <= r; ++i) {
  49.         if (vx[i].insert) {
  50.             mn = std::min(mn, ans[vx[i].i] - xdir * vx[i].xx() - vx[i].yy());
  51.         } else {
  52.             ans[vx[i].i] = std::min(ans[vx[i].i], mn + xdir * vx[i].xx() + vx[i].yy());
  53.         }
  54.     }
  55.     mn = inf;
  56.     for (li i = r; i >= l; --i) {
  57.         if (vx[i].insert) {
  58.             mn = std::min(mn, ans[vx[i].i] - xdir * vx[i].xx() + vx[i].yy());
  59.         } else {
  60.             ans[vx[i].i] = std::min(ans[vx[i].i], mn + xdir * vx[i].xx() - vx[i].yy());
  61.         }
  62.     }
  63. }
  65. void cdqx(li l, li r, const std::vector<node>& vi)
  66. {
  67.     if (l > r || l == r) {
  68.         return;
  69.     }
  70.     static std::vector<node> v1;
  71.     static std::vector<node> v2;
  72.     li midl = l + r >> 1;
  73.     li midr = midl + 1;
  74.     v1.resize(0);
  75.     v2.resize(0);
  76.     ul v1flag = 0, v2flag = 0;
  77.     for (li i = l; i <= midl; ++i) {
  78.         if (vi[i].insert) {
  79.             v1.push_back(vi[i]);
  80.             v1flag |= 1;
  81.         } else {
  82.             v2.push_back(vi[i]);
  83.             v2flag |= 2;
  84.         }
  85.     }
  86.     for (li i = midr; i <= r; ++i) {
  87.         if (vi[i].query) {
  88.             v1.push_back(vi[i]);
  89.             v1flag |= 2;
  90.         } else {
  91.             v2.push_back(vi[i]);
  92.             v2flag |= 1;
  93.         }
  94.     }
  95.     if (v1flag == 3) {
  96.         std::sort(v1.begin(), v1.end(), [](const node& a, const node& b) {return a.yy() < b.yy();});
  97.         cdqy(0, v1.size() - 1, v1, 1);
  98.     }
  99.     if (v2flag == 3) {
  100.         std::sort(v2.begin(), v2.end(), [](const node& a, const node& b) {return a.yy() < b.yy();});
  101.         cdqy(0, v2.size() - 1, v2, -1);
  102.     }
  103.     if (v1flag & v2flag >> 1 & 1) {
  104.         cdqx(l, midl, vi);
  105.     }
  106.     if (v1flag >> 1 & v2flag & 1) {
  107.         cdqx(midr, r, vi);
  108.     }
  109. }
  111. void cdqi1(li l, li r)
  112. {
  113.     if (l == r) {
  114.         if (l != n) {
  115.             ans[l] = dis(x[l], x[l + 1]) + dis(y[l], y[l + 1]);
  116.         }
  117.         return;
  118.     }
  119.     static std::vector<node> v;
  120.     li midl = l + r >> 1;
  121.     li midr = midl + 1;
  122.     cdqi1(l, midl);
  123.     v.resize(0);
  124.     for (li i = l; i <= midl; ++i) {
  125.         v.push_back(node(i, true, false));
  126.     }
  127.     for (li i = midr; i <= r; ++i) {
  128.         v.push_back(node(i, false, true));
  129.     }
  130.     std::sort(v.begin(), v.end(), [](const node& a, const node& b){return a.xx() < b.xx();});
  131.     cdqx(0, v.size() - 1, v);
  132.     cdqi1(midr, r);
  133. }
  135. void cdqi2(li l, li r)
  136. {
  137.     if (l > r) {
  138.         return;
  139.     }
  140.     if (l == r) {
  141.         if (l != n) {
  142.             ans[l] -= dis(x[l], x[l + 1]) + dis(y[l], y[l + 1]);
  143.         }
  144.         return;
  145.     }
  146.     static std::vector<node> v;
  147.     li midl = l + r >> 1;
  148.     li midr = midl + 1;
  149.     cdqi2(l, midl);
  150.     v.resize(0);
  151.     for (li i = l; i <= midl; ++i) {
  152.         v.push_back(node(i, false, true));
  153.     }
  154.     for (li i = midr; i <= r; ++i) {
  155.         v.push_back(node(i, true, false));
  156.     }
  157.     std::sort(v.begin(), v.end(), [](const node& a, const node& b){return a.xx() < b.xx();});
  158.     cdqx(0, v.size() - 1, v);
  159.     cdqi2(midr, r);
  160. }
  162. int main()
  163. {
  164.     std::ios::sync_with_stdio(false);
  165.     std::cin.tie(0);
  166.     iss.tie(0);
  167.     oss.tie(0);
  168.     std::getline(std::cin, instr, char(0));
  169.     iss.str(instr);
  170.     iss >> T;
  171.     for (ul Case = 1; Case <= T; ++Case) {
  172.         iss >> n;
  173.         ll sum = 0;
  174.         for (li i = 1; i <= n; ++i) {
  175.             iss >> x[i] >> y[i];
  176.             if (i != 1) {
  177.                 sum += dis(x[i], x[i - 1]) + dis(y[i], y[i - 1]);
  178.             }
  179.         }
  180.         std::memset(ans + 1, 0, sizeof(ll) * n);
  181.         cdqi1(1, n);
  182.         cdqi2(1, n - 1);
  183.         ll out = inf;
  184.         for (li i = 1; i <= n; ++i) {
  185.             out = std::min(out, ans[i] + sum);
  186.         }
  187.         oss << out << '\n';
  188.     }
  189.     std::cout << oss.str();
  190.     return 0;
  191. }

K、Game on a Circle 6801

设被删除的时候是其第次被访问，于是显然是独立同分布的。且，官方题解如下：
无标题.png-103.8kB

  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. class ntt_t {
  86. public:
  87.     static const ul lgsz = 21;
  88.     static const ul sz = 1 << lgsz;
  89.     static const ul g = 3;
  90.     ul w[sz + 1];
  91.     ul leninv[lgsz + 1];
  92.     ntt_t() {
  93.         ul wn = pow(g, (base - 1) >> lgsz);
  94.         w[0] = 1;
  95.         for (ul i = 1; i <= sz; ++i) {
  96.             w[i] = mul(w[i - 1], wn);
  97.         }
  98.         leninv[lgsz] = inverse(sz);
  99.         for (ul i = lgsz - 1; ~i; --i) {
  100.             leninv[i] = plus(leninv[i + 1], leninv[i + 1]);
  101.         }
  102.     }
  103.     void operator()(vul& v, ul& n, bool inv) {
  104.         ul lgn = 0;
  105.         while ((1 << lgn) < n) {
  106.             ++lgn;
  107.         }
  108.         n = 1 << lgn;
  109.         v.resize(n, 0);
  110.         for (ul i = 0, j = 0; i != n; ++i) {
  111.             if (i < j) {
  112.                 std::swap(v[i], v[j]);
  113.             }
  114.             ul k = n >> 1;
  115.             while (k & j) {
  116.                 j &= ~k;
  117.                 k >>= 1;
  118.             }
  119.             j |= k;
  120.         }
  121.         for (ul lgmid = 0; (1 << lgmid) != n; ++lgmid) {
  122.             ul mid = 1 << lgmid;
  123.             ul len = mid << 1;
  124.             for (ul i = 0; i != n; i += len) {
  125.                 for (ul j = 0; j != mid; ++j) {
  126.                     ul t0 = v[i + j];
  127.                     ul t1 = mul(w[inv ? (len - j << lgsz - lgmid - 1) : (j << lgsz - lgmid - 1)], v[i + j + mid]);
  128.                     v[i + j] = plus(t0, t1);
  129.                     v[i + j + mid] = minus(t0, t1);
  130.                 }
  131.             }
  132.         }
  133.         if (inv) {
  134.             for (ul i = 0; i != n; ++i) {
  135.                 v[i] = mul(v[i], leninv[lgn]);
  136.             }
  137.         }
  138.     }
  139. } ntt;
  141. polynomial& operator*=(polynomial& a, const polynomial& b)
  142. {
  143.     if (!b.size() || !a.size()) {
  144.         a.resize(0);
  145.         return a;
  146.     }
  147.     polynomial temp = b;
  148.     ul npmp1 = a.size() + b.size() - 1;
  149.     if (ull(a.size()) * ull(b.size()) <= ull(npmp1) * ull(50)) {
  150.         temp.resize(0);
  151.         temp.resize(npmp1, 0);
  152.         for (ul i = 0; i != a.size(); ++i) {
  153.             for (ul j = 0; j != b.size(); ++j) {
  154.                 temp[i + j] = plus(temp[i + j], mul(a[i], b[j]));
  155.             }
  156.         }
  157.         a = temp;
  158.         a.clearzero();
  159.         return a;
  160.     }
  161.     ntt(a, npmp1, false);
  162.     ntt(temp, npmp1, false);
  163.     for (ul i = 0; i != npmp1; ++i) {
  164.         a[i] = mul(a[i], temp[i]);
  165.     }
  166.     ntt(a, npmp1, true);
  167.     a.clearzero();
  168.     return a;
  169. }
  171. polynomial operator*(const polynomial& a, const polynomial& b)
  172. {
  173.     polynomial ret = a;
  174.     return ret *= b;
  175. }
  177. ul T;
  178. ul n, a, b, c;
  179. const ul maxn = 1e6;
  181. ul fac[maxn + 1];
  182. ul fiv[maxn + 1];
  183. ul inv[maxn + 1];
  185. polynomial alpha, beta;
  187. ul f[maxn + 1];
  189. ul qpow[maxn + 1];
  191. int main()
  192. {
  193.     std::ios::sync_with_stdio(false);
  194.     std::cin.tie(0);
  195.     iss.tie(0);
  196.     oss.tie(0);
  197.     std::getline(std::cin, instr, char(0));
  198.     iss.str(instr);
  199.     fac[0] = 1;
  200.     for (ul i = 1; i <= maxn; ++i) {
  201.         fac[i] = mul(fac[i - 1], i);
  202.     }
  203.     fiv[maxn] = inverse(fac[maxn]);
  204.     for (ul i = maxn; i >= 1; --i) {
  205.         fiv[i - 1] = mul(fiv[i], i);
  206.         inv[i] = mul(fiv[i], fac[i - 1]);
  207.     }
  208.     iss >> T;
  209.     for (ul Case = 1; Case <= T; ++Case) {
  210.         iss >> n >> a >> b >> c;
  211.         ul p = mul(a, inverse(b));
  212.         ul q = minus(1, p);
  213.         f[0] = 1;
  214.         f[1] = plus(mul(c - 1, q), n - c);
  215.         for (ul i = 1; i + 1 <= n - 1; ++i) {
  216.             f[i + 1] = mul(inv[i + 1], plus(mul(plus(mul(c - 1, q), minus(minus(n, c), mul(plus(q, 1), i))), f[i]), mul(mul(q, n - i), f[i - 1])));
  217.         }
  218.         alpha.resize(n);
  219.         beta.resize(n);
  220.         qpow[0] = 1;
  221.         for (ul i = 1; i <= n; ++i) {
  222.             qpow[i] = mul(qpow[i - 1], q);
  223.         }
  224.         for (ul i = 0; i <= n - 1; ++i) {
  225.             alpha[i] = mul(mul(fac[n - 1 - i], f[n - 1 - i]), inverse(minus(1, qpow[n - i])));
  226.             beta[i] = (i & 1) ? minus(0, fiv[i]) : fiv[i];
  227.         }
  228.         alpha *= beta;
  229.         alpha.resize(n, 0);
  230.         for (ul i = 0; i <= n - 1; ++i) {
  231.             oss << mul(p, mul(alpha[i], fiv[n - 1 - i])) << '\n';
  232.         }
  233.     }
  234.     std::cout << oss.str();
  235.     return 0;
  236. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注