[关闭]
@qq290637843 2021-01-23T04:40:27.000000Z 字数 25702 阅读 346

2019银川

题目见https://www.jisuanke.com/contest/5527/challenges，其中N题不知道题面在哪找。

A、Girls Band Party

按照是否有第一类加成和是否有第二类加成分为四类，每一类最多留下五个基价值最高的不同名字，然后总共最多二十张卡作为选择，最后暴力二十选五。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. using card = std::pair<std::string, std::string>;
  12. std::map<card, ul> map1;
  14. ul n;
  16. char str1[11], str2[11];
  18. std::string bonuscolor;
  20. using namep = std::pair<std::string, ul>;
  22. std::vector<namep> other[2];
  24. std::map<std::string, ul> nameid;
  26. ul power[16][2];
  28. std::set<std::string> already;
  30. ul tot = 0;
  32. using cd = std::pair<ul, ul>;
  34. cd sp[21];
  36. int main()
  37. {
  38.     std::scanf("%u", &T);
  39.     for (ul Case = 1; Case <= T; ++Case) {
  40.         std::scanf("%u", &n);
  41.         map1.clear();
  42.         for (ul i = 1; i <= n; ++i) {
  43.             ul p;
  44.             std::scanf("%s%s%u", &str1, &str2, &p);
  45.             auto& v = map1[card(std::string(str1), std::string(str2))];
  46.             v = std::max(v, p);
  47.         }
  48.         nameid.clear();
  49.         for (ul i = 1; i <= 5; ++i) {
  50.             std::scanf("%s", &str1);
  51.             nameid[str1] = i;
  52.         }
  53.         std::scanf("%s", &str1);
  54.         bonuscolor = str1;
  55.         other[0].resize(0);
  56.         other[1].resize(0);
  57.         std::memset(power, 0, sizeof(power));
  58.         for (const auto& p : map1) {
  59.             auto it = nameid.find(p.first.first);
  60.             if (it != nameid.end()) {
  61.                 auto& v = power[it->second][p.first.second == bonuscolor];
  62.                 v = std::max(v, p.second);
  63.             } else {
  64.                 other[p.first.second == bonuscolor].push_back(namep(p.first.first, p.second));
  65.             }
  66.         }
  67.         std::sort(other[0].begin(), other[0].end(), [](const namep& a, const namep& b){return a.second > b.second;});
  68.         std::sort(other[1].begin(), other[1].end(), [](const namep& a, const namep& b){return a.second > b.second;});
  69.         for (ul i = 0; i <= 1; ++i) {
  70.             already.clear();
  71.             for (const auto& p : other[i]) {
  72.                 if (already.insert(p.first).second) {
  73.                     auto& currnameid = nameid[p.first];
  74.                     if (!currnameid) {
  75.                         currnameid = nameid.size();
  76.                     }
  77.                     power[currnameid][i] = p.second;
  78.                     if (already.size() == 5) {
  79.                         break;
  80.                     }
  81.                 }
  82.             }
  83.         }
  84.         tot = 0;
  85.         for (ul i = 1; i <= nameid.size(); ++i) {
  86.             for (ul j = 0; j <= 1; ++j) {
  87.                 if (power[i][j]) {
  88.                     ++tot;
  89.                     sp[tot].first = i;
  90.                     sp[tot].second = j;
  91.                 }
  92.             }
  93.         }
  94.         ul base = 0;
  95.         ul ans = 0;
  96.         ul bonus = 0;
  97.         for (ul a = 1; a + 4 <= tot; ++a) {
  98.             base += power[sp[a].first][sp[a].second];
  99.             if (sp[a].first <= 5) {
  100.                 bonus += 1;
  101.             }
  102.             if (sp[a].second) {
  103.                 bonus += 2;
  104.             }
  105.             for (ul b = a + 1; b + 3 <= tot; ++b) {
  106.                 if (sp[a].first == sp[b].first) {
  107.                     continue;
  108.                 }
  109.                 base += power[sp[b].first][sp[b].second];
  110.                 if (sp[b].first <= 5) {
  111.                     bonus += 1;
  112.                 }
  113.                 if (sp[b].second) {
  114.                     bonus += 2;
  115.                 }
  116.                 for (ul c = b + 1; c + 2 <= tot; ++c) {
  117.                     if (sp[c].first == sp[b].first) {
  118.                         continue;
  119.                     }
  120.                     base += power[sp[c].first][sp[c].second];
  121.                     if (sp[c].first <= 5) {
  122.                         bonus += 1;
  123.                     }
  124.                     if (sp[c].second) {
  125.                         bonus += 2;
  126.                     }
  127.                     for (ul d = c + 1; d + 1 <= tot; ++d) {
  128.                         if (sp[d].first == sp[c].first) {
  129.                             continue;
  130.                         }
  131.                         base += power[sp[d].first][sp[d].second];
  132.                         if (sp[d].first <= 5) {
  133.                             bonus += 1;
  134.                         }
  135.                         if (sp[d].second) {
  136.                             bonus += 2;
  137.                         }
  138.                         for (ul e = d + 1; e <= tot; ++e) {
  139.                             if (sp[e].first == sp[d].first) {
  140.                                 continue;
  141.                             }
  142.                             base += power[sp[e].first][sp[e].second];
  143.                             if (sp[e].first <= 5) {
  144.                                 bonus += 1;
  145.                             }
  146.                             if (sp[e].second) {
  147.                                 bonus += 2;
  148.                             }
  149.                             ans = std::max(ans, base * (10 + bonus) / 10);
  150.                             base -= power[sp[e].first][sp[e].second];
  151.                             if (sp[e].first <= 5) {
  152.                                 bonus -= 1;
  153.                             }
  154.                             if (sp[e].second) {
  155.                                 bonus -= 2;
  156.                             }
  157.                         }
  158.                         base -= power[sp[d].first][sp[d].second];
  159.                         if (sp[d].first <= 5) {
  160.                             bonus -= 1;
  161.                         }
  162.                         if (sp[d].second) {
  163.                             bonus -= 2;
  164.                         }
  165.                     }
  166.                     base -= power[sp[c].first][sp[c].second];
  167.                     if (sp[c].first <= 5) {
  168.                         bonus -= 1;
  169.                     }
  170.                     if (sp[c].second) {
  171.                         bonus -= 2;
  172.                     }
  173.                 }
  174.                 base -= power[sp[b].first][sp[b].second];
  175.                 if (sp[b].first <= 5) {
  176.                     bonus -= 1;
  177.                 }
  178.                 if (sp[b].second) {
  179.                     bonus -= 2;
  180.                 }
  181.             }
  182.             base -= power[sp[a].first][sp[a].second];
  183.             if (sp[a].first <= 5) {
  184.                 bonus -= 1;
  185.             }
  186.             if (sp[a].second) {
  187.                 bonus -= 2;
  188.             }
  189.         }
  190.         std::printf("%u\n", ans);
  191.     }
  192.     return 0;
  193. }

