[关闭]
@qq290637843 2020-11-17T15:37:55.000000Z 字数 23373 阅读 442

2020杭电第七场

B、Bitwise Xor 6845

官方题解如下。
image.png-188.5kB
关于改写法正确性的证明：
考虑如下两个向线性基里插入向量的算法：
1、

  1. void push(std::pair<ul, ul> base[], std::pair<ul, ul> p)
  2. {
  3.     for (ul i = 29; ~i && p.first; --i) {
  4.         if (~p.first >> i & 1) {
  5.             continue;
  6.         }
  7.         if (!base[i].first) {
  8.             base[i] = p;
  9.             break;
  10.         }
  11.         p.first ^= base[i].first;
  12.     }
  13. }

2、

  1. void push(std::pair<ul, ul> base[], std::pair<ul, ul> p)
  2. {
  3.     for (ul i = 29; ~i && p.first; --i) {
  4.         if (~p.first >> i & 1) {
  5.             continue;
  6.         }
  7.         if (!base[i].first) {
  8.             base[i] = p;
  9.             break;
  10.         }
  11.         if (p.second > base[i].second) {
  12.             std::swap(p, base[i]);
  13.         }
  14.         p.first ^= base[i].first;
  15.     }
  16. }

于是证明分为两个部分：一、证明将区间中的向量从右向左用算法1插入得到的线性基能解决的询问；二、证明将区间中的向量从左向右用算法2插入得到的线性基，并将其中下标小于的向量删去得到的结果，正好和第一部分中所说的线性基一致。

  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 T;
  12. std::pair<ul, ul> base[maxn + 1][30];
  14. ul n, q;
  16. ul pre[maxn + 1];
  18. ul p[maxn + 1];
  20. void push(std::pair<ul, ul> base[], std::pair<ul, ul> p)
  21. {
  22.     for (ul i = 29; ~i && p.first; --i) {
  23.         if (~p.first >> i & 1) {
  24.             continue;
  25.         }
  26.         if (!base[i].first) {
  27.             base[i] = p;
  28.             break;
  29.         }
  30.         if (p.second > base[i].second) {
  31.             std::swap(p, base[i]);
  32.         }
  33.         p.first ^= base[i].first;
  34.     }
  35. }
  37. std::string instr;
  39. std::stringstream iss;
  41. std::stringstream oss;
  43. int main()
  44. {
  45.     std::ios::sync_with_stdio(false);
  46.     std::cin.tie(0);
  47.     iss.tie(0);
  48.     oss.tie(0);
  49.     std::getline(std::cin, instr, char(0));
  50.     iss.str(instr);
  51.     iss >> T;
  52.     for (ul Case = 1; Case <= T; ++Case) {
  53.         iss >> n >> q;
  54.         for (ul i = 1; i <= n; ++i) {
  55.             ul m;
  56.             iss >> m >> p[i];
  57.             std::memcpy(base[i], base[i - 1], sizeof(base[i]));
  58.             pre[i] = 0;
  59.             for (ul j = 1; j <= m; ++j) {
  60.                 ul x, y;
  61.                 iss >> x >> y;
  62.                 push(base[i], std::pair<ul, ul>(x ^ y, i));
  63.                 pre[i] ^= x;
  64.             }
  65.             pre[i] ^= pre[i - 1];
  66.         }
  67.         for (ul i = 1; i <= q; ++i) {
  68.             ul t;
  69.             iss >> t;
  70.             if (t == 1) {
  71.                 ul x, y;
  72.                 iss >> x >> y;
  73.                 p[x] = y;
  74.             } else {
  75.                 ul l, r, x;
  76.                 iss >> l >> r >> x;
  77.                 x ^= pre[r] ^ pre[l - 1];
  78.                 for (ul i = 29; ~i; --i) {
  79.                     if (base[r][i].first == 0 || base[r][i].second < l) {
  80.                         continue;
  81.                     }
  82.                     if ((base[r][i].first ^ x ^ p[base[r][i].second]) < (x ^ p[base[r][i].second])) {
  83.                         x ^= base[r][i].first;
  84.                     }
  85.                 }
  86.                 oss << x << '\n';
  87.             }
  88.         }
  89.     }
  90.     std::cout << oss.str();
  91.     return 0;
  92. }

C、Counting 6846

