[关闭]
@qq290637843 2020-11-24T20:30:02.000000Z 字数 16541 阅读 246

2020杭电第六场

A、Road To The 3rd Building 6827

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul mod = 1e9 + 7;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + mod - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % mod;
  27. }
  29. ul T;
  30. ul n;
  32. const ul maxn = 2e5;
  34. ul inv[maxn + 2];
  35. ul H[maxn + 2];
  37. int main()
  38. {
  39.     std::ios::sync_with_stdio(false);
  40.     std::cin.tie(0);
  41.     iss.tie(0);
  42.     oss.tie(0);
  43.     std::getline(std::cin, instr, char(0));
  44.     iss.str(instr);
  45.     inv[1] = 1;
  46.     H[1] = 1;
  47.     for (ul i = 2; i <= maxn + 1; ++i) {
  48.         inv[i] = minus(0, mul(mod / i, inv[mod % i]));
  49.         H[i] = plus(H[i - 1], inv[i]);
  50.     }
  51.     iss >> T;
  52.     for (ul Case = 1; Case <= T; ++Case) {
  53.         iss >> n;
  54.         ul ans = 0;
  55.         for (ul k = 1; k <= n; ++k) {
  56.             ul t;
  57.             iss >> t;
  58.             ul alpha = 0;
  59.             alpha = plus(alpha, mul(n + 1, H[n]));
  60.             alpha = minus(alpha, mul(k, H[k]));
  61.             alpha = minus(alpha, mul(n + 1 - k, H[n - k]));
  62.             ans = plus(ans, mul(alpha, t));
  63.         }
  64.         ans = mul(mul(ans, mul(inv[n + 1], inv[n])), 2);
  65.         oss << ans << '\n';
  66.     }
  67.     std::cout << oss.str();
  68.     return 0;
  69. }

B、Little Rabbit's Equation 6828

简单题

  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. std::string s;
  14. std::vector<ul> a, b, c;
  16. const ul base = 998244353;
  18. ul plus(ul a, ul b)
  19. {
  20.     return a + b < base ? a + b : a + b - base;
  21. }
  23. ul minus(ul a, ul b)
  24. {
  25.     return a < b ? a + base - b : a - b;
  26. }
  28. ul mul(ul a, ul b)
  29. {
  30.     return ull(a) * ull(b) % base;
  31. }
  33. void exgcd(li a, li b, li& x, li& y)
  34. {
  35.     if (b) {
  36.         exgcd(b, a % b, y, x);
  37.         y -= a / b * x;
  38.     } else {
  39.         x = 1;
  40.         y = 0;
  41.     }
  42. }
  44. ul inverse(ul a)
  45. {
  46.     li x, y;
  47.     exgcd(a, base, x, y);
  48.     return x < 0 ? x + li(base) : x;
  49. }
  51. bool check(char x)
  52. {
  53.     return '0' <= x && x <= '9' || 'A' <= x && x <= 'F';
  54. }
  56. ul encode[256];
  58. bool check(ul r, char op)
  59. {
  60.     ul aa = 0, bb = 0, cc = 0;
  61.     for (auto t : a) {
  62.         if (t >= r) {
  63.             return false;
  64.         }
  65.         aa = mul(aa, r);
  66.         aa = plus(aa, t);
  67.     }
  68.     for (auto t : b) {
  69.         if (t >= r) {
  70.             return false;
  71.         }
  72.         bb = mul(bb, r);
  73.         bb = plus(bb, t);
  74.     }
  75.     for (auto t : c) {
  76.         if (t >= r) {
  77.             return false;
  78.         }
  79.         cc = mul(cc, r);
  80.         cc = plus(cc, t);
  81.     }
  82.     if (op == '+') {
  83.         return plus(aa, bb) == cc;
  84.     } else if (op == '-') {
  85.         return minus(aa, bb) == cc;
  86.     } else if (op == '*') {
  87.         return mul(aa, bb) == cc;
  88.     } else {
  89.         return mul(aa, inverse(bb)) == cc;
  90.     }
  91. }
  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.     for (ul i = '0'; i <= '9'; ++i) {
  102.         encode[i] = i - '0';
  103.     }
  104.     for (ul i = 'A'; i <= 'F'; ++i) {
  105.         encode[i] = i - 'A' + 10;
  106.     }
  107.     while (iss >> s) {
  108.         a.resize(0);
  109.         b.resize(0);
  110.         c.resize(0);
  111.         ul i;
  112.         for (i = 0; i != s.size() && check(s[i]); ++i) {
  113.             a.push_back(encode[s[i]]);
  114.         }
  115.         char op = s[i];
  116.         for (++i; i != s.size() && check(s[i]); ++i) {
  117.             b.push_back(encode[s[i]]);
  118.         }
  119.         for (++i; i != s.size() && check(s[i]); ++i) {
  120.             c.push_back(encode[s[i]]);
  121.         }
  122.         bool flag = false;
  123.         for (ul r = 2; r <= 16; ++r) {
  124.             if (check(r, op)) {
  125.                 oss << r << '\n';
  126.                 flag = true;
  127.                 break;
  128.             }
  129.         }
  130.         if (!flag) {
  131.             oss << "-1\n";
  132.         }
  133.     }
  134.     std::cout << oss.str();
  135.     return 0;
  136. }