B、So Easy

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n;
  10. const li maxn = 1000;
  12. li v[maxn][maxn];
  14. ul a, b;
  16. int main()
  17. {
  18.     std::scanf("%u", &n);
  19.     for (ul i = 0; i < n; ++i) {
  20.         for (ul j = 0; j < n; ++j) {
  21.             std::scanf("%d", &v[i][j]);
  22.             if (v[i][j] < 0) {
  23.                 a = i;
  24.                 b = j;
  25.             }
  26.         }
  27.     }
  28.     std::printf("%d\n", v[(a + 1) % n][b] + v[a][(b + 1) % n] - v[(a + 1) % n][(b + 1) % n]);
  29.     return 0;
  30. }

C、Image Processing

设

于是对于，满足如下递推式：
由于如果则，故如果则，这说明在这种情况下，必定没有保留的价值，所以对于求，只需要保留的单调（升）栈。现在注意在单调栈内如果且且，那么由于于是，又因为，故，又因为，故，故，这就说明随着增大，最优一定可以是不降的，故上文中的单调栈改为单调队列即可。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n, k;
  10. const ul maxn = 1e6;
  12. using pulul = std::pair<ul, ul>;
  14. std::deque<pulul> cqueue;
  16. std::deque<pulul> vqueueu;
  17. std::deque<pulul> vqueued;
  19. ul c[maxn + 1];
  21. ul g(ul x, bool re)
  22. {
  23.     if (re) {
  24.         ul l, r;
  25.         l = -1;
  26.         r = vqueueu.size() - 1;
  27.         while (l + 1 != r) {
  28.             ul mid = l + r >> 1;
  29.             if (vqueueu[mid].first < x) {
  30.                 l = mid;
  31.             } else {
  32.                 r = mid;
  33.             }
  34.         }
  35.         ul u = vqueueu[r].second;
  36.         l = -1;
  37.         r = vqueued.size() - 1;
  38.         while (l + 1 != r) {
  39.             ul mid = l + r >> 1;
  40.             if (vqueued[mid].first < x) {
  41.                 l = mid;
  42.             } else {
  43.                 r = mid;
  44.             }
  45.         }
  46.         ul d = vqueued[r].second;
  47.         return d - u;
  48.     } else {
  49.         while (vqueueu.front().first < x) {
  50.             vqueueu.pop_front();
  51.         }
  52.         while (vqueued.front().first < x) {
  53.             vqueued.pop_front();
  54.         }
  55.         return vqueued.front().second - vqueueu.front().second;
  56.     }
  57. }
  59. int main()
  60. {
  61.     std::scanf("%u%u", &n, &k);
  62.     for (ul i = 1; i <= n; ++i) {
  63.         ul v;
  64.         std::scanf("%u", &v);
  65.         v ^= c[i - 1];
  66.         while (vqueueu.size() && vqueueu.back().second >= v) {
  67.             vqueueu.pop_back();
  68.         }
  69.         vqueueu.push_back(pulul(i, v));
  70.         while (vqueued.size() && vqueued.back().second <= v) {
  71.             vqueued.pop_back();
  72.         }
  73.         vqueued.push_back(pulul(i, v));
  74.         if (i < k) {
  75.             c[i] = 0;
  76.         } else if (i < k + k) {
  77.             c[i] = vqueued.front().second - vqueueu.front().second;
  78.         } else {
  79.             while (cqueue.size() && cqueue.back().second >= c[i - k]) {
  80.                 cqueue.pop_back();
  81.             }
  82.             cqueue.push_back(pulul(i - k, c[i - k]));
  83.             while (cqueue.size() >= 2 && std::max(cqueue[0].second, g(cqueue[0].first + 1, false)) >= std::max(cqueue[1].second, g(cqueue[1].first + 1, true))) {
  84.                 cqueue.pop_front();
  85.             }
  86.             c[i] = std::max(cqueue[0].second, g(cqueue[0].first + 1, false));
  87.         }
  88.     }
  89.     for (ul i = 1; i <= n; ++i) {
  90.         std::printf("%u\n", c[i]);
  91.     }
  92.     return 0;
  93. }

D、Easy Problem

下文将简记为。 

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 59964251;
  10. const ul phi = 59870352;
  12. ul plus(ul a, ul b)
  13. {
  14.     return a + b < mod ? a + b : a + b - mod;
  15. }
  17. ul minus(ul a, ul b)
  18. {
  19.     return a < b ? a + mod - b : a - b;
  20. }
  22. ul mul(ul a, ul b)
  23. {
  24.     return ull(a) * ull(b) % mod;
  25. }
  27. ul pow(ul a, ul b)
  28. {
  29.     ul ret = 1;
  30.     while (b) {
  31.         if (b & 1) {
  32.             ret = mul(ret, a);
  33.         }
  34.         a = mul(a, a);
  35.         b >>= 1;
  36.     }
  37.     return ret;
  38. }
  40. ul T;
  42. ul m, d, k;
  44. char str[100002];
  46. ull n;
  48. const ul maxm = 1e5;
  50. ul sak[maxm + 1];
  51. ul ak[maxm + 1];
  53. std::vector<ul> prime;
  55. ul mu[maxm + 1];
  57. bool notprime[maxm + 1];
  59. int main()
  60. {
  61.     mu[1] = 1;
  62.     for (ul i = 2; i <= maxm; ++i) {
  63.         if (!notprime[i]) {
  64.             mu[i] = minus(0, 1);
  65.             prime.push_back(i);
  66.         }
  67.         for (ul p : prime) {
  68.             if (p * i > maxm) {
  69.                 break;
  70.             }
  71.             notprime[p * i] = true;
  72.             if (i % p == 0) {
  73.                 mu[p * i] = 0;
  74.                 break;
  75.             } else {
  76.                 mu[p * i] = minus(0, mu[i]);
  77.             }
  78.         }
  79.     }
  80.     std::scanf("%u", &T);
  81.     for (ul Case = 1; Case <= T; ++Case) {
  82.         std::scanf("%s", str + 1);
  83.         n = 0;
  84.         for (ul i = 1; str[i]; ++i) {
  85.             n *= 10;
  86.             n += str[i] - '0';
  87.             if (n >= phi + phi) {
  88.                 n %= phi;
  89.                 n += phi;
  90.             }
  91.         }
  92.         std::scanf("%u%u%u", &m, &d, &k);
  93.         for (ul a = 1; a * d <= m; ++a) {
  94.             ak[a] = pow(a, k);
  95.             sak[a] = plus(sak[a - 1], ak[a]);
  96.         }
  97.         ul ans = 0;
  98.         for (ul t = 1; t * d <= m; ++t) {
  99.             if (mu[t]) {
  100.                 ans = plus(ans, mul(pow(mul(ak[t], sak[m / d / t]), n), mu[t]));
  101.             }
  102.         }
  103.         ans = mul(ans, pow(pow(d, k), n));
  104.         std::printf("%u\n", ans);
  105.     }
  106.     return 0;
  107. }