image.png-203.4kB
解释一下这个官方题解是什么意思：
第一部分：
注意一个带颜色的序列合法当且仅当对任何位置上的项，其之后的第一个（如果有）和其异色的项的值必须小于等于的值。于是可知第一部分中所说的也是充要条件。
第二部分：
注意第一部分的充要条件可以得出，所有中的项的颜色是相同的。以及可知，染色有且只有两个限制：①中项颜色一致；②值相同的两项颜色相异。
第三部分：第一句话来自第二部分，于是合法。的意思是，所以第二句话就是说合法，注意这里的和之前的来源并不一致。考虑将合法无色序列先分为子段集族，那么可以给这些子段集黑白染色（注意，和红蓝染色是两件事，红蓝染色是每个子段集中对子段按照二分图那样染色，而这里是说每个子段集都染相同的颜色），那么有种染法，每个颜色的项目取出再将值压回和，于是正好对应了两个无色（指红蓝）的合法序列（这里只是说是映射，没说单满问题）。而反过来，正好对于每个，以及长为和的无色合法序列，从中选个数，将投上去，将投到剩下的个数，那么正好对应一种长为的黑白染色的合法序列。综上可知合法。
懒得整理了，把整个多项式的模板全复制过来了，实际上用不到这么多。

  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. std::mt19937_64 rnd;
  11. const ul base = 998244353;
  13. ul plus(ul a, ul b)
  14. {
  15.     return a + b < base ? a + b : a + b - base;
  16. }
  18. ul minus(ul a, ul b)
  19. {
  20.     return a < b ? a + base - b : a - b;
  21. }
  23. ul mul(ul a, ul b)
  24. {
  25.     return ull(a) * ull(b) % base;
  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 -= x * (a / b);
  33.     } else {
  34.         x = 1;
  35.         y = 0;
  36.     }
  37. }
  39. ul inverse(ul a)
  40. {
  41.     li x, y;
  42.     exgcd(a, base, x, y);
  43.     return x < 0 ? x + li(base) : x;
  44. }
  46. ul pow(ul a, ul b)
  47. {
  48.     ul ret = 1;
  49.     ul temp = a;
  50.     while (b) {
  51.         if (b & 1) {
  52.             ret = mul(ret, temp);
  53.         }
  54.         temp = mul(temp, temp);
  55.         b >>= 1;
  56.     }
  57.     return ret;
  58. }
  62. ul sqrt(ul x)
  63. {
  64.     ul a;
  65.     ul w2;
  66.     while (true) {
  67.         a = rnd() % base;
  68.         w2 = minus(mul(a, a), x);
  69.         if (pow(w2, base - 1 >> 1) == base - 1) {
  70.             break;
  71.         }
  72.     }
  73.     ul b = base + 1 >> 1;
  74.     ul rs = 1, rt = 0;
  75.     ul as = a, at = 1;
  76.     ul qs, qt;
  77.     while (b) {
  78.         if (b & 1) {
  79.             qs = plus(mul(rs, as), mul(mul(rt, at), w2));
  80.             qt = plus(mul(rs, at), mul(rt, as));
  81.             rs = qs;
  82.             rt = qt;
  83.         }
  84.         b >>= 1;
  85.         qs = plus(mul(as, as), mul(mul(at, at), w2));
  86.         qt = plus(mul(as, at), mul(as, at));
  87.         as = qs;
  88.         at = qt;
  89.     }
  90.     return rs + rs < base ? rs : base - rs;
  91. }
  93. class polynomial : public vul {
  94. public:
  95.     void clearzero() {
  96.         while (size() && !back()) {
  97.             pop_back();
  98.         }
  99.     }
  100.     polynomial()=default;
  101.     polynomial(const vul& a): vul(a) { }
  102.     polynomial(vul&& a): vul(std::move(a)) { }
  103.     ul degree() const {
  104.         return size() - 1;
  105.     }
  106.     ul operator()(ul x) const {
  107.         ul ret = 0;
  108.         for (ul i = size() - 1; ~i; --i) {
  109.             ret = mul(ret, x);
  110.             ret = plus(ret, vul::operator[](i));
  111.         }
  112.         return ret;
  113.     }
  114. };
  116. polynomial& operator+=(polynomial& a, const polynomial& b)
  117. {
  118.     a.resize(std::max(a.size(), b.size()), 0);
  119.     for (ul i = 0; i != b.size(); ++i) {
  120.         a[i] = plus(a[i], b[i]);
  121.     }
  122.     a.clearzero();
  123.     return a;
  124. }
  126. polynomial operator+(const polynomial& a, const polynomial& b)
  127. {
  128.     polynomial ret = a;
  129.     return ret += b;
  130. }
  132. polynomial& operator-=(polynomial& a, const polynomial& b)
  133. {
  134.     a.resize(std::max(a.size(), b.size()), 0);
  135.     for (ul i = 0; i != b.size(); ++i) {
  136.         a[i] = minus(a[i], b[i]);
  137.     }
  138.     a.clearzero();
  139.     return a;
  140. }
  142. polynomial operator-(const polynomial& a, const polynomial& b)
  143. {
  144.     polynomial ret = a;
  145.     return ret -= b;
  146. }
  148. class ntt_t {
  149. public:
  150.     static const ul lgsz = 18;
  151.     static const ul sz = 1 << lgsz;
  152.     static const ul g = 3;
  153.     ul w[sz + 1];
  154.     ul leninv[lgsz + 1];
  155.     ntt_t() {
  156.         ul wn = pow(g, (base - 1) >> lgsz);
  157.         w[0] = 1;
  158.         for (ul i = 1; i <= sz; ++i) {
  159.             w[i] = mul(w[i - 1], wn);
  160.         }
  161.         leninv[lgsz] = inverse(sz);
  162.         for (ul i = lgsz - 1; ~i; --i) {
  163.             leninv[i] = plus(leninv[i + 1], leninv[i + 1]);
  164.         }
  165.     }
  166.     void operator()(vul& v, ul& n, bool inv) {
  167.         ul lgn = 0;
  168.         while ((1 << lgn) < n) {
  169.             ++lgn;
  170.         }
  171.         n = 1 << lgn;
  172.         v.resize(n, 0);
  173.         for (ul i = 0, j = 0; i != n; ++i) {
  174.             if (i < j) {
  175.                 std::swap(v[i], v[j]);
  176.             }
  177.             ul k = n >> 1;
  178.             while (k & j) {
  179.                 j &= ~k;
  180.                 k >>= 1;
  181.             }
  182.             j |= k;
  183.         }
  184.         for (ul lgmid = 0; (1 << lgmid) != n; ++lgmid) {
  185.             ul mid = 1 << lgmid;
  186.             ul len = mid << 1;
  187.             for (ul i = 0; i != n; i += len) {
  188.                 for (ul j = 0; j != mid; ++j) {
  189.                     ul t0 = v[i + j];
  190.                     ul t1 = mul(w[inv ? (len - j << lgsz - lgmid - 1) : (j << lgsz - lgmid - 1)], v[i + j + mid]);
  191.                     v[i + j] = plus(t0, t1);
  192.                     v[i + j + mid] = minus(t0, t1);
  193.                 }
  194.             }
  195.         }
  196.         if (inv) {
  197.             for (ul i = 0; i != n; ++i) {
  198.                 v[i] = mul(v[i], leninv[lgn]);
  199.             }
  200.         }
  201.     }
  202. } ntt;
  204. polynomial& operator*=(polynomial& a, const polynomial& b)
  205. {
  206.     if (!b.size() || !a.size()) {
  207.         a.resize(0);
  208.         return a;
  209.     }
  210.     polynomial temp = b;
  211.     ul npmp1 = a.size() + b.size() - 1;
  212.     if (ull(a.size()) * ull(b.size()) <= ull(npmp1) * ull(50)) {
  213.         temp.resize(0);
  214.         temp.resize(npmp1, 0);
  215.         for (ul i = 0; i != a.size(); ++i) {
  216.             for (ul j = 0; j != b.size(); ++j) {
  217.                 temp[i + j] = plus(temp[i + j], mul(a[i], b[j]));
  218.             }
  219.         }
  220.         a = temp;
  221.         a.clearzero();
  222.         return a;
  223.     }
  224.     ntt(a, npmp1, false);
  225.     ntt(temp, npmp1, false);
  226.     for (ul i = 0; i != npmp1; ++i) {
  227.         a[i] = mul(a[i], temp[i]);
  228.     }
  229.     ntt(a, npmp1, true);
  230.     a.clearzero();
  231.     return a;
  232. }
  234. polynomial operator*(const polynomial& a, const polynomial& b)
  235. {
  236.     polynomial ret = a;
  237.     return ret *= b;
  238. }
  240. polynomial& operator*=(polynomial& a, ul b)
  241. {
  242.     if (!b) {
  243.         a.resize(0);
  244.         return a;
  245.     }
  246.     for (ul i = 0; i != a.size(); ++i) {
  247.         a[i] = mul(a[i], b);
  248.     }
  249.     return a;
  250. }
  252. polynomial operator*(const polynomial& a, ul b)
  253. {
  254.     polynomial ret = a;
  255.     return ret *= b;
  256. }
  258. polynomial inverse(const polynomial& a, ul lgdeg)
  259. {
  260.     polynomial ret({inverse(a[0])});
  261.     polynomial temp;
  262.     polynomial tempa;
  263.     for (ul i = 0; i != lgdeg; ++i) {
  264.         tempa.resize(0);
  265.         tempa.resize(1 << i << 1, 0);
  266.         for (ul j = 0; j != tempa.size() && j != a.size(); ++j) {
  267.             tempa[j] = a[j];
  268.         }
  269.         temp = ret * (polynomial({2}) - tempa * ret);
  270.         if (temp.size() > (1 << i << 1)) {
  271.             temp.resize(1 << i << 1, 0);
  272.         }
  273.         temp.clearzero();
  274.         std::swap(temp, ret);
  275.     }
  276.     return ret;
  277. }
  279. void quotientremain(const polynomial& a, polynomial b, polynomial& q, polynomial& r)
  280. {
  281.     if (a.size() < b.size()) {
  282.         q = polynomial();
  283.         r = std::move(a);
  284.         return;
  285.     }
  286.     std::reverse(b.begin(), b.end());
  287.     auto ta = a;
  288.     std::reverse(ta.begin(), ta.end());
  289.     ul n = a.size() - 1;
  290.     ul m = b.size() - 1;
  291.     ta.resize(n - m + 1);
  292.     ul lgnmmp1 = 0;
  293.     while ((1 << lgnmmp1) < n - m + 1) {
  294.         ++lgnmmp1;
  295.     }
  296.     q = ta * inverse(b, lgnmmp1);
  297.     q.resize(n - m + 1);
  298.     std::reverse(b.begin(), b.end());
  299.     std::reverse(q.begin(), q.end());
  300.     r = a - b * q;
  301. }
  303. polynomial mod(const polynomial& a, const polynomial& b)
  304. {
  305.     polynomial q, r;
  306.     quotientremain(a, b, q, r);
  307.     return r;
  308. }
  310. polynomial quotient(const polynomial& a, const polynomial& b)
  311. {
  312.     polynomial q, r;
  313.     quotientremain(a, b, q, r);
  314.     return q;
  315. }
  317. polynomial sqrt(const polynomial& a, ul lgdeg)
  318. {
  319.     polynomial ret({sqrt(a[0])});
  320.     polynomial temp;
  321.     polynomial tempa;
  322.     for (ul i = 0; i != lgdeg; ++i) {
  323.         tempa.resize(0);
  324.         tempa.resize(1 << i << 1, 0);
  325.         for (ul j = 0; j != tempa.size() && j != a.size(); ++j) {
  326.             tempa[j] = a[j];
  327.         }
  328.         temp = (tempa * inverse(ret, i + 1) + ret) * (base + 1 >> 1);
  329.         if (temp.size() > (1 << i << 1)) {
  330.             temp.resize(1 << i << 1, 0);
  331.         }
  332.         temp.clearzero();
  333.         std::swap(temp, ret);
  334.     }
  335.     return ret;
  336. }
  338. polynomial diffrential(const polynomial& a)
  339. {
  340.     if (!a.size()) {
  341.         return a;
  342.     }
  343.     polynomial ret(vul(a.size() - 1, 0));
  344.     for (ul i = 1; i != a.size(); ++i) {
  345.         ret[i - 1] = mul(a[i], i);
  346.     }
  347.     return ret;
  348. }
  350. polynomial integral(const polynomial& a)
  351. {
  352.     polynomial ret(vul(a.size() + 1, 0));
  353.     for (ul i = 0; i != a.size(); ++i) {
  354.         ret[i + 1] = mul(a[i], inverse(i + 1));
  355.     }
  356.     return ret;
  357. }
  359. polynomial ln(const polynomial& a, ul lgdeg)
  360. {
  361.     polynomial da = diffrential(a);
  362.     polynomial inva = inverse(a, lgdeg);
  363.     polynomial ret = integral(da * inva);
  364.     if (ret.size() > (1 << lgdeg)) {
  365.         ret.resize(1 << lgdeg);
  366.         ret.clearzero();
  367.     }
  368.     return ret;
  369. }
  371. polynomial exp(const polynomial& a, ul lgdeg)
  372. {
  373.     polynomial ret({1});
  374.     polynomial temp;
  375.     polynomial tempa;
  376.     for (ul i = 0; i != lgdeg; ++i) {
  377.         tempa.resize(0);
  378.         tempa.resize(1 << i << 1, 0);
  379.         for (ul j = 0; j != tempa.size() && j != a.size(); ++j) {
  380.             tempa[j] = a[j];
  381.         }
  382.         temp = ret * (polynomial({1}) - ln(ret, i + 1) + tempa);
  383.         if (temp.size() > (1 << i << 1)) {
  384.             temp.resize(1 << i << 1, 0);
  385.         }
  386.         temp.clearzero();
  387.         std::swap(temp, ret);
  388.     }
  389.     return ret;
  390. }
  392. polynomial pow(const polynomial& a, ul k, ul lgdeg)
  393. {
  394.     return exp(ln(a, lgdeg) * k, lgdeg);
  395. }
  397. polynomial alpi[1 << 16][17];
  399. polynomial getalpi(const ul x[], ul l, ul lgrml)
  400. {
  401.     if (lgrml == 0) {
  402.         return alpi[l][lgrml] = vul({minus(0, x[l]), 1});
  403.     }
  404.     return alpi[l][lgrml] = getalpi(x, l, lgrml - 1) * getalpi(x, l + (1 << lgrml - 1), lgrml - 1);
  405. }
  407. void multians(const polynomial& f, const ul x[], ul y[], ul l, ul lgrml)
  408. {
  409.     if (f.size() <= 700) {
  410.         for (ul i = l; i != l + (1 << lgrml); ++i) {
  411.             y[i] = f(x[i]);
  412.         }
  413.         return;
  414.     }
  415.     if (lgrml == 0) {
  416.         y[l] = f(x[l]);
  417.         return;
  418.     }
  419.     multians(mod(f, alpi[l][lgrml - 1]), x, y, l, lgrml - 1);
  420.     multians(mod(f, alpi[l + (1 << lgrml - 1)][lgrml - 1]), x, y, l + (1 << lgrml - 1), lgrml - 1);
  421. }
  423. const ul maxn = 1e5;
  424. ul T;
  425. ul n;
  427. polynomial tmp;
  429. std::stringstream iss;
  430. std::stringstream oss;
  432. std::string instr;
  434. int main()
  435. {
  436.     rnd.seed(std::time(0));
  437.     std::ios::sync_with_stdio(false);
  438.     std::cin.tie(0);
  439.     iss.tie(0);
  440.     oss.tie(0);
  441.     std::getline(std::cin, instr, char(0));
  442.     iss.str(instr);
  443.     tmp.resize(maxn + maxn + 1);
  444.     tmp[0] = 1;
  445.     for (ul i = 1; i <= maxn + maxn; ++i) {
  446.         tmp[i] = mul(tmp[i - 1], plus(i, inverse(i)));
  447.     }
  448.     tmp = sqrt(tmp, 17);
  449.     tmp.resize(maxn + 1);
  450.     ul fac = 1;
  451.     for (ul i = 1; i <= maxn; ++i) {
  452.         fac = mul(i, fac);
  453.         tmp[i] = mul(tmp[i], fac);
  454.     }
  455.     iss >> T;
  456.     for (ul Case = 1; Case <= T; ++Case) {
  457.         iss >> n;
  458.         oss << tmp[n] << '\n';
  459.     }
  460.     std::cout << oss.str();
  461.     return 0;
  462. }