C、Borrow 6829

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

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul base = 998244353;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < base ? a + b : a + b - base;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + base - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % base;
  27. }
  29. ul T;
  31. const ul maxn = 1e6;
  33. ul fac[maxn + 1];
  34. ul fiv[maxn + 1];
  35. ul inv[maxn + 1];
  36. ul twopowinv[maxn + 1];
  38. ul x, y, z;
  40. ul sbi(ul a, ul b)
  41. {
  42.     return mul(fac[a + b], mul(fiv[a], fiv[b]));
  43. }
  45. int main()
  46. {
  47.     std::ios::sync_with_stdio(false);
  48.     std::cin.tie(0);
  49.     iss.tie(0);
  50.     oss.tie(0);
  51.     std::getline(std::cin, instr, char(0));
  52.     iss.str(instr);
  53.     fac[0] = 1;
  54.     for (ul i = 1; i <= maxn; ++i) {
  55.         fac[i] = mul(fac[i - 1], i);
  56.     }
  57.     inv[1] = 1;
  58.     fiv[0] = fiv[1] = 1;
  59.     for (ul i = 2; i <= maxn; ++i) {
  60.         inv[i] = base - mul(base / i, inv[base % i]);
  61.         fiv[i] = mul(fiv[i - 1], inv[i]);
  62.     }
  63.     twopowinv[0] = 1;
  64.     for (ul i = 1; i <= maxn; ++i) {
  65.         twopowinv[i] = mul(twopowinv[i - 1], inv[2]);
  66.     }
  67.     iss >> T;
  68.     for (ul Case = 1; Case <= T; ++Case) {
  69.         iss >> x >> y >> z;
  70.         if (x < z) {
  71.             std::swap(x, z);
  72.         }
  73.         if (x < y) {
  74.             std::swap(x, y);
  75.         }
  76.         ul a = x - y, b = x - z;
  77.         if ((a + b) % 3 != 0) {
  78.             oss << "-1\n";
  79.             continue;
  80.         }
  81.         if (a >= b + b) {
  82.             oss << (a + a - b) / 3 * 2 << '\n';
  83.             continue;
  84.         }
  85.         if (b >= a + a) {
  86.             oss << (b + b - a) / 3 * 2 << '\n';
  87.             continue;
  88.         }
  89.         ul na = (a + a - b) / 3, nb = (b + b - a) / 3;
  90.         a = na;
  91.         b = nb;
  92.         ul ans = 0;
  93.         for (ul s = 1; s <= a; ++s) {
  94.             ans = plus(ans, mul(mul(s + a + b, sbi(a - s, b - 1)), twopowinv[a + b - s]));
  95.         }
  96.         for (ul t = 1; t <= b; ++t) {
  97.             ans = plus(ans, mul(mul(t + a + b, sbi(a - 1, b - t)), twopowinv[a + b - t]));
  98.         }
  99.         oss << ans << '\n';
  100.     }
  101.     std::cout << oss.str();
  102.     return 0;
  103. }