E、XOR Tree

下文中表示在二进制下位的数。
首先考虑两个数列和，那么

其中
于是当两个数列相同的时候为
而原题意中不重复考虑，故为
至于的事，先直接求个下缀和，再从上向下每个点的阶祖先都减掉此位置就行。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n, k;
  10. const ul maxn = 1e5;
  12. ul cnt[maxn + 1];
  14. ul A[maxn + 1][32][32];
  16. ul a;
  18. ul f[maxn + 1];
  20. std::vector<ul> sons[maxn + 1];
  22. std::vector<ul> stack;
  24. void search(ul curr)
  25. {
  26.     ul depth = stack.size();
  27.     stack.push_back(curr);
  28.     if (depth >= k + 1) {
  29.         cnt[stack[depth - k - 1]] -= cnt[curr];
  30.         for (ul s = 0; s != 32; ++s) {
  31.             for (ul t = 0; t != 32; ++t) {
  32.                 A[stack[depth - k - 1]][s][t] -= A[curr][s][t];
  33.             }
  34.         }
  35.     }
  36.     for (ul next : sons[curr]) {
  37.         search(next);
  38.     }
  39.     stack.pop_back();
  40. }
  42. int main()
  43. {
  44.     std::scanf("%u%u", &n, &k);
  45.     for (ul i = 1; i <= n; ++i) {
  46.         std::scanf("%u", &a);
  47.         for (ul s = 0; s != 32; ++s) {
  48.             if (a >> s & 1) {
  49.                 for (ul t = 0; t != 32; ++t) {
  50.                     if (a >> t & 1) {
  51.                         A[i][s][t] = 1;
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.         cnt[i] = 1;
  57.     }
  58.     for (ul i = 2; i <= n; ++i) {
  59.         std::scanf("%u", &f[i]);
  60.         sons[f[i]].push_back(i);
  61.     }
  62.     for (ul i = n; i >= 2; --i) {
  63.         cnt[f[i]] += cnt[i];
  64.         for (ul s = 0; s != 32; ++s) {
  65.             for (ul t = 0; t != 32; ++t) {
  66.                 A[f[i]][s][t] += A[i][s][t];
  67.             }
  68.         }
  69.     }
  70.     search(1);
  71.     for (ul i = 1; i <= n; ++i) {
  72.         ull ans = 0;
  73.         for (ul s = 0; s != 32; ++s) {
  74.             for (ul t = 0; t != 32; ++t) {
  75.                 ans += ull(cnt[i]) * ull(A[i][s][t]) + ull(A[i][s][s]) * ull(A[i][t][t]) - 2 * ull(A[i][s][t]) * ull(A[i][t][t]) - 2 * ull(A[i][s][t]) * ull(A[i][s][s]) + 2 * ull(A[i][s][t]) * ull(A[i][s][t]) << s << t;
  76.             }
  77.         }
  78.         std::printf("%llu\n", ans);
  79.     }
  80.     return 0;
  81. }

F、Function!

对于相等的区间分开处理即可。
注意最大只能取到，整数的次前缀和随便怎么预处理都可以。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul mod = 998244353;
  10. ul plus(ul a, ul b)
  11. {
  12.     return a + b < mod ? a + b : a + b - mod;
  13. }
  15. ul minus(ul a, ul b)
  16. {
  17.     return a < b ? a + mod - b : a - b;
  18. }
  20. ul mul(ul a, ul b)
  21. {
  22.     return ull(a) * ull(b) % mod;
  23. }
  25. ul pow(ul a, ul b)
  26. {
  27.     ul ret = 1;
  28.     while (b) {
  29.         if (b & 1) {
  30.             ret = mul(ret, a);
  31.         }
  32.         a = mul(a, a);
  33.         b >>= 1;
  34.     }
  35.     return ret;
  36. }
  38. void exgcd(li a, li b, li& x, li& y)
  39. {
  40.     if (b) {
  41.         exgcd(b, a % b, y, x);
  42.         y -= a / b * x;
  43.     } else {
  44.         x = 1;
  45.         y = 0;
  46.     }
  47. }
  49. ul inverse(ul a)
  50. {
  51.     li x, y;
  52.     exgcd(a, mod, x, y);
  53.     return x < 0 ? x + li(mod) : x;
  54. }
  56. ul bm(const ul s[], ul cc[], ul nn)
  57. {
  58.     static ul bb[200];
  59.     static ul tt[200];
  60.     cc[0] = 1;
  61.     bb[0] = 1;
  62.     ul tl;
  63.     ul bl = 0;
  64.     ul l = 0;
  65.     ul m = 1;
  66.     ul b = 1;
  67.     for (ul n = 0; n != nn; ++n) {
  68.         ul d = 0;
  69.         for (ul i = 0; i <= l; ++i) {
  70.             d = plus(d, mul(cc[i], s[n - i]));
  71.         }
  72.         if (d == 0) {
  73.             ++m;
  74.         } else if (l + l <= n) {
  75.             std::memcpy(tt, cc, sizeof(ul) * (l + 1));
  76.             tl = l;
  77.             std::memset(&cc[l + 1], 0, sizeof(ul) * (n - l - l + 1));
  78.             l = n + 1 - l;
  79.             ul lambda = mul(inverse(b), d);
  80.             for (ul i = 0; i <= bl; ++i) {
  81.                 cc[i + m] = minus(cc[i + m], mul(lambda, bb[i]));
  82.             }
  83.             bl = tl;
  84.             std::memcpy(bb, tt, sizeof(ul) * (bl + 1));
  85.             b = d;
  86.             m = 1;
  87.         } else {
  88.             ul lambda = mul(inverse(b), d);
  89.             for (ul i = 0; i <= bl; ++i) {
  90.                 cc[i + m] = minus(cc[i + m], mul(lambda, bb[i]));
  91.             }
  92.             ++m;
  93.         }
  94.     }
  95.     return l;
  96. }
  99. ul linearrec(const ul s[], const ul tcc[], ul len, ull n)
  100. {
  101.     static ul cc[200];
  102.     static ul ret[200];
  103.     static ul temp[200];
  104.     if (n < len) {
  105.         return s[n];
  106.     }
  107.     std::memcpy(cc, tcc, sizeof(ul) * (len + 1));
  108.     std::memset(ret, 0, sizeof(ul) * len);
  109.     ret[0] = 1;
  110.     ul dret = 0;
  111.     for (ull t = ull(1) << 63 - __builtin_clzll(n); t; t >>= 1) {
  112.         std::memset(temp, 0, sizeof(ul) * (dret + dret + 1));
  113.         for (ul i = 0; i <= dret; ++i) {
  114.             temp[i + i] = plus(temp[i + i], mul(ret[i], ret[i]));
  115.             for (ul j = i + 1; j <= dret; ++j) {
  116.                 ul tp = mul(ret[i], ret[j]);
  117.                 temp[i + j] = plus(temp[i + j], plus(tp, tp));
  118.             }
  119.         }
  120.         for (ul i = dret + dret; i >= len; --i) {
  121.             ul lambda = minus(0, temp[i]);
  122.             if (!lambda) {
  123.                 continue;
  124.             }
  125.             for (ul j = 0; j <= len; ++j) {
  126.                 temp[i - j] = plus(temp[i - j], mul(cc[j], lambda));
  127.             }
  128.         }
  129.         std::memcpy(ret, temp, sizeof(ul) * len);
  130.         dret = std::min(dret + dret, len - ul(1));
  131.         if (t & n) {
  132.             for (ul i = dret + 1; i; --i) {
  133.                 ret[i] = ret[i - 1];
  134.             }
  135.             ret[0] = 0;
  136.             ++dret;
  137.             if (dret == len) {
  138.                 ul lambda = minus(0, ret[len]);
  139.                 if (lambda) {
  140.                     for (ul i = 0; i <= len; ++i) {
  141.                         ret[len - i] = plus(ret[len - i], mul(cc[i], lambda));
  142.                     }
  143.                 }
  144.                 --dret;
  145.             }
  146.         }
  147.     }
  148.     ul out = 0;
  149.     for (ul i = 0; i != len; ++i) {
  150.         out = plus(out, mul(s[i], ret[i]));
  151.     }
  152.     return out;
  153. }
  155. const ul maxt = 40;
  157. ul s[maxt + 1][maxt + maxt + 4];
  159. ul cc[maxt + 1][maxt + 3];
  161. ul len[maxt + 1];
  163. ull n;
  165. using lf = double;
  167. ull powroot(ull a, ul b)
  168. {
  169.     ull tmp = std::llround(std::pow(a, lf(1) / lf(b)));
  170.     if (std::pow(tmp, b) > n) {
  171.         --tmp;
  172.     }
  173.     return tmp;
  174. }
  176. const ul inv2 = mod + 1 >> 1;
  178. int main()
  179. {
  180.     std::scanf("%llu", &n);
  181.     for (ul t = 2; (ull(1) << t - 1) <= n; ++t) {
  182.         for (ul x = 1; x <= t + t + 3; ++x) {
  183.             s[t][x] = plus(s[t][x - 1], pow(x, t));
  184.         }
  185.         len[t] = bm(s[t], cc[t], t + t + 4);
  186.     }
  187.     ul ans = 0;
  188.     for (ul k = 1; (ull(1) << k) <= n; ++k) {
  189.         ull l = powroot(n, k + 1) + 1;
  190.         ull r = powroot(n, k);
  191.         ans = plus(ans, mul(k, mul((n + 1) % mod, mul((l + r) % mod, mul((r - l + 1) % mod, inv2)))));
  192.         ans = minus(ans, minus(linearrec(s[k + 1], cc[k + 1], len[k + 1], r), 1));
  193.     }
  194.     std::printf("%u\n", ans);
  195.     return 0;
  196. }

G、Pot!!

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n, q;
  10. const ul sz = 1 << 17;
  12. li tree[11][sz << 1];
  14. void change(ul l, ul r, li val, li tree[])
  15. {
  16.     li temp;
  17.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  18.         if (~l & 1) {
  19.             tree[l ^ 1] += val;
  20.         }
  21.         if (r & 1) {
  22.             tree[r ^ 1] += val;
  23.         }
  24.         temp = std::max(tree[l], tree[l ^ 1]);
  25.         tree[l] -= temp;
  26.         tree[l ^ 1] -= temp;
  27.         tree[l >> 1] += temp;
  28.         temp = std::max(tree[r], tree[r ^ 1]);
  29.         tree[r] -= temp;
  30.         tree[r ^ 1] -= temp;
  31.         tree[r >> 1] += temp;
  32.     }
  33.     for (ul i = l; i >> 1; i >>= 1) {
  34.         temp = std::max(tree[i], tree[i ^ 1]);
  35.         tree[i] -= temp;
  36.         tree[i ^ 1] -= temp;
  37.         tree[i >> 1] += temp;
  38.     }
  39. }
  41. li& maxx(li& a, li b)
  42. {
  43.     return a = std::max(a, b);
  44. }
  46. li query(ul l, ul r, const li tree[])
  47. {
  48.     li lans = -1e7;
  49.     li rans = -1e7;
  50.     for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
  51.         if (~l & 1) {
  52.             maxx(lans, tree[l ^ 1]);
  53.         }
  54.         if (r & 1) {
  55.             maxx(rans, tree[r ^ 1]);
  56.         }
  57.         lans += tree[l >> 1];
  58.         rans += tree[r >> 1];
  59.     }
  60.     li ans = std::max(lans, rans);
  61.     for (ul i = l; i >> 1; i >>= 1) {
  62.         ans += tree[i >> 1];
  63.     }
  64.     return ans;
  65. }
  67. char str[20];
  69. int main()
  70. {
  71.     std::scanf("%u%u", &n, &q);
  72.     for (ul i = 1; i <= q; ++i) {
  73.         std::scanf("%s", str);
  74.         if (str[1] == 'U') {
  75.             ul l, r, x;
  76.             std::scanf("%u%u%u", &l, &r, &x);
  77.             for (ul p : {2, 3, 5, 7}) {
  78.                 ul t = 0;
  79.                 while (x % p == 0) {
  80.                     x /= p;
  81.                     ++t;
  82.                 }
  83.                 change(l, r, t, tree[p]);
  84.             }
  85.         } else {
  86.             ul l, r;
  87.             std::scanf("%u%u", &l, &r);
  88.             std::printf("ANSWER %d\n", std::max(std::max(query(l, r, tree[2]), query(l, r, tree[3])), std::max(query(l, r, tree[5]), query(l, r, tree[7]))));
  89.         }
  90.     }
  91.     return 0;
  92. }

H、Delivery Route

强连通分量内直接狄克斯特拉，强连通分量外按照拓扑序处理。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul n, x, y, s;
  10. const ul maxn = 25000;
  12. ul rk[maxn + 1];
  13. ul fa[maxn + 1];
  15. ul getfather(ul x)
  16. {
  17.     return fa[x] == x ? x : fa[x] = getfather(fa[x]);
  18. }
  20. void connect(ul a, ul b)
  21. {
  22.     a = getfather(a);
  23.     b = getfather(b);
  24.     if (a == b) {
  25.         return;
  26.     }
  27.     if (rk[a] > rk[b]) {
  28.         fa[b] = a;
  29.     } else if (rk[b] > rk[a]) {
  30.         fa[a] = b;
  31.     } else {
  32.         fa[a] = b;
  33.         ++rk[b];
  34.     }
  35. }
  37. class edge_t {
  38. public:
  39.     ul to = 0;
  40.     li c = 0;
  41.     edge_t()=default;
  42.     edge_t(ul a, li b): to(a), c(b) {}
  43. };
  45. std::vector<edge_t> edges[maxn + 1];
  47. std::vector<ul> bigedges[maxn + 1];
  49. ul cnt[maxn + 1];
  51. std::vector<ul> order;
  53. std::deque<ul> queue;
  55. bool operator<(const edge_t& a, const edge_t& b)
  56. {
  57.     return a.c > b.c;
  58. }
  60. std::priority_queue<edge_t> heap[maxn + 1];
  62. li dis[maxn + 1];
  64. const li inf = 250000001;
  66. int main()
  67. {
  68.     std::scanf("%u%u%u%u", &n, &x, &y, &s);
  69.     for (ul i = 1; i <= n; ++i) {
  70.         dis[i] = inf;
  71.         fa[i] = i;
  72.     }
  73.     for (ul i = 1; i <= x; ++i) {
  74.         ul a, b, c;
  75.         std::scanf("%u%u%u", &a, &b, &c);
  76.         edges[a].push_back(edge_t(b, c));
  77.         edges[b].push_back(edge_t(a, c));
  78.         connect(a, b);
  79.     }
  80.     for (ul i = 1; i <= y; ++i) {
  81.         ul a, b;
  82.         li c;
  83.         std::scanf("%u%u%d", &a, &b, &c);
  84.         edges[a].push_back(edge_t(b, c));
  85.         bigedges[getfather(a)].push_back(getfather(b));
  86.         ++cnt[getfather(b)];
  87.     }
  88.     for (ul i = 1; i <= n; ++i) {
  89.         if (getfather(i) != i) {
  90.             continue;
  91.         }
  92.         if (cnt[i] == 0) {
  93.             queue.push_back(i);
  94.         }
  95.     }
  96.     while (queue.size()) {
  97.         ul curr = queue.front();
  98.         queue.pop_front();
  99.         order.push_back(curr);
  100.         for (ul next : bigedges[curr]) {
  101.             --cnt[next];
  102.             if (!cnt[next]) {
  103.                 queue.push_back(next);
  104.             }
  105.         }
  106.     }
  107.     dis[s] = 0;
  108.     heap[getfather(s)].push(edge_t(s, 0));
  109.     for (const auto t : order) {
  110.         while (heap[t].size()) {
  111.             auto curr = heap[t].top();
  112.             heap[t].pop();
  113.             if (dis[curr.to] != curr.c) {
  114.                 continue;
  115.             }
  116.             for (const auto& next : edges[curr.to]) {
  117.                 if (dis[next.to] > curr.c + next.c) {
  118.                     dis[next.to] = curr.c + next.c;
  119.                     heap[getfather(next.to)].push(edge_t(next.to, curr.c + next.c));
  120.                 }
  121.             }
  122.         }
  123.     }
  124.     for (ul i = 1; i <= n; ++i) {
  125.         if (dis[i] == inf) {
  126.             std::printf("NO PATH\n");
  127.         } else {
  128.             std::printf("%d\n", dis[i]);
  129.         }
  130.     }
  131.     return 0;
  132. }

I、Base62

简单题

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using vul = std::vector<ul>;
  9. ul x, y;
  11. vul operator*(const vul& a, const vul& b)
  12. {
  13.     static vul ret;
  14.     ret.resize(0);
  15.     if (a.empty() || b.empty()) {
  16.         return ret;
  17.     }
  18.     ret.resize(a.size() + b.size() - 1, 0);
  19.     for (ul i = 0; i != a.size(); ++i) {
  20.         if (a[i]) {
  21.             for (ul j = 0; j != b.size(); ++j) {
  22.                 ret[i + j] += a[i] * b[j];
  23.             }
  24.         }
  25.     }
  26.     for (ul i = 0; i != ret.size(); ++i) {
  27.         ul k = ret[i] / y;
  28.         ret[i] %= y;
  29.         if (k) {
  30.             if (ret.size() == i + 1) {
  31.                 ret.push_back(0);
  32.             }
  33.             ret[i + 1] += k;
  34.         }
  35.     }
  36.     return ret;
  37. }
  39. vul operator+(const vul& a, const vul& b)
  40. {
  41.     static vul ret;
  42.     ret.resize(std::max(a.size(), b.size()));
  43.     for (ul i = 0; i != ret.size(); ++i) {
  44.         ret[i] = (i < a.size() ? a[i] : ul(0)) + (i < b.size() ? b[i] : ul(0));
  45.     }
  46.     for (ul i = 0; i != ret.size(); ++i) {
  47.         ul k = ret[i] / y;
  48.         ret[i] %= y;
  49.         if (k) {
  50.             if (ret.size() == i + 1) {
  51.                 ret.push_back(0);
  52.             }
  53.             ret[i + 1] += k;
  54.         }
  55.     }
  56.     return ret;
  57. }
  59. vul xv, currv, pv;
  61. ul ctv[256];
  62. ul vtc[62];
  64. char z[121];
  66. int main()
  67. {
  68.     std::scanf("%u%u", &x, &y);
  69.     while (x) {
  70.         xv.push_back(x % y);
  71.         x /= y;
  72.     }
  73.     for (ul i = 0; i <= 9; ++i) {
  74.         ctv['0' + i] = i;
  75.         vtc[i] = '0' + i;
  76.     }
  77.     for (ul i = 0; i <= 25; ++i) {
  78.         ctv['A' + i] = 10 + i;
  79.         vtc[10 + i] = 'A' + i;
  80.     }
  81.     for (ul i = 0; i <= 25; ++i) {
  82.         ctv['a' + i] = 36 + i;
  83.         vtc[36 + i] = 'a' + i;
  84.     }
  85.     std::scanf("%s", z);
  86.     for (ul i = 0; z[i]; ++i) {
  87.         ul p = ctv[z[i]];
  88.         pv.resize(0);
  89.         while (p) {
  90.             pv.push_back(p % y);
  91.             p /= y;
  92.         }
  93.         currv = currv * xv + pv;
  94.     }
  95.     if (currv.empty()) {
  96.         std::printf("0\n");
  97.         return 0;
  98.     }
  99.     for (ul i = currv.size() - 1; ~i; --i) {
  100.         std::putchar(char(vtc[currv[i]]));
  101.     }
  102.     std::putchar('\n');
  103.     return 0;
  104. }

J、Toad’s Travel

首先注意到，实际就是要求给每条边赋权，使得所有点的度数都是偶数，或者有两个奇度点，且其中一个是，那么显然所有边最少被走一次，最多被走两次。那么可以考虑动态规划。代码中ans_t的数组v[][]，表示根当前度数奇偶性为，根之外有个奇度点的最小花费，而ans2_t中的数组v[][][]是给“有两个根的结构”准备的，其中和分别表示两头的度数的奇偶性，表示两头之外有多少个奇度点。至于深搜过程，实际就是点双连通分量的写法，dfn[]表示的深搜序，low[]表示从出发走一些（可以是零条）树边最多再走一条回边能到达的深搜序最小的点的深搜序。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. const ul maxn = 1e5;
  10. ul n, m;
  12. class edge_t {
  13. public:
  14.     ul to = 0;
  15.     ul len = 0;
  16.     edge_t()=default;
  17.     edge_t(ul a, ul b): to(a), len(b) {}
  18. };
  20. std::vector<edge_t> edges[maxn + 1];
  22. ul dfn[maxn + 1];
  23. ul low[maxn + 1];
  25. const ull inf = 1e18;
  27. class ans_t {
  28. public:
  29.     ull v[2][2];
  30.     ans_t() {
  31.         for (ul a : {0, 1}) {
  32.             for (ul b : {0, 1}) {
  33.                 v[a][b] = inf;
  34.             }
  35.         }
  36.     }
  37.     ans_t(ul x) {
  38.         for (ul a : {0, 1}) {
  39.             for (ul b : {0, 1}) {
  40.                 v[a][b] = inf;
  41.             }
  42.         }
  43.         v[0][0] = 0;
  44.     }
  45.     ull* operator[](ul x) {
  46.         return v[x];
  47.     }
  48.     const ull* operator[](ul x) const {
  49.         return v[x];
  50.     }
  51. };
  53. class ans2_t {
  54. public:
  55.     ull v[2][2][2];
  56.     ans2_t() {
  57.         for (ul a : {0, 1}) {
  58.             for (ul b : {0, 1}) {
  59.                 for (ul c : {0, 1}) {
  60.                     v[a][b][c] = inf;
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     using ttt = ull[2];
  66.     ttt* operator[](ul x) {
  67.         return v[x];
  68.     }
  69.     const ttt* operator[](ul x) const {
  70.         return v[x];
  71.     }
  72. };
  74. ans_t ans[maxn + 1];
  76. ans_t deal1(const ans_t& a, const ans_t& b, ul len)
  77. {
  78.     ans_t ret;
  79.     for (ul ar : {0, 1}) {
  80.         for (ul al : {0, 1}) {
  81.             if (a[ar][al] == inf) {
  82.                 continue;
  83.             }
  84.             for (ul br : {0, 1}) {
  85.                 for (ul bl : {0, 1}) {
  86.                     if (al && bl) {
  87.                         continue;
  88.                     }
  89.                     if (b[br][bl] == inf) {
  90.                         continue;
  91.                     }
  92.                     for (ul w : {1, 2}) {
  93.                         ul cr = (ar ^ w) & 1;
  94.                         ul cl = al + ((br ^ w) & 1) + bl;
  95.                         if (cl >= 2) {
  96.                             continue;
  97.                         }
  98.                         ret[cr][cl] = std::min(ret[cr][cl], a[ar][al] + b[br][bl] + w * len);
  99.                     }
  100.                 }
  101.             }
  102.         }
  103.     }
  104.     return ret;
  105. }
  107. ans2_t deal2(const ans_t& a, const ans_t& b, ul len)
  108. {
  109.     ans2_t ret;
  110.     for (ul ar : {0, 1}) {
  111.         for (ul al : {0, 1}) {
  112.             if (a[ar][al] == inf) {
  113.                 continue;
  114.             }
  115.             for (ul br : {0, 1}) {
  116.                 for (ul bl : {0, 1}) {
  117.                     if (al && bl) {
  118.                         continue;
  119.                     }
  120.                     if (b[br][bl] == inf) {
  121.                         continue;
  122.                     }
  123.                     for (ul w : {1, 2}) {
  124.                         ul cr1 = (ar ^ w) & 1;
  125.                         ul cr2 = (br ^ w) & 1;
  126.                         ul cl = al + bl;
  127.                         ret[cr1][cr2][cl] = std::min(ret[cr1][cr2][cl], a[ar][al] + b[br][bl] + w * len);
  128.                     }
  129.                 }
  130.             }
  131.         }
  132.     }
  133.     return ret;
  134. }
  136. ans2_t deal3(const ans_t& a, const ans2_t& b, ul len)
  137. {
  138.     ans2_t ret;
  139.     for (ul ar : {0, 1}) {
  140.         for (ul al : {0, 1}) {
  141.             if (a[ar][al] == inf) {
  142.                 continue;
  143.             }
  144.             for (ul br1 : {0, 1}) {
  145.                 for (ul br2 : {0, 1}) {
  146.                     for (ul bl : {0, 1}) {
  147.                         if (al && bl) {
  148.                             continue;
  149.                         }
  150.                         if (b[br1][br2][bl] == inf) {
  151.                             continue;
  152.                         }
  153.                         for (ul w : {1, 2}) {
  154.                             ul cr1 = (ar ^ w) & 1;
  155.                             ul cr2 = br2;
  156.                             ul cl = al + bl + ((br1 ^ w) & 1);
  157.                             if (cl >= 2) {
  158.                                 continue;
  159.                             }
  160.                             ret[cr1][cr2][cl] = std::min(ret[cr1][cr2][cl], a[ar][al] + b[br1][br2][bl] + w * len);
  161.                         }
  162.                     }
  163.                 }
  164.             }
  165.         }
  166.     }
  167.     return ret;
  168. }
  170. ans_t deal4(const ans_t& a, const ans2_t& b, ul len)
  171. {
  172.     ans_t ret;
  173.     for (ul ar : {0, 1}) {
  174.         for (ul al : {0, 1}) {
  175.             if (a[ar][al] == inf) {
  176.                 continue;
  177.             }
  178.             for (ul br1 : {0, 1}) {
  179.                 for (ul br2 : {0, 1}) {
  180.                     for (ul bl : {0, 1}) {
  181.                         if (al && bl) {
  182.                             continue;
  183.                         }
  184.                         if (b[br1][br2][bl] == inf) {
  185.                             continue;
  186.                         }
  187.                         for (ul w : {1, 2}) {
  188.                             ul cr = (ar ^ w ^ br2) & 1;
  189.                             ul cl = al + bl + ((br1 ^ w) & 1);
  190.                             if (cl >= 2) {
  191.                                 continue;
  192.                             }
  193.                             ret[cr][cl] = std::min(ret[cr][cl], a[ar][al] + b[br1][br2][bl] + w * len);
  194.                         }
  195.                     }
  196.                 }
  197.             }
  198.         }
  199.     }
  200.     return ret;
  201. }
  203. ul tim;
  205. const ans_t zero(0);
  207. void search(ul v, ul u)
  208. {
  209.     static std::vector<edge_t> stack;
  210.     ++tim;
  211.     dfn[v] = tim;
  212.     low[v] = dfn[v];
  213.     ans[v] = zero;
  214.     for (const auto& e : edges[v]) {
  215.         ul w = e.to;
  216.         if (!dfn[w]) {
  217.             stack.push_back(e);
  218.             search(w, v);
  219.             low[v] = std::min(low[v], low[w]);
  220.             if (low[w] == dfn[v]) {
  221.                 auto laste = stack.back();
  222.                 stack.pop_back();
  223.                 ans2_t tmp = deal2(ans[stack.back().to], zero, laste.len);
  224.                 while (stack.back().to != w) {
  225.                     laste = stack.back();
  226.                     stack.pop_back();
  227.                     tmp = deal3(ans[stack.back().to], tmp, laste.len);
  228.                 }
  229.                 stack.pop_back();
  230.                 ans[v] = deal4(ans[v], tmp, e.len);
  231.             } else if (low[w] > dfn[v]) {
  232.                 ans[v] = deal1(ans[v], ans[w], e.len);
  233.                 stack.pop_back();
  234.             }
  235.         } else if (dfn[w] < dfn[v] && w != u) {
  236.             stack.push_back(e);
  237.             low[v] = std::min(low[v], dfn[w]);
  238.         }
  239.     }
  240. }
  242. int main()
  243. {
  244.     std::scanf("%u%u", &n, &m);
  245.     for (ul i = 1; i <= m; ++i) {
  246.         ul u, v, w;
  247.         std::scanf("%u%u%u", &u, &v, &w);
  248.         edges[u].push_back(edge_t(v, w));
  249.         edges[v].push_back(edge_t(u, w));
  250.     }
  251.     search(1, 0);
  252.     std::printf("%llu\n", std::min(ans[1][0][0], ans[1][1][1]));
  253.     return 0;
  254. }

K、Largest Common Submatrix

由于题意说了任何数在一个数组中都只出现一次，所以此题实际和求零一数组的最大全零子数组是一样的做法。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. using pulul = std::pair<ul, ul>;
  10. ul n, m;
  12. const ul maxn = 1000;
  13. const ul maxm = 1000;
  15. ul a[maxn + 1][maxm + 2];
  17. ul b[maxn + 1][maxm + 2];
  19. pulul pos[maxn * maxm + 1];
  21. ul h[maxn + 1][maxm + 1];
  23. ul l[maxn + 1][maxm + 1];
  25. std::vector<pulul> stack;
  27. int main()
  28. {
  29.     std::scanf("%u%u", &n, &m);
  30.     for (ul i = 1; i <= n; ++i) {
  31.         for (ul j = 1; j <= m; ++j) {
  32.             std::scanf("%u", &a[i][j]);
  33.             pos[a[i][j]] = pulul(i, j);
  34.         }
  35.     }
  36.     ul ans = 0;
  37.     for (ul i = 1; i <= n; ++i) {
  38.         stack.resize(0);
  39.         stack.push_back(pulul(0, 0));
  40.         for (ul j = 1; j <= m; ++j) {
  41.             std::scanf("%u", &b[i][j]);
  42.             if (a[pos[b[i][j]].first - 1][pos[b[i][j]].second] == b[i - 1][j]) {
  43.                 h[i][j] = h[i - 1][j] + 1;
  44.             } else {
  45.                 h[i][j] = 1;
  46.             }
  47.             if (a[pos[b[i][j]].first][pos[b[i][j]].second - 1] != b[i][j - 1]) {
  48.                 stack.resize(0);
  49.                 stack.push_back(pulul(j - 1, 0));
  50.             }
  51.             while (stack.back().second >= h[i][j]) {
  52.                 stack.pop_back();
  53.             }
  54.             l[i][j] = stack.back().first + 1;
  55.             stack.push_back(pulul(j, h[i][j]));
  56.         }
  57.         stack.resize(0);
  58.         stack.push_back(pulul(m + 1, 0));
  59.         for (ul j = m; j >= 1; --j) {
  60.             if (a[pos[b[i][j]].first][pos[b[i][j]].second + 1] != b[i][j + 1]) {
  61.                 stack.resize(0);
  62.                 stack.push_back(pulul(j + 1, 0));
  63.             }
  64.             while (stack.back().second >= h[i][j]) {
  65.                 stack.pop_back();
  66.             }
  67.             ul r = stack.back().first - 1;
  68.             ans = std::max((r - l[i][j] + 1) * h[i][j], ans);
  69.             stack.push_back(pulul(j, h[i][j]));
  70.         }
  71.     }
  72.     std::printf("%u\n", ans);
  73.     return 0;
  74. }

L、Xian Xiang

预处理之后记忆化搜索

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. using pulul = std::pair<ul, ul>;
  10. ul T;
  12. ul n, m, k;
  14. const ul maxn = 7;
  15. const ul maxm = 7;
  16. const ul maxk = 5;
  18. char str[maxn + 1][maxm + 1][maxk + 1];
  20. ul tot;
  22. const ul maxtot = 18;
  24. pulul pos[maxtot + 1];
  26. ul s[maxk + 1];
  28. ul val[maxtot][maxtot + 1];
  30. ul ban[maxtot][maxtot + 1][2];
  32. ul ans[1 << maxtot];
  34. ul already[1 << maxtot];
  36. ul tim = 0;
  38. void search(ul curr)
  39. {
  40.     if (already[curr] == tim) {
  41.         return;
  42.     }
  43.     already[curr] = tim;
  44.     ans[curr] = 0;
  45.     for (ul mi = curr; __builtin_popcount(mi) >= 2; mi &= ~(1 << __builtin_ctz(mi))) {
  46.         ul i = __builtin_ctz(mi) + 1;
  47.         for (ul mj = mi & ~(1 << i - 1); mj; mj &= ~(1 << __builtin_ctz(mj))) {
  48.             ul j = __builtin_ctz(mj) + 1;
  49.             if ((curr & ban[i][j][0]) && (curr & ban[i][j][1])) {
  50.                 continue;
  51.             }
  52.             ul next = curr & ~(1 << i - 1) & ~(1 << j - 1);
  53.             search(next);
  54.             ans[curr] = std::max(ans[curr], ans[next] + val[i][j]);
  55.         }
  56.     }
  57. }
  59. int main()
  60. {
  61.     std::scanf("%u", &T);
  62.     for (ul Case = 1; Case <= T; ++Case) {
  63.         std::scanf("%u%u%u", &n, &m, &k);
  64.         tot = 0;
  65.         for (ul i = 1; i <= n; ++i) {
  66.             for (ul j = 1; j <= m; ++j) {
  67.                 std::scanf("%s", str[i][j]);
  68.                 if (str[i][j][0] != '-') {
  69.                     ++tot;
  70.                     pos[tot] = pulul(i, j);
  71.                 }
  72.             }
  73.         }
  74.         for (ul i = 0; i <= k; ++i) {
  75.             std::scanf("%u", &s[i]);
  76.         }
  77.         for (ul i = 1; i + 1 <= tot; ++i) {
  78.             for (ul j = i + 1; j <= tot; ++j) {
  79.                 ul cnt = 0;
  80.                 for (ul q = 0; q != k; ++q) {
  81.                     if (str[pos[i].first][pos[i].second][q] == str[pos[j].first][pos[j].second][q]) {
  82.                         ++cnt;
  83.                     }
  84.                 }
  85.                 val[i][j] = s[cnt];
  86.                 ban[i][j][0] = ban[i][j][1] = 0;
  87.                 for (ul q = 1; q <= tot; ++q) {
  88.                     if (q == i || q == j) {
  89.                         continue;
  90.                     }
  91.                     if (pos[q].first == pos[i].first && (pos[q].second >= pos[i].second) == (pos[q].second <= pos[j].second)) {
  92.                         ban[i][j][0] |= 1 << q - 1;
  93.                     }
  94.                     if (pos[q].second == pos[j].second && (pos[q].first >= pos[i].first) == (pos[q].first <= pos[j].first)) {
  95.                         ban[i][j][0] |= 1 << q - 1;
  96.                     }
  97.                     if (pos[q].first == pos[j].first && (pos[q].second >= pos[i].second) == (pos[q].second <= pos[j].second)) {
  98.                         ban[i][j][1] |= 1 << q - 1;
  99.                     }
  100.                     if (pos[q].second == pos[i].second && (pos[q].first >= pos[i].first) == (pos[q].first <= pos[j].first)) {
  101.                         ban[i][j][1] |= 1 << q - 1;
  102.                     }
  103.                 }
  104.             }
  105.         }
  106.         ++tim;
  107.         already[0] = tim;
  108.         ans[0] = 0;
  109.         search((1 << tot) - 1);
  110.         std::printf("%u\n", ans[(1 << tot) - 1]);
  111.     }
  112.     return 0;
  113. }

M、Crazy Cake

设个点的，不考虑旋转一致性的问题的答案为。现在考虑用伯恩赛德引理，考虑将点转不变的方案数怎么求。首先这里定为的因数，如果不是，那么直接取为和的最大公因数即可。
注意，只要，那么转不变的方案数就等于转不变的方案数（这一点自己证明），记为。于是，输入为时的答案就应该是：

现在考虑和怎么求。
显然有如下的递推式（自己证）：
该式可改写为
关于，
该式可改写为
现在定义，于是
即
解之得

设，那么，于是

接着处理，
即
设，那么，于是

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  7. using pulul = std::pair<ul, ul>;
  9. const ul mod = 1e9 + 7;
  11. const ul maxn = 1e6;
  13. ul plus(ul a, ul b)
  14. {
  15.     return a + b < mod ? a + b : a + b - mod;
  16. }
  18. ul minus(ul a, ul b)
  19. {
  20.     return a < b ? a + mod - b : a - b;
  21. }
  23. ul mul(ul a, ul b)
  24. {
  25.     return ull(a) * ull(b) % mod;
  26. }
  28. void exgcd(li a, li b, li& x, li& y)
  29. {
  30.     if (b) {
  31.         exgcd(b, a % b, y, x);
  32.         y -= a / b * x;
  33.     } else {
  34.         x = 1;
  35.         y = 0;
  36.     }
  37. }
  39. ul inverse(ul a)
  40. {
  41.     li x, y;
  42.     exgcd(a, mod, x, y);
  43.     return x < 0 ? x + li(mod) : x;
  44. }
  46. ul h[maxn + 1];
  48. ul fac[maxn + 1];
  50. ul fiv[maxn + 1];
  52. ul inv[maxn + 1];
  54. ul f[maxn + 1];
  56. ul g[maxn + 1];
  58. ul low[maxn + 1];
  60. std::vector<ul> prime;
  62. ul phi[maxn + 1];
  64. ul T;
  66. std::vector<pulul> stack;
  68. ul ans;
  70. ul cnt[30];
  72. ul n;
  74. void search(ul i, ul k)
  75. {
  76.     if (i == stack.size()) {
  77.         if (k != 1) {
  78.             ans = plus(ans, mul(phi[k], g[n / k]));
  79.         }
  80.         return;
  81.     }
  82.     for (cnt[i] = 0; cnt[i] <= stack[i].second; ++cnt[i], k *= stack[i].first) {
  83.         search(i + 1, k);
  84.     }
  85. }
  87. int main()
  88. {
  89.     fac[0] = 1;
  90.     for (ul i = 1; i <= maxn; ++i) {
  91.         fac[i] = mul(fac[i - 1], i);
  92.     }
  93.     fiv[maxn] = inverse(fac[maxn]);
  94.     for (ul i = maxn; i >= 1; --i) {
  95.         fiv[i - 1] = mul(fiv[i], i);
  96.         inv[i] = mul(fiv[i], fac[i - 1]);
  97.     }
  98.     h[0] = 1;
  99.     h[1] = minus(0, 6);
  100.     h[2] = minus(0, 16);
  101.     for (ul n = 2; n + 1 <= maxn; ++n) {
  102.         h[n + 1] = mul(inv[2], mul(inv[n + 1], minus(mul(24 * n - 12, h[n]), mul(8 * n - 16, h[n - 1]))));
  103.     }
  104.     f[1] = mul(3, inv[2]);
  105.     f[2] = minus(0, 1);
  106.     for (ul n = 0; n + 1 <= maxn; ++n) {
  107.         f[n + 1] = minus(f[n + 1], mul(h[n], inv[2]));
  108.     }
  109.     h[0] = 1;
  110.     h[1] = 6;
  111.     h[2] = 52;
  112.     for (ul n = 2; n + 1 <= maxn; ++n) {
  113.         h[n + 1] = mul(inv[2], mul(inv[n + 1], minus(mul(24 * n + 12, h[n]), mul(8 * n, h[n - 1]))));
  114.     }
  115.     for (ul n = 0; n + 1 <= maxn; ++n) {
  116.         g[n + 1] = plus(h[n], h[n]);
  117.     }
  118.     for (ul i = 2; i <= maxn; ++i) {
  119.         if (!low[i]) {
  120.             low[i] = i;
  121.             prime.push_back(i);
  122.             phi[i] = i - 1;
  123.         }
  124.         for (ul p : prime) {
  125.             if (i * p > maxn) {
  126.                 break;
  127.             }
  128.             low[i * p] = p;
  129.             if (i % p == 0) {
  130.                 phi[i * p] = phi[i] * p;
  131.                 break;
  132.             } else {
  133.                 phi[i * p] = phi[i] * (p - 1);
  134.             }
  135.         }
  136.     }
  137.     std::scanf("%u", &T);
  138.     for (ul Case = 1; Case <= T; ++Case) {
  139.         std::scanf("%u", &n);
  140.         ans = f[n];
  141.         stack.resize(0);
  142.         ul tn = n;
  143.         while (tn != 1) {
  144.             if (stack.empty() || stack.back().first != low[tn]) {
  145.                 stack.push_back(pulul(low[tn], 0));
  146.             }
  147.             ++stack.back().second;
  148.             tn /= low[tn];
  149.         }
  150.         search(0, 1);
  151.         std::printf("%u\n", mul(ans, inv[n]));
  152.     }
  153.     return 0;
  154. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注