D、Decision 6847

image.png-14.7kB
image.png-61.6kB

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. ul t, a, c, m;
  12. ul plus(ul a, ul b)
  13. {
  14.     return a + b < m ? a + b : a + b - m;
  15. }
  17. ul mul(ul a, ul b)
  18. {
  19.     return ull(a) * ull(b) % m;
  20. }
  22. ull gcd(ull a, ull b)
  23. {
  24.     while (b) {
  25.         b ^= a ^= b ^= a %= b;
  26.     }
  27.     return a;
  28. }
  30. const ul maxm = 1e6;
  32. ul to[maxm][21];
  33. ull cnt[maxm][21];
  35. ull ans;
  37. std::stringstream iss;
  38. std::stringstream oss;
  40. std::string instr;
  42. int main()
  43. {
  44.     std::ios::sync_with_stdio(false);
  45.     std::cin.tie(0);
  46.     iss.tie(0);
  47.     oss.tie(0);
  48.     std::getline(std::cin, instr, char(0));
  49.     iss.str(instr);
  50.     iss >> T;
  51.     for (ul Case = 1; Case <= T; ++Case) {
  52.         iss >> t >> a >> c >> m;
  53.         for (ul i = 0; i != m; ++i) {
  54.             to[i][0] = plus(mul(a, plus(mul(a, i), c)), c);
  55.             cnt[i][0] = ~i & 1;
  56.         }
  57.         ul maxstep = 0;
  58.         for (ul sum = 0; sum <= t + t; ++sum) {
  59.             ul step;
  60.             if (sum & 1) {
  61.                 step = (std::min(sum, t + t - sum) - 1 >> 1) + 1;
  62.             } else {
  63.                 step = std::min(sum, t + t - sum) >> 1;
  64.             }
  65.             maxstep = std::max(maxstep, step);
  66.         }
  67.         for (ul k = 1; (1 << k) <= maxstep; ++k) {
  68.             for (ul i = 0; i != m; ++i) {
  69.                 to[i][k] = to[to[i][k - 1]][k - 1];
  70.                 cnt[i][k] = cnt[i][k - 1] + cnt[to[i][k - 1]][k - 1];
  71.             }
  72.         }
  73.         ans = 0;
  74.         for (ul sum = 0; sum <= t + t; ++sum) {
  75.             if (sum & 1) {
  76.                 ul start = plus(mul(a, sum), c);
  77.                 ul step = (std::min(sum, t + t - sum) - 1 >> 1) + 1;
  78.                 while (step) {
  79.                     ul k = 31 - __builtin_clz(step);
  80.                     step -= 1 << k;
  81.                     ans += cnt[start][k] << 1;
  82.                     start = to[start][k];
  83.                 }
  84.             } else {
  85.                 ul start = sum;
  86.                 ans += cnt[sum][0];
  87.                 start = to[sum][0];
  88.                 ul step = std::min(sum, t + t - sum) >> 1;
  89.                 while (step) {
  90.                     ul k = 31 - __builtin_clz(step);
  91.                     step -= 1 << k;
  92.                     ans += cnt[start][k] << 1;
  93.                     start = to[start][k];
  94.                 }
  95.             }
  96.         }
  97.         ull mm = ull(t + 1) * ull(t + 1);
  98.         ull g = gcd(ans, mm);
  99.         oss << ans / g << '/' << mm / g << '\n';
  100.     }
  101.     std::cout << oss.str();
  102.     return 0;
  103. }