D、Asteroid in Love 6830

简单题

  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. class vec {
  13. public:
  14.     ll x = 0;
  15.     ll y = 0;
  16.     vec()=default;
  17.     vec(ll a, ll b): x(a), y(b) {}
  18. };
  20. vec operator+(const vec& a, const vec& b)
  21. {
  22.     return vec(a.x + b.x, a.y + b.y);
  23. }
  25. vec operator-(const vec& a, const vec& b)
  26. {
  27.     return vec(a.x - b.x, a.y - b.y);
  28. }
  30. ll operator*(const vec& a, const vec& b)
  31. {
  32.     return a.x * b.x + a.y * b.y;
  33. }
  35. ll operator^(const vec& a, const vec& b)
  36. {
  37.     return a.x * b.y - a.y * b.x;
  38. }
  40. ul T;
  42. ul n;
  44. std::vector<vec> star[3];
  46. std::vector<vec> buttom;
  47. std::vector<vec> top;
  49. ll findans(const std::vector<vec>& v, const vec& a, const vec& b)
  50. {
  51.     vec dir = b - a;
  52.     ul l = 0, r = v.size();
  53.     while (l + 1 != r) {
  54.         ul mid = l + r >> 1;
  55.         ul midl = mid - 1;
  56.         if ((dir ^ v[mid]) >= (dir ^ v[midl])) {
  57.             l = mid;
  58.         } else {
  59.             r = mid;
  60.         }
  61.     }
  62.     return dir ^ (v[l] - a);
  63. }
  65. int main()
  66. {
  67.     std::ios::sync_with_stdio(false);
  68.     std::cin.tie(0);
  69.     iss.tie(0);
  70.     oss.tie(0);
  71.     std::getline(std::cin, instr, char(0));
  72.     iss.str(instr);
  73.     iss >> T;
  74.     for (ul Case = 1; Case <= T; ++Case) {
  75.         star[0].resize(0);
  76.         star[1].resize(0);
  77.         star[2].resize(0);
  78.         iss >> n;
  79.         for (ul i = 1; i <= n; ++i) {
  80.             vec tmp;
  81.             ul c;
  82.             iss >> tmp.x >> tmp.y >> c;
  83.             star[c].push_back(tmp);
  84.         }
  85.         for (ul c = 0; c <= 2; ++c) {
  86.             if (star[c].size() == 1) {
  87.                 continue;
  88.             }
  89.             std::sort(star[c].begin(), star[c].end(), [](const vec& a, const vec& b){return a.x != b.x ? a.x < b.x : a.y < b.y;});
  90.             buttom.resize(0);
  91.             for (const auto& curr : star[c]) {
  92.                 while (buttom.size() >= 2 && (buttom.back() - buttom[buttom.size() - 2] ^ curr - buttom.back()) <= 0) {
  93.                     buttom.pop_back();
  94.                 }
  95.                 buttom.push_back(curr);
  96.             }
  97.             std::reverse(star[c].begin(), star[c].end());
  98.             top.resize(0);
  99.             for (const auto& curr : star[c]) {
  100.                 while (top.size() >= 2 && (top.back() - top[top.size() - 2] ^ curr - top.back()) <= 0) {
  101.                     top.pop_back();
  102.                 }
  103.                 top.push_back(curr);
  104.             }
  105.             star[c].resize(0);
  106.             for (const auto& curr : buttom) {
  107.                 star[c].push_back(curr);
  108.             }
  109.             star[c].pop_back();
  110.             for (const auto& curr : top) {
  111.                 star[c].push_back(curr);
  112.             }
  113.             star[c].pop_back();
  114.         }
  115.         if (star[0].size() < star[1].size()) {
  116.             std::swap(star[0], star[1]);
  117.         }
  118.         if (star[0].size() < star[2].size()) {
  119.             std::swap(star[0], star[2]);
  120.         }
  121.         std::sort(star[0].begin(), star[0].end(), [](const vec& a, const vec& b){return a.x != b.x ? a.x < b.x : a.y < b.y;});
  122.         buttom.resize(0);
  123.         for (const auto& curr : star[0]) {
  124.             while (buttom.size() >= 2 && (buttom.back() - buttom[buttom.size() - 2] ^ curr - buttom.back()) <= 0) {
  125.                 buttom.pop_back();
  126.             }
  127.             buttom.push_back(curr);
  128.         }
  129.         std::reverse(star[0].begin(), star[0].end());
  130.         top.resize(0);
  131.         for (const auto& curr : star[0]) {
  132.             while (top.size() >= 2 && (top.back() - top[top.size() - 2] ^ curr - top.back()) <= 0) {
  133.                 top.pop_back();
  134.             }
  135.             top.push_back(curr);
  136.         }
  137.         ll ans = 0;
  138.         for (const auto& a : star[1]) {
  139.             for (const auto& b : star[2]) {
  140.                 if (a.x > b.x) {
  141.                     ans = std::max(ans, findans(buttom, a, b));
  142.                     ans = std::max(ans, findans(top, b, a));
  143.                 } else {
  144.                     ans = std::max(ans, findans(top, a, b));
  145.                     ans = std::max(ans, findans(buttom, b, a));
  146.                 }
  147.             }
  148.         }
  149.         oss << (ans >> 1) << ((ans & 1) ? ".5\n" : ".0\n"); 
  150.     }
  151.     std::cout << oss.str();
  152.     return 0;
  153. }