E、Expectation 6848

考虑求每个限段被经过的次数的期望值。
注意无论第一次选了种可能方案中的哪一种，都一定会消耗掉相邻的一个球和洞，并规约为一个球洞的问题。所以可以归纳。
设（用越界下标指代不存在的点）表示一开始有个球时，从左往右第个（从右往左第个）球那边那个线段被经过次数的期望值。于是显然有如下递推式：

于是可以递归说明，于是递推式变为

  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;
  9. const ul mod = 998244353;
  11. ul plus(ul a, ul b)
  12. {
  13.     return a + b < mod ? a + b : a + b - mod;
  14. }
  16. ul mul(ul a, ul b)
  17. {
  18.     return ull(a) * ull(b) % mod;
  19. }
  21. void exgcd(li a, li b, li& x, li&y)
  22. {
  23.     if (b) {
  24.         exgcd(b, a % b, y, x);
  25.         y -= a / b * x;
  26.     } else {
  27.         x = 1;
  28.         y = 0;
  29.     }
  30. }
  32. ul inverse(ul a)
  33. {
  34.     li x, y;
  35.     exgcd(a, mod, x, y);
  36.     return x < 0 ? x + li(mod) : x;
  37. }
  39. const ul maxn = 3e3;
  41. ul n;
  43. ul ans[maxn + 1][maxn + 1];
  45. std::stringstream iss;
  46. std::stringstream oss;
  48. std::string instr;
  50. ul inv[maxn + maxn + 1];
  52. int main()
  53. {
  54.     std::ios::sync_with_stdio(false);
  55.     std::cin.tie(0);
  56.     iss.tie(0);
  57.     oss.tie(0);
  58.     std::getline(std::cin, instr, char(0));
  59.     iss.str(instr);
  60.     for (ul i = 1; i <= maxn + maxn; ++i) {
  61.         inv[i] = inverse(i);
  62.     }
  63.     for (ul x = 1; x <= maxn; ++x) {
  64.         for (ul y = 1; x + y - 1 <= maxn; ++y) {
  65.             ans[x][y] = mul(plus(plus(mul(x + x - 1, ans[x - 1][y]), mul(y + y - 1, ans[x][y - 1])), 1), inv[x + x + y + y - 2]);
  66.         }
  67.     }
  68.     iss >> T;
  69.     for (ul Case = 1; Case <= T; ++Case) {
  70.         iss >> n;
  71.         ul out = 0;
  72.         li x;
  73.         iss >> x;
  74.         for (ul i = 1; i <= n; ++i) {
  75.             li y;
  76.             iss >> y >> y;
  77.             out = plus(out, mul(ans[i][n - i + 1], (y - x) % mod));
  78.             x = y;
  79.         }
  80.         oss << out << std::endl;
  81.     }
  82.     std::cout << oss.str();
  83.     return 0;
  84. }

F、Flower 6849

关于官方题解：
首先考虑如下三个问题：①从朵花中选择一些，使得它们占据的点集不相交，最大化选择的花的权值和；②给朵花分别赋予一个非负实数“选择程度”，满足对任何结点，拥有该节点的花的“选择程度”的和小于等于，最大化每朵花的选择程度与其权值的积的和；③给个节点分别赋予一个非负实权值，满足对每朵花，其拥有的结点的权值和大于这朵花的权值，最小化节点的权值和。
于是第一个问题的限制条件强于第二个，于是第一个问题的最优解的值小于等于第二个，但是我不知道怎么证明相等（可以找到系数矩阵不全幺模的例子，所以不能用全幺模这么强的判定方法，不过个人发现生效了的约束好像是全幺模的，但我也不知道怎么证）。而第二个问题和第三个问题是在线性规划意义上对偶的，根据强对偶定理，第二个问题的最优解一定等于第三个。

所以直接动态规划，用表示只考虑以为根的子树完全包含的花所能具有的最大答案，那么转移就有两种来历，一种是直接将赋给，另一种是考虑所有最浅点是的花，要查询出距离为的所有子树中的点的值之和，然后加上，得到的值就是选择这朵花的最大价值，要做到这一点，直接点分治即可。

  1. #include <bits/stdc++.h>
  3. using ul = std::uint32_t;
  4. using li = std::int32_t;
  5. using ull = std::uint64_t;
  6. using ll = std::int64_t;
  8. ul T;
  10. const ul maxn = 1e5;
  11. const ul maxm = 1e5;
  13. ul n;
  14. ul m;
  16. ul x[maxm + 1], r[maxm + 1], v[maxm + 1];
  18. class circle_t {
  19. public:
  20.     ul x = 0;
  21.     ul r = 0;
  22.     ul v = 0;
  23.     circle_t()=default;
  24.     circle_t(ul a, ul b, ul c): x(a), r(b), v(c) {}
  25. };
  27. std::vector<circle_t> circles[maxn + 1];
  29. std::vector<ul> edge[maxn + 1];
  31. std::stringstream iss;
  32. std::stringstream oss;
  34. std::string instr;
  36. ul rk[maxn + 1];
  38. class belong_t {
  39. public:
  40.     ul center = 0;
  41.     ul type = 0;
  42.     ul dis = 0;
  43.     belong_t()=default;
  44.     belong_t(ul a, ul b, ul c): center(a), type(b), dis(c) {}
  45. };
  47. std::vector<belong_t> belong[maxn + 1];
  48. std::vector<std::vector<ull>> val[maxn + 1];
  49. std::vector<ull> valsum[maxn + 1];
  50. ull val0[maxn + 1];
  52. ul getsz(ul curr, ul prev)
  53. {
  54.     ul ret = 1;
  55.     for (ul next : edge[curr]) {
  56.         if (next == prev) {
  57.             continue;
  58.         }
  59.         if (rk[next]) {
  60.             continue;
  61.         }
  62.         ret += getsz(next, curr);
  63.     }
  64.     return ret;
  65. }
  67. void search1(ul curr, ul prev, ul fullsz, ul& currsz, ul& mnmxsz, ul& mnmxszid)
  68. {
  69.     currsz = 1;
  70.     ul mxsz = 0;
  71.     for (ul next : edge[curr]) {
  72.         if (next == prev) {
  73.             continue;
  74.         }
  75.         if (rk[next]) {
  76.             continue;
  77.         }
  78.         ul nextsz;
  79.         search1(next, curr, fullsz, nextsz, mnmxsz, mnmxszid);
  80.         currsz += nextsz;
  81.         mxsz = std::max(mxsz, nextsz);
  82.     }
  83.     mxsz = std::max(mxsz, fullsz - currsz);
  84.     if (mnmxsz > mxsz) {
  85.         mnmxszid = curr;
  86.         mnmxsz = mxsz;
  87.     }
  88. }
  90. ul search2(ul curr, ul prev, ul center, ul type, ul dis)
  91. {
  92.     ul ret = 0;
  93.     belong[curr].push_back(belong_t(center, type, dis));
  94.     for (ul next : edge[curr]) {
  95.         if (next == prev) {
  96.             continue;
  97.         }
  98.         if (rk[next]) {
  99.             continue;
  100.         }
  101.         ret = std::max(search2(next, curr, center, type, dis + 1), ret);
  102.     }
  103.     return ret + 1;
  104. }
  106. ull querysum(ul x, ul dis)
  107. {
  108.     ull ret = 0;
  109.     for (const auto& b : belong[x]) {
  110.         if (b.dis == dis) {
  111.             ret += val0[b.center];
  112.         } else if (b.dis < dis) {
  113.             if (valsum[b.center].size() > dis - b.dis) {
  114.                 ret += valsum[b.center][dis - b.dis];
  115.                 if (val[b.center][b.type].size() > dis - b.dis) {
  116.                     ret -= val[b.center][b.type][dis - b.dis];
  117.                 }
  118.             }
  119.         }
  120.     }
  121.     if (valsum[x].size() > dis) {
  122.         ret += valsum[x][dis];
  123.     }
  124.     return ret;
  125. }
  127. void change(ul x, ull v)
  128. {
  129.     for (const auto& b : belong[x]) {
  130.         valsum[b.center][b.dis] += v;
  131.         val[b.center][b.type][b.dis] += v;
  132.     }
  133.     val0[x] += v;
  134. }
  136. ul depth[maxn + 1];
  137. ul fa[maxn + 1][17];
  139. void search3(ul curr, ul prev)
  140. {
  141.     for (ul i = 1; (1 << i) <= depth[curr]; ++i) {
  142.         fa[curr][i] = fa[fa[curr][i - 1]][i - 1];
  143.     }
  144.     for (ul next : edge[curr]) {
  145.         if (next == prev) {
  146.             continue;
  147.         }
  148.         depth[next] = depth[curr] + 1;
  149.         fa[next][0] = curr;
  150.         search3(next, curr);
  151.     }
  152. }
  154. void search4(ul curr, ul prev)
  155. {
  156.     ull ans = 0;
  157.     for (ul next : edge[curr]) {
  158.         if (next == prev) {
  159.             continue;
  160.         }
  161.         search4(next, curr);
  162.         ans += val0[next];
  163.     }
  164.     for (const auto& c : circles[curr]) {
  165.         ans = std::max(ans, c.v + querysum(c.x, c.r + 1));
  166.     }
  167.     change(curr, ans);
  168. }
  170. int main()
  171. {
  172.     std::ios::sync_with_stdio(false);
  173.     std::cin.tie(0);
  174.     iss.tie(0);
  175.     oss.tie(0);
  176.     std::getline(std::cin, instr, char(0));
  177.     iss.str(instr);
  178.     iss >> T;
  179.     for (ul Case = 1; Case <= T; ++Case) {
  180.         iss >> n >> m;
  181.         for (ul i = 1; i <= n; ++i) {
  182.             edge[i].resize(0);
  183.             rk[i] = 0;
  184.             belong[i].resize(0);
  185.             val[i].resize(0);
  186.             valsum[i].resize(0);
  187.             val0[i] = 0;
  188.             circles[i].resize(0);
  189.         }
  190.         for (ul i = 1; i <= n - 1; ++i) {
  191.             ul u, v;
  192.             iss >> u >> v;
  193.             edge[u].push_back(v);
  194.             edge[v].push_back(u);
  195.         }
  196.         for (ul i = 1; i <= m; ++i) {
  197.             iss >> x[i] >> r[i] >> v[i];
  198.         }
  199.         for (ul i = 1; i <= n; ++i) {
  200.             while (!rk[i]) {
  201.                 ul sz = getsz(i, 0);
  202.                 ul mnmxsz = sz;
  203.                 ul mnmxszid = i;
  204.                 ul tmp;
  205.                 search1(i, 0, sz, tmp, mnmxsz, mnmxszid);
  206.                 rk[mnmxszid] = sz;
  207.                 ul maxmaxlen = 0;
  208.                 for (ul next : edge[mnmxszid]) {
  209.                     if (rk[next]) {
  210.                         continue;
  211.                     }
  212.                     ul maxlen = search2(next, 0, mnmxszid, val[mnmxszid].size(), 1);
  213.                     val[mnmxszid].push_back(std::vector<ull>(maxlen + 1, 0));
  214.                     maxmaxlen = std::max(maxlen, maxmaxlen);
  215.                 }
  216.                 valsum[mnmxszid].resize(maxmaxlen + 1, 0);
  217.             }
  218.         }
  219.         depth[1] = 0;
  220.         search3(1, 0);
  221.         for (ul i = 1; i <= m; ++i) {
  222.             if (r[i] > depth[x[i]]) {
  223.                 circles[1].push_back(circle_t(x[i], r[i], v[i]));
  224.             } else {
  225.                 ul tmpx = x[i];
  226.                 ul tmpr = r[i];
  227.                 while (tmpr) {
  228.                     ul tmp = __builtin_ctz(tmpr);
  229.                     tmpx = fa[tmpx][tmp];
  230.                     tmpr -= 1 << tmp;
  231.                 }
  232.                 circles[tmpx].push_back(circle_t(x[i], r[i], v[i]));
  233.             }
  234.         }
  235.         search4(1, 0);
  236.         oss << val0[1] << '\n';
  237.     }
  238.     std::cout << oss.str();
  239.     return 0;
  240. }