E、Fragrant numbers 6831

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul maxlen = 11;
  14. std::string s = " 1145141919114514191911451419191145141919114514191911451419191145141919114514191911451419191145141919";
  16. std::vector<ul> ans[maxlen + 1][maxlen + 1];
  18. li out[5001];
  20. ul T;
  22. ul n;
  24. ul cnt;
  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 len = 1; len <= maxlen; ++len) {
  35.         for (ul l = 1, r = l + len - 1; r <= maxlen; ++l, ++r) {
  36.             if (len <= 4) {
  37.                 ul t = 0;
  38.                 for (ul i = l; i <= r; ++i) {
  39.                     t *= 10;
  40.                     t += s[i] - '0';
  41.                 }
  42.                 if (t <= 5000) {
  43.                     ans[l][r].push_back(t);
  44.                 }
  45.             }
  46.             for (ul ml = l, mr = l + 1; mr <= r; ++ml, ++mr) {
  47.                 for (ul a : ans[l][ml]) {
  48.                     for (ul b : ans[mr][r]) {
  49.                         if (a + b <= 5000) {
  50.                             ans[l][r].push_back(a + b);
  51.                         }
  52.                         if (a * b <= 5000) {
  53.                             ans[l][r].push_back(a * b);
  54.                         }
  55.                     }
  56.                 }
  57.                 std::sort(ans[l][r].begin(), ans[l][r].end());
  58.                 ans[l][r].resize(std::unique(ans[l][r].begin(), ans[l][r].end()) - ans[l][r].begin());
  59.             }
  60.             if (l == 1) {
  61.                 for (auto t : ans[l][r]) {
  62.                     if (!out[t]) {
  63.                         out[t] = r;
  64.                         ++cnt;
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     out[3] = out[7] = -1;
  71.     iss >> T;
  72.     for (ul Case = 1; Case <= T; ++Case) {
  73.         iss >> n;
  74.         oss << out[n] << '\n';
  75.     }
  76.     std::cout << oss.str();
  77.     return 0;
  78. }

F、A Very Easy Graph Problem 6832

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul mod = 1e9 + 7;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul mul(ul a, ul b)
  20. {
  21.     return ull(a) * ull(b) % mod;
  22. }
  24. ul T;
  26. ul n, m;
  28. const ul maxn = 1e5;
  30. ul fa[maxn + 1];
  31. ul rk[maxn + 1];
  32. ul cnt[maxn + 1][3];
  33. ul al[2];
  34. std::vector<std::pair<ul, ul>> edge[maxn + 1];
  36. ul getfather(ul x)
  37. {
  38.     return x == fa[x] ? x : fa[x] = getfather(fa[x]);
  39. }
  41. bool connect(ul x, ul y)
  42. {
  43.     x = getfather(x);
  44.     y = getfather(y);
  45.     if (x == y) {
  46.         return false;
  47.     }
  48.     if (rk[x] > rk[y]) {
  49.         fa[y] = x;
  50.     } else if (rk[x] < rk[y]) {
  51.         fa[x] = y;
  52.     } else {
  53.         fa[y] = x;
  54.         ++rk[x];
  55.     }
  56.     return true;
  57. }
  59. ul ans;
  61. void search(ul curr, ul prev)
  62. {
  63.     for (const auto& e : edge[curr]) {
  64.         ul next = e.first;
  65.         ul v = e.second;
  66.         if (next == prev) {
  67.             continue;
  68.         }
  69.         search(next, curr);
  70.         ans = plus(ans, mul(v, mul(cnt[next][0], al[1] - cnt[next][4])));
  71.         ans = plus(ans, mul(v, mul(cnt[next][5], al[0] - cnt[next][0])));
  72.         cnt[curr][0] += cnt[next][0];
  73.         cnt[curr][6] += cnt[next][7];
  74.     }
  75. }
  77. int main()
  78. {
  79.     std::ios::sync_with_stdio(false);
  80.     std::cin.tie(0);
  81.     iss.tie(0);
  82.     oss.tie(0);
  83.     std::getline(std::cin, instr, char(0));
  84.     iss.str(instr);
  85.     iss >> T;
  86.     for (ul Case = 1; Case <= T; ++Case) {
  87.         al[0] = al[1] = 0;
  88.         iss >> n >> m;
  89.         for (ul i = 1; i <= n; ++i) {
  90.             fa[i] = i;
  91.             rk[i] = 0;
  92.             cnt[i][0] = cnt[i][8] = 0;
  93.             ul a;
  94.             iss >> a;
  95.             cnt[i][a] = 1;
  96.             ++al[a];
  97.             edge[i].resize(0);
  98.         }
  99.         ans = 0;
  100.         for (ul i = 1, t = 2; i <= m; ++i, t = plus(t, t)) {
  101.             ul u, v;
  102.             iss >> u >> v;
  103.             if (connect(u, v)) {
  104.                 edge[u].push_back(std::pair<ul, ul>(v, t));
  105.                 edge[v].push_back(std::pair<ul, ul>(u, t));
  106.             }
  107.         }
  108.         search(1, 0);
  109.         oss << ans << '\n';
  110.     }
  111.     std::cout << oss.str();
  112.     return 0;
  113. }

G、A Very Easy Math Problem 6833

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul base = 1e9 + 7;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < base ? a + b : a + b - base;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + base - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % base;
  27. }
  29. ul mpow(ul a, ul b)
  30. {
  31.     ul ret = 1;
  32.     while (b) {
  33.         if (b & 1) {
  34.             ret = mul(a, ret);
  35.         }
  36.         a = mul(a, a);
  37.         b >>= 1;
  38.     }
  39.     return ret;
  40. }
  42. ul T;
  44. ul n, x, k;
  46. const ul maxn = 2e5;
  48. ul mu[maxn + 1];
  49. ul mu2[maxn + 1];
  50. ul smuixk[maxn + 1];
  51. ul smu2ixk[maxn + 1];
  52. ul sik[maxn + 1];
  53. ul sik_x[maxn + 1];
  55. bool notprime[maxn + 1];
  56. std::vector<ul> prime;
  58. ul ans;
  59. ul ans2[maxn + 1];
  60. bool al[maxn + 1];
  62. int main()
  63. {
  64.     std::ios::sync_with_stdio(false);
  65.     std::cin.tie(0);
  66.     iss.tie(0);
  67.     oss.tie(0);
  68.     std::getline(std::cin, instr, char(0));
  69.     iss.str(instr);
  70.     iss >> T >> k >> x;
  71.     mu[1] = 1;
  72.     mu2[1] = 1;
  73.     smuixk[1] = 1;
  74.     smu2ixk[1] = 1;
  75.     for (ul i = 2; i <= maxn; ++i) {
  76.         if (!notprime[i]) {
  77.             prime.push_back(i);
  78.             mu[i] = minus(0, 1);
  79.             mu2[i] = 1;
  80.         }
  81.         smuixk[i] = plus(mul(mu[i], mpow(mpow(i, x), k)), smuixk[i - 1]);
  82.         smu2ixk[i] = plus(mul(mul(mu2[i], mpow(mpow(i, x), k)), i), smu2ixk[i - 1]);
  83.         for (ul p : prime) {
  84.             if (i * p > maxn) {
  85.                 break;
  86.             }
  87.             notprime[i * p] = true;
  88.             if (i % p == 0) {
  89.                 mu[i * p] = 0;
  90.                 mu2[i * p] = 0;
  91.                 break;
  92.             } else {
  93.                 mu[i * p] = minus(0, mu[i]);
  94.                 mu2[i * p] = mu2[i];
  95.             }
  96.         }
  97.     }
  98.     for (ul i = 1; i <= maxn; ++i) {
  99.         ul ik = mpow(i, k);
  100.         sik[i] = plus(sik[i - 1], ik);
  101.         sik_x[i] = mpow(sik[i], x);
  102.     }
  103.     for (ul Case = 1; Case <= T; ++Case) {
  104.         iss >> n;
  105.         ul ans = 0;
  106.         for (ul d = 1, dd; d <= n; d = dd + 1) {
  107.             ul nqd = n / d;
  108.             dd = n / nqd;
  109.             if (!al[nqd]) {
  110.                 al[nqd] = true;
  111.                 for (ul e = 1, ee; e <= nqd; e = ee + 1) {
  112.                     ul nqdqe = nqd / e;
  113.                     ee = nqd / nqdqe;
  114.                     ans2[nqd] = plus(ans2[nqd], mul(minus(smuixk[ee], smuixk[e - 1]), sik_x[nqdqe]));
  115.                 }
  116.             }
  117.             ans = plus(ans, mul(minus(smu2ixk[dd], smu2ixk[d - 1]), ans2[nqd]));
  118.         }
  119.         oss << ans << '\n';
  120.     }
  121.     std::cout << oss.str();
  122.     return 0;
  123. }

H、Yukikaze and Smooth numbers 6834

见此

I、Divisibility 6835

简单题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T;
  13. ull b, x;
  15. int main()
  16. {
  17.     std::ios::sync_with_stdio(false);
  18.     std::cin.tie(0);
  19.     iss.tie(0);
  20.     oss.tie(0);
  21.     std::getline(std::cin, instr, char(0));
  22.     iss.str(instr);
  23.     iss >> T;
  24.     for (ul Case = 1; Case <= T; ++Case) {
  25.         iss >> b >> x;
  26.         oss << (b % x == 1 ? "T\n" : "F\n");
  27.     }
  28.     std::cout << oss.str();
  29.     return 0;
  30. }

J、Expectation 6836

简单题 矩阵树定理证明见此

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul base = 998244353;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < base ? a + b : a + b - base;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + base - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % base;
  27. }
  29. void exgcd(li a, li b, li& x, li& y)
  30. {
  31.     if (b) {
  32.         exgcd(b, a % b, y, x);
  33.         y -= a / b * x;
  34.     } else {
  35.         x = 1;
  36.         y = 0;
  37.     }
  38. }
  40. ul inverse(ul a)
  41. {
  42.     li x, y;
  43.     exgcd(a, base, x, y);
  44.     return x < 0 ? x + li(base) : x;
  45. }
  47. ul T;
  49. ul n, m;
  51. const ul maxn = 100;
  53. ul mat[32][maxn + 1][maxn + 1];
  55. ul smat[maxn + 1][maxn + 1];
  57. ul det(ul a[][maxn + 1], ul n)
  58. {
  59.     ul ret = 1;
  60.     for (ul i = 1; i <= n; ++i) {
  61.         ul id;
  62.         for (id = i; i <= n && !a[id][i]; ++i);
  63.         if (id != i) {
  64.             for (ul j = i; j <= n; ++j) {
  65.                 std::swap(a[i][j], a[id][j]);
  66.             }
  67.             ret = minus(0, ret);
  68.         }
  69.         ret = mul(ret, a[i][i]);
  70.         for (ul j = i + 1; j <= n; ++j) {
  71.             ul tmp = minus(0, mul(a[j][i], inverse(a[i][i])));
  72.             for (ul k = i; k <= n; ++k) {
  73.                 a[j][k] = plus(a[j][k], mul(a[i][k], tmp));
  74.             }
  75.         }
  76.     }
  77.     return ret;
  78. }
  80. int main()
  81. {
  82.     std::ios::sync_with_stdio(false);
  83.     std::cin.tie(0);
  84.     iss.tie(0);
  85.     oss.tie(0);
  86.     std::getline(std::cin, instr, char(0));
  87.     iss.str(instr);
  88.     iss >> T;
  89.     for (ul Case = 1; Case <= T; ++Case) {
  90.         iss >> n >> m;
  91.         for (ul i = 0; i != 32; ++i) {
  92.             for (ul j = 1; j <= n; ++j) {
  93.                 std::memset(mat[i][j] + 1, 0, sizeof(ul) * n);
  94.             }
  95.         }
  96.         for (ul i = 1; i <= n; ++i) {
  97.             std::memset(smat[i] + 1, 0, sizeof(ul) * n);
  98.         }
  99.         for (ul i = 1; i <= m; ++i) {
  100.             ul u, v, w;
  101.             iss >> u >> v >> w;
  102.             smat[u][u] = plus(smat[u][u], 1);
  103.             smat[v][v] = plus(smat[v][v], 1);
  104.             smat[u][v] = minus(smat[u][v], 1);
  105.             smat[v][u] = minus(smat[v][u], 1);
  106.             for (ul j = 0; j != 32; ++j) {
  107.                 if (w >> j & 1) {
  108.                     mat[j][u][u] = plus(mat[j][u][u], 1);
  109.                     mat[j][v][v] = plus(mat[j][v][v], 1);
  110.                     mat[j][u][v] = minus(mat[j][u][v], 1);
  111.                     mat[j][v][u] = minus(mat[j][v][u], 1);
  112.                 }
  113.             }
  114.         }
  115.         ul s = det(smat, n - 1);
  116.         ul ans = 0;
  117.         for (ul i = 31; ~i; --i) {
  118.             ans = plus(ans, ans);
  119.             ans = plus(ans, det(mat[i], n - 1));
  120.         }
  121.         oss << mul(ans, inverse(s)) << '\n';
  122.     }
  123.     std::cout << oss.str();
  124.     return 0;
  125. }

K、Kirakira 6837

线段极角排序裸题

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul base = 31607;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < base ? a + b : a + b - base;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + base - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return a * b % base;
  27. }
  29. void exgcd(li a, li b, li& x, li& y)
  30. {
  31.     if (b) {
  32.         exgcd(b, a % b, y, x);
  33.         y -= a / b * x;
  34.     } else {
  35.         x = 1;
  36.         y = 0;
  37.     }
  38. }
  40. ul inverse(ul a)
  41. {
  42.     li x, y;
  43.     exgcd(a, base, x, y);
  44.     return x < 0 ? x + li(base) : x;
  45. }
  47. ul reg(li a)
  48. {
  49.     a %= li(base);
  50.     return a < 0 ? a + li(base) : a;
  51. }
  53. ul T;
  55. ul n;
  57. const ul maxn = 1e3;
  59. class vec {
  60. public:
  61.     li x = 0;
  62.     li y = 0;
  63.     vec()=default;
  64.     vec(li a, li b): x(a), y(b) {}
  65. };
  67. vec operator+(const vec& a, const vec& b)
  68. {
  69.     return vec(a.x + b.x, a.y + b.y);
  70. }
  72. vec operator-(const vec& a, const vec& b)
  73. {
  74.     return vec(a.x - b.x, a.y - b.y);
  75. }
  77. li operator*(const vec& a, const vec& b)
  78. {
  79.     return a.x * b.x + a.y * b.y;
  80. }
  82. li operator^(const vec& a, const vec& b)
  83. {
  84.     return a.x * b.y - a.y * b.x;
  85. }
  87. vec point[maxn + 1];
  89. ul p[maxn + 1];
  91. using pulul = std::pair<ul, ul>;
  93. std::vector<pulul> dirs;
  95. li sgn(li x)
  96. {
  97.     return x < 0 ? -1 : (x > 0 ? 1 : 0);
  98. }
  100. ul type(const vec& v)
  101. {
  102.     static const ul types[3][3] = {{3, 3, 2}, {4, 0, 2}, {4, 1, 1}};
  103.     return types[sgn(v.x) + 1][sgn(v.y) + 1];
  104. }
  106. bool cmp(const vec& a, const vec& b, const vec& c, const vec& d)
  107. {
  108.     vec ab = b - a;
  109.     vec cd = d - c;
  110.     ul tab = type(ab);
  111.     ul tcd = type(cd);
  112.     if (tab != tcd) {
  113.         return tab < tcd;
  114.     }
  115.     li tmp = ab ^ cd;
  116.     if (tmp != 0) {
  117.         return tmp > 0;
  118.     }
  119.     vec ac = c - a;
  120.     tmp = ab ^ ac;
  121.     if (tmp != 0) {
  122.         return tmp > 0;
  123.     }
  124.     tmp = ab * ac;
  125.     if (tmp != 0) {
  126.         return tmp > 0;
  127.     }
  128.     return ab * (d - b) > 0;
  129. }
  131. ul ord[maxn + 1];
  132. ul pos[maxn + 1];
  134. ul pre[maxn + 1];
  136. int main()
  137. {
  138.     std::ios::sync_with_stdio(false);
  139.     std::cin.tie(0);
  140.     iss.tie(0);
  141.     oss.tie(0);
  142.     std::getline(std::cin, instr, char(0));
  143.     iss.str(instr);
  144.     pre[0] = 1;
  145.     iss >> T;
  146.     for (ul Case = 1; Case <= T; ++Case) {
  147.         iss >> n;
  148.         for (ul i = 1; i <= n; ++i) {
  149.             iss >> point[i].x >> point[i].y;
  150.             ul u, v;
  151.             iss >> u >> v;
  152.             p[i] = mul(u, inverse(v));
  153.         }
  154.         dirs.resize(0);
  155.         for (ul i = 1; i + 1 <= n; ++i) {
  156.             for (ul j = i + 1; j <= n; ++j) {
  157.                 dirs.push_back(pulul(i, j));
  158.                 dirs.push_back(pulul(j, i));
  159.             }
  160.         }
  161.         std::sort(dirs.begin(), dirs.end(), [](const pulul& a, const pulul& b){return cmp(point[a.first], point[a.second], point[b.first], point[b.second]);});
  162.         for (ul i = 1; i <= n; ++i) {
  163.             ord[i] = i;
  164.         }
  165.         std::sort(ord + 1, ord + n + 1, [](ul a, ul b){return point[a].y != point[b].y ? point[a].y < point[b].y : point[a].x < point[b].x;});
  166.         for (ul i = 1; i <= n; ++i) {
  167.             pos[ord[i]] = i;
  168.             pre[i] = mul(pre[i - 1], minus(1, p[ord[i]]));
  169.         }
  170.         ul ans = 0;
  171.         for (const auto dir : dirs) {
  172.             ans = plus(mul(mul(mul(p[dir.first], p[dir.second]), pre[pos[dir.first] - 1]), reg(point[dir.first] ^ point[dir.second])), ans);
  173.             std::swap(pos[dir.first], pos[dir.second]);
  174.             pre[pos[dir.second]] = mul(pre[pos[dir.second] - 1], minus(1, p[dir.second]));
  175.         }
  176.         oss << mul(ans, inverse(2)) << '\n';
  177.     }
  178.     std::cout << oss.str();
  179.     return 0;
  180. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注