G、Game 6850

官方题解如下：
image.png-12.9kB
image.png-206.6kB
image.png-61.5kB

直接使用方法二做，证明很容易，只要注意到必胜策略同样适用于“无视重复”的情况。

  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 us = std::uint16_t;
  9. ul T;
  11. const ul maxn = 2000;
  13. ul n;
  15. li x[maxn + 1], y[maxn + 1];
  17. ll dis[maxn + 1][maxn + 1];
  19. std::vector<std::pair<us, us>> edges(maxn * maxn);
  21. bool ans[maxn + 1][maxn + 1];
  23. bool suf[maxn + 1];
  25. ll sqr(ll a)
  26. {
  27.     return a * a;
  28. }
  30. std::stringstream iss;
  31. std::stringstream oss;
  32. std::string instr;
  34. int main()
  35. {
  36.     std::ios::sync_with_stdio(false);
  37.     std::cin.tie(0);
  38.     iss.tie(0);
  39.     oss.tie(0);
  40.     std::freopen("G.in", "r", stdin);
  41.     std::getline(std::cin, instr, char(0));
  42.     iss.str(instr);
  43.     iss >> T;
  44.     for (ul Case = 1; Case <= T; ++Case) {
  45.         iss >> n;
  46.         edges.resize(0);
  47.         for (ul i = 1; i <= n; ++i) {
  48.             iss >> x[i] >> y[i];
  49.             suf[i] = true;
  50.             for (ul j = 1; j != i; ++j) {
  51.                 dis[i][j] = sqr(x[i] - x[j]) + sqr(y[i] - y[j]);
  52.                 edges.push_back(std::pair<us, us>(i, j));
  53.             }
  54.         }
  55.         std::sort(edges.begin(), edges.end(), [&](const std::pair<us, us>& a, const std::pair<us, us>& b){return dis[a.first][a.second] > dis[b.first][b.second];});
  56.         for (ul l = 0, r = 0; l != edges.size(); l = r) {
  57.             for ( ; r != edges.size() && dis[edges[l].first][edges[l].second] == dis[edges[r].first][edges[r].second]; ++r);
  58.             for (ul i = l; i != r; ++i) {
  59.                 ans[edges[i].first][edges[i].second] = !suf[edges[i].second];
  60.                 ans[edges[i].second][edges[i].first] = !suf[edges[i].first];
  61.             }
  62.             for (ul i = l; i != r; ++i) {
  63.                 suf[edges[i].first] = suf[edges[i].first] && ans[edges[i].first][edges[i].second];
  64.                 suf[edges[i].second] = suf[edges[i].second] && ans[edges[i].second][edges[i].first];
  65.             }
  66.         }
  67.         oss << (suf[1] ? "NO\n" : "YES\n");
  68.     }
  69.     std::freopen("out.txt", "w", stdout);
  70.     std::cout << oss.str();
  71.     return 0;
  72. }

H、Heart 6851

关于如何实现计算

请自己搜索集合幂级数中的集合无交并卷积。

现将上述运算简记为。

现在设表示允许使用这些碎片且碎片集合刚好为的所有符卡的伤害之和，那么显然，，其中表示碎片编号最大为，且碎片集合刚好为的所有弹幕的伤害之和。而则等于所有无需碎片的弹幕的伤害加一之积。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. const ul mod = 998244353;
  14. ul plus(ul a, ul b)
  15. {
  16.     return a + b < mod ? a + b : a + b - mod;
  17. }
  19. ul minus(ul a, ul b)
  20. {
  21.     return a < b ? a + mod - b : a - b;
  22. }
  24. ul mul(ul a, ul b)
  25. {
  26.     return ull(a) * ull(b) % mod;
  27. }
  29. ul v[1 << 21][22];
  31. ul ans[1 << 21][22];
  33. std::vector<std::pair<ul, ul>> danmaku[21];
  35. int main()
  36. {
  37.     std::ios::sync_with_stdio(false);
  38.     std::cin.tie(0);
  39.     iss.tie(0);
  40.     oss.tie(0);
  41.     std::getline(std::cin, instr, char(0));
  42.     iss.str(instr);
  43.     ans[0][0] = 1;
  44.     ul n;
  45.     iss >> n;
  46.     for (ul i = 1; i <= n; ++i) {
  47.         ul p, b;
  48.         iss >> p >> b;
  49.         if (b == 0) {
  50.             ans[0][0] = mul(ans[0][0], plus(p, 1));
  51.         } else {
  52.             danmaku[31 - __builtin_clz(b)].push_back(std::pair<ul, ul>(p, b));
  53.         }
  54.     }
  55.     for (ul cnt = 1; cnt <= 21; ++cnt) {
  56.         for (const auto& p : danmaku[cnt - 1]) {
  57.             v[p.second][__builtin_popcount(p.second)] = plus(v[p.second][__builtin_popcount(p.second)], p.first);
  58.         }
  59.         v[0][0] = 1;
  60.         for (ul i = 0; i != cnt; ++i) {
  61.             ul set = (1 << cnt) - 1 & ~(1 << i);
  62.             for (ul sub = set; ; sub = sub - 1 & set) {
  63.                 for (ul t = 0; t <= cnt; ++t) {
  64.                     v[sub | 1 << i][t] = plus(v[sub | 1 << i][t], v[sub][t]);
  65.                     ans[sub | 1 << i][t] = plus(ans[sub | 1 << i][t], ans[sub][t]);
  66.                 }
  67.                 if (!sub) {
  68.                     break;
  69.                 }
  70.             }
  71.         }
  72.         for (ul set = 0; set != (1 << cnt); ++set) {
  73.             for (ul sz = cnt; ~sz; --sz) {
  74.                 ul tmp = 0;
  75.                 for (ul i = 0; i <= sz; ++i) {
  76.                     tmp = plus(tmp, mul(v[set][i], ans[set][sz - i]));
  77.                 }
  78.                 ans[set][sz] = tmp;
  79.             }
  80.         }
  81.         for (ul i = 0; i != cnt; ++i) {
  82.             ul set = (1 << cnt) - 1 & ~(1 << i);
  83.             for (ul sub = set; ; sub = sub - 1 & set) {
  84.                 for (ul t = 0; t <= cnt; ++t) {
  85.                     ans[sub | 1 << i][t] = minus(ans[sub | 1 << i][t], ans[sub][t]);
  86.                 }
  87.                 if (!sub) {
  88.                     break;
  89.                 }
  90.             }
  91.         }
  92.         std::memset(v, 0, sizeof(ul) * 22 << cnt);
  93.     }
  94.     ul m;
  95.     iss >> m;
  96.     for (ul i = 1; i <= m; ++i) {
  97.         ul x;
  98.         iss >> x;
  99.         oss << ans[x][__builtin_popcount(x)] << '\n';
  100.     }
  101.     std::cout << oss.str();
  102.     return 0;
  103. }

I、Increasing and Decreasing 6852

官方题解如下：
image.png-172.9kB
其中“证明显然”并不显然。首先考虑狄尔沃斯定理，于是知道长为的置换的最长上升子序列的长度正好就是最小下降序列覆盖的大小，也就是说，其可以被拆为个长度不超过最长下降子序列的长度的子序列的并，故。
而这一结果确实是字典序最小的这一点的证明如下：考虑对使用归纳法。（的情况显然）
设。
如果，那么，于是直接可以把问题约归为的问题。
如果，那么由于必须将序列分为个下降子列的并，而每个下降子列长度不超过，这意味着所属的下降子列的长度至少为，于是至少是，于是问题被约归为的问题。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T;
  13. ul n, x, y;
  14. const ul maxn = 1e5;
  15. ul ans[maxn + 1];
  17. int main()
  18. {
  19.     std::ios::sync_with_stdio(false);
  20.     std::cin.tie(0);
  21.     iss.tie(0);
  22.     oss.tie(0);
  23.     std::getline(std::cin, instr, char(0));
  24.     iss.str(instr);
  25.     iss >> T;
  26.     for (ul Case = 1; Case <= T; ++Case) {
  27.         iss >> n >> x >> y;
  28.         if (ull(x) * y < n || x + y - 1 > n) {
  29.             oss << "NO\n";
  30.             continue;
  31.         }
  32.         oss << "YES\n";
  33.         ul a = x, b = y;
  34.         for (ul i = 1; i <= n; ++i) {
  35.             ans[i] = i;
  36.         }
  37.         if (b != 1) {
  38.             ul q = (n - a + b - 2) / (b - 1);
  39.             std::reverse(ans + a - q + 1, ans + n - (q - 1) * b + 1);
  40.             for (ul i = 1; i <= q - 1; ++i) {
  41.                 std::reverse(ans + n - i * b + 1, ans + n - (i - 1) * b + 1);
  42.             }
  43.         }
  44.         for (ul i = 1; i <= n; ++i) {
  45.             if (i != 1) {
  46.                 oss << ' ';
  47.             }
  48.             oss << ans[i];
  49.         }
  50.         oss << '\n';
  51.     }
  52.     std::cout << oss.str();
  53.     return 0;
  54. }

J、Jogging 6853

官方题解如下：
image.png-332.6kB
其实关于时间复杂度的证明稍微有点问题。因为中不止需要是质数，而且不能落在中，当然到底怎么证明不清楚。

  1. #include <bits/stdc++.h>
  3. std::stringstream iss;
  4. std::stringstream oss;
  5. std::string instr;
  7. using ul = std::uint32_t;
  8. using li = std::int32_t;
  9. using ull = std::uint64_t;
  10. using ll = std::int64_t;
  12. ul T;
  14. ll gcd(ll a, ll b)
  15. {
  16.     while (b) {
  17.         b ^= a ^= b ^= a %= b;
  18.     }
  19.     return a;
  20. }
  22. class vec {
  23. public:
  24.     ll x = 0;
  25.     ll y = 0;
  26.     vec()=default;
  27.     vec(ll a, ll b): x(a), y(b) {}
  28. };
  30. bool operator<(const vec& a, const vec& b)
  31. {
  32.     return a.x != b.x ? a.x < b.x : a.y < b.y;
  33. }
  35. vec operator+(const vec& a, const vec& b)
  36. {
  37.     return vec(a.x + b.x, a.y + b.y);
  38. }
  40. const std::vector<vec> dirs = {vec(-1, -1), vec(-1, 0), vec(-1, 1), vec(0, -1), vec(0, 0), vec(0, 1), vec(1, -1), vec(1, 0), vec(1, 1)};
  42. vec s;
  44. std::deque<vec> queue;
  46. std::set<vec> set;
  48. int main()
  49. {
  50.     std::ios::sync_with_stdio(false);
  51.     std::cin.tie(0);
  52.     iss.tie(0);
  53.     oss.tie(0);
  54.     std::getline(std::cin, instr, char(0));
  55.     iss.str(instr);
  56.     iss >> T;
  57.     for (ul Case = 1; Case <= T; ++Case) {
  58.         iss >> s.x >> s.y;
  59.         if (s.x == s.y) {
  60.             oss << "0/1\n";
  61.             continue;
  62.         }
  63.         while (queue.size()) {
  64.             queue.pop_front();
  65.         }
  66.         set.clear();
  67.         queue.push_back(s);
  68.         set.insert(s);
  69.         ul cnt1 = 0, cnt2 = 0;
  70.         for (const auto& dir : dirs) {
  71.             auto next = s + dir;
  72.             if (gcd(next.x, next.y) > 1) {
  73.                 ++cnt1;
  74.             }
  75.         }
  76.         bool flag = false;
  77.         while (queue.size()) {
  78.             auto curr = queue.front();
  79.             queue.pop_front();
  80.             for (const auto& dir : dirs) {
  81.                 auto next = curr + dir;
  82.                 if (next.x == next.y) {
  83.                     oss << "0/1\n";
  84.                     flag = true;
  85.                     break;
  86.                 }
  87.                 ll g = gcd(next.x, next.y);
  88.                 if (g > 1) {
  89.                     ++cnt2;
  90.                 }
  91.                 if (g > 1 && set.insert(next).second) {
  92.                     queue.push_back(next);
  93.                 }
  94.             }
  95.             if (flag) {
  96.                 break;
  97.             }
  98.         }
  99.         if (!flag) {
  100.             ul g = gcd(cnt1, cnt2);
  101.             oss << cnt1 / g << '/' << cnt2 / g << '\n';
  102.         }
  103.     }
  104.     std::cout << oss.str();
  105.     return 0;
  106. }

K、Kcats 6854

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

  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. void exgcd(li a, li b, li& x, li& y)
  30. {
  31.     if (b) {
  32.         exgcd(b, a % b, y, x);
  33.         y -= a / b * x;
  34.     } else {
  35.         x = 1;
  36.         y = 0;
  37.     }
  38. }
  40. ul inverse(ul a)
  41. {
  42.     li x, y;
  43.     exgcd(a, mod, x, y);
  44.     return x < 0 ? x + li(mod) : x;
  45. }
  47. ul T;
  49. ul n;
  51. const ul maxn = 100;
  53. li a[maxn + 1];
  55. ul fac[maxn + 1];
  56. ul fiv[maxn + 1];
  58. ul ans[maxn + 2][maxn + 2][maxn + 1];
  59. ul al[maxn + 2][maxn + 2][maxn + 1];
  60. ul tim = 0;
  62. ul sbi(ul a, ul b)
  63. {
  64.     return mul(fac[a + b], mul(fiv[a], fiv[b]));
  65. }
  67. void search(ul dep, ul l, ul r)
  68. {
  69.     if (tim == al[dep][l][r]) {
  70.         return;
  71.     }
  72.     al[dep][l][r] = tim;
  73.     if (r < l) {
  74.         ans[dep][l][r] = 1;
  75.         return;
  76.     }
  77.     ans[dep][l][r] = 0;
  78.     for (ul i = l; i <= r; ++i) {
  79.         if (~a[i] && a[i] != dep) {
  80.             continue;
  81.         }
  82.         if (i + i < l + r) {
  83.             search(dep, l, i - 1);
  84.             if (!ans[dep][l][i - 1]) {
  85.                 continue;
  86.             }
  87.             search(dep + 1, i + 1, r);
  88.             if (!ans[dep + 1][i + 1][r]) {
  89.                 continue;
  90.             }
  91.         } else {
  92.             search(dep + 1, i + 1, r);
  93.             if (!ans[dep + 1][i + 1][r]) {
  94.                 continue;
  95.             }
  96.             search(dep, l, i - 1);
  97.             if (!ans[dep][l][i - 1]) {
  98.                 continue;
  99.             }
  100.         }
  101.         ans[dep][l][r] = plus(ans[dep][l][r], mul(mul(ans[dep][l][i - 1], ans[dep + 1][i + 1][r]), sbi(i - l, r - i)));
  102.     }
  103. }
  105. int main()
  106. {
  107.     std::ios::sync_with_stdio(false);
  108.     std::cin.tie(0);
  109.     iss.tie(0);
  110.     oss.tie(0);
  111.     std::getline(std::cin, instr, char(0));
  112.     iss.str(instr);
  113.     fac[0] = 1;
  114.     for (ul i = 1; i <= maxn; ++i) {
  115.         fac[i] = mul(fac[i - 1], i);
  116.     }
  117.     fiv[maxn] = inverse(fac[maxn]);
  118.     for (ul i = maxn; i >= 1; --i) {
  119.         fiv[i - 1] = mul(fiv[i], i);
  120.     }
  121.     iss >> T;
  122.     for (ul Case = 1; Case <= T; ++Case) {
  123.         iss >> n;
  124.         for (ul i = 1; i <= n; ++i) {
  125.             iss >> a[i];
  126.         }
  127.         ++tim;
  128.         search(1, 1, n);
  129.         oss << ans[1][1][n] << '\n';
  130.     }
  131.     std::cout << oss.str();
  132.     return 0;
  133. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注