Code Ton round2 題解

先聲明這篇題解不是我寫的，我只負責把他從簡體中文翻譯成繁體中文XD
(~~基本上就是Google翻譯完檢查一下而已~~)
(UPD: 我錯了，latex不能複製貼上，要重打好累QQ)

A Two 0-1 sequences

第一個字串後\(m-1\)位必須和第二個字串一樣，前面的位只要有一個第二個字串的第一個字符就行。

後來加的題，沒代碼

B Luke is a foodie

直接順著掃到第一個不存在合法的 \(v\) 的區間給答案 +1，然後從這裡再開始做就行。

Code































#include <cstdio>
#include <iostream>

using namespace std;

int n, d;

void solve() {
  cin >> n >> d;
  int ans = 0, l = 0, r = 2e9;
  while (n--) {
    int x;
    cin >> x;
    int a = x - d, b = x + d;
    if (b < l || a > r) {
      ans++;
      l = a, r = b;
    } else
      l = max(l, a), r = min(r, b);
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
}

C Virus

把所有未被感染的連續段拉出來，一定是從長的開始，堵上兩邊，模擬就行。

Code






































#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int N = 100005;
int n, m, a[N], b[N];

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
    cin >> a[i];
  sort(a + 1, a + m + 1);
  b[1] = a[1] - 1 + n - a[m];
  for (int i = 2; i <= m; i++)
    b[i] = a[i] - a[i - 1] - 1;
  sort(b + 1, b + m + 1, greater<int>());
  int sum = 0;
  for (int i = 1; i <= m; i++) {
    b[i] -= 4 * (i - 1);
    if (b[i] == 1)
      sum += 1;
    if (b[i] > 1)
      sum += b[i] - 1;
  }
  cout << n - sum << '\n';
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
}

D Magical Array

感覺挺妙的，Anton 4min 就秒了，外國老哥這方面都挺強。我想了很長時間（至少20min），智商不太夠。

發現對於\(s = \sum_{i=1}^{k} ia_i\)，操作一不會改變，而操作二會使\(s\)加上\(1\)，把每個數組的\(s\)算一下就行。

Code




































#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int n, m;

void solve() {
  cin >> n >> m;
  long long mn = 1ll << 60, mx = 0;
  int p = 0;
  for (int i = 1; i <= n; i++) {
    long long s = 0;
    for (int j = 1; j <= m; j++) {
      long long x;
      cin >> x;
      s += x * j;
    }
    if (s < mn)
      mn = s;
    if (s > mx)
      mx = s, p = i;
  }
  cout << p << ' ' << mx - mn << '\n';
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
}

E Count Seconds

先跑遍拓撲，然後發現\(n\)輪之後如果一個點有，那麼它能到達的所有點一定有。所以暴力模擬前\(n\)輪，然後算出最後到達匯點的值就行。

Code




















































































#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int N = 1005, mod = 998244353;
int n, m, a[N], in[N];
bool u[N];
vector<int> to[N];

int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }

bool check() {
  for (int i = 1; i <= n; i++)
    if (a[i] > 0)
      return 1;
  return 0;
}

void solve() {
  static int q[N];
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  while (m--) {
    int x, y;
    cin >> x >> y;
    to[x].push_back(y);
    in[y]++;
  }

  int t = 0;
  while ((++t) <= n) {
    for (int i = 1; i <= n; i++)
      if (in[i] == 0 && u[i] == 0) {
        u[i] = 1, q[t] = i;
        for (int j : to[i])
          in[j]--;
        break;
      }
  }
  for (int i = 1; i <= n; i++)
    u[i] = 0;

  int ans = 0;
  while (ans <= n && check()) {
    ans++;
    for (int i = n; i; i--)
      if (a[q[i]]) {
        a[q[i]]--;
        for (int j : to[q[i]])
          a[j]++;
      }
  }
  if (!check()) {
    cout << ans << '\n';
    return;
  }

  for (int i = 1; i <= n; i++) {
    a[q[i]] %= mod;
    for (int j : to[q[i]])
      a[j] = add(a[j], a[q[i]]);
  }
  cout << add(ans, a[q[n]]) << '\n';
}

void clear() {
  for (int i = 1; i <= n; i++)
    to[i].clear();
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int t;
  cin >> t;
  while (t--) {
    solve();
    clear();
  }
}

F Colouring Game

也挺妙的，完全不會了。

可以發現如果顏色個數不相等，那麼誰的多誰就贏，因為剛開始一定是雙方將一個RB 或BR 刪掉，然後沒了之後再每次刪掉自己的一個顏色，那一定是個數少的人先輸。

不然兩個人個數相等，就是比每次刪一個RB 或BR，看誰先不能操作，就只能刪自己的一個，然後輸了。

把每個RB 相間的段提出來，因為刪的是兩個不同顏色，所以雙方操作集合相同，是個公平博弈。直接對所有長度算出所有sg 就行。

暴力sg 是\(O(n^2)\)的，但是打表之後能發現一個有個在三十左右的\(len\)，sg 在\(3 \times len\)及以後有長為\(len\)的循環節，所以打前面一些就行。

~~這份代碼是錯的，因為沒有對\(3 \times len\)取min，但之前數據太水了過了，懶得改了。~~

Code



















































#include <cstdio>
#include <iostream>

using namespace std;

int n, f[103];
char a[500005];

void prep() {
  for (int i = 2; i <= 102; i++) {
    bool u[10] = {0};
    for (int j = 1; j != i; j++)
      u[f[j - 1] ^ f[i - j - 1]] = 1;
    for (int x = 0;; x++)
      if (!u[x]) {
        f[i] = x;
        break;
      }
  }
}

void solve() {
  cin >> n >> (a + 1);
  int s = 0, ans = 0;
  for (int i = 1, j; i <= n; i = j + 1) {
    for (j = i; j < n && a[j] != a[j + 1]; j++)
      ;
    ans ^= f[j - i + 1];
  }
  for (int i = 1; i <= n; i++)
    if (a[i] == 'R')
      s++;
    else
      s--;
  if (s > 0 || (s == 0 && ans))
    cout << "Alice\n";
  else
    cout << "Bob\n";
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  prep();

  int t;
  cin >> t;
  while (t--)
    solve();
}

G Mio and Lucky Array

忽略一些細節，只講大致思路。

將\(a\)和\(b\)的偶數位取反，於是操作變成根據操作開始位置的奇偶性給後面加或減\(1,2,...\)。然後做二階差分，枚舉一個開始位置，就要求從這里之後\(a\)和\(b\)對位相差不超過一，且根據奇偶性是\(a_i \leq b_j \leq a_i+1\)或\(b_j \leq a_i \leq b_j+1\)。這個是類似經典的fft 做字符串匹配，可能要設計一個權值，不然平方的話值大於\(998244353\)可能在模意義下被判為合法。

還有差分之前的兩位是要特殊判的，大概就是開始位置前面操作的帶符號和。\(i+1\)位和\(i\)的差告訴了奇數位操作次數- 偶數位操作次數，而告訴了奇數位操作位置和- 偶數位操作位置和。由於操作是連續的，也就是說是\(1,2,3,4,...i\)都可以操作，所以最後確定了操作次數的差，就可以貪心算出在這個差下\(a_i\)可能的最小值和最大值，而在這之間奇偶性相同應該都可以取到，判一下\(a_i\)是否在這個區間裡即可。

~~這題是後來加的，所以口胡，沒代碼。~~

H Game of AI

建立一張有向圖，\(i\)指向\(a_i\)，那麼就得到了一個基環樹森林。考慮計算這個基環樹森林的答案，那麼對於環之外的每個點，如果它沒有被孩子佔領，那麼它的孩子一定會它孩子的孩子佔領。於是可以\(F_0(x), F_1(x)\)設分別表示自己被孩子佔領/不被孩子佔領的樹的生成函數（EGF），那麼則有：

\(F_0(x) = x(F_0(x) + F_1(x))exp(F_0(x) + F_1(x))\) (\(1\))
\(F_1(x) = xexpF_0(x)\) (\(2\))

\(F_0(x)\)遞推即為確定被哪個孩子佔領，\(F_1(x)\)就是孩子全部被孩子的孩子佔領。

將(\(2\))帶入(\(1\))即可得到\(F_0(x)\)的方程，牛頓迭代即可得到\(F_0(x)\)，進而得到\(F_1(x)\)。

現在考慮把樹拼起來變成一棵基環樹。我們設在環上的一個點和它的子樹，它被佔領/不被佔領的生成函數為\(G_0(x), G_1(x)\)，那麼考慮一個點是被自己的孩子佔領還是被環上的上一個點佔領，生成函數就是\(G_0(x)=F_0(x)+F_1(x)\)。

考慮環上每一個點，如果某個點沒有被別人佔領那麼它在環上的後一個點一定會被佔領。那麼如果一個點它沒有被別的點佔領，我們就在後面強制拼上一個被佔領的點，即\(G_1(x)=F_1(x)+G_0(x)\)。

對於環還有一個限制，就是不能環上的每一個點都被它在環上的前一個點佔領。可以證明一個環合法當且僅當這兩個條件成立。

設\(G_2(x)=G_0(x)+G_1(x)\)。先不考慮第二個限制，那麼一個環的生成函數就是：
\(\sum_{i=1}^{+\infty} \frac{G_2(x)^i}{i} - G_0(x)\) = \(-ln(1-G_2(x)) - G_0(x)\)

減掉\(G_0(x)\)是因為環上不能只有一個點。

考慮第二個限制，類似上面可以得到違反第二條限制的生成函數是\(-ln(1-F_1(x))-F_1(x)\)。

兩部分相減得到基環樹的生成函數之後再exp一下就能得到原問題（基環樹森林）的答案了。

時間複雜度\(O(nlogn)\)。

Code














































































































































































































































































































































#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef unsigned long long u64;
typedef __uint128_t u128;

const int o = 18, len = 1 << o, B = 16;
int n, fac[len], ifac[len], iv[len], mod;
int f[len], ef[len], xef[len], a[len], b[len], h[len];

struct fastmod {
  u64 b;
  int m;

  fastmod(int mod) : b(((u128)1 << 64) / mod), m(mod) {}
  int reduce(u64 a) {
    u64 q = ((u128)a * b) >> 64;
    int r = a - q * m;
    return r < m ? r : r - m;
  }
} z(998244353);

int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
int sub(int x, int y) { return x < y ? x + mod - y : x - y; }

int power(int a, int n) {
  int tp = 1;
  while (n) {
    if (n & 1)
      tp = z.reduce(1ll * tp * a);
    a = z.reduce(1ll * a * a), n >>= 1;
  }
  return tp;
}

void prep(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++)
    fac[i] = z.reduce(1ll * fac[i - 1] * i);
  ifac[n] = power(fac[n], mod - 2);
  for (int i = n - 1; i != -1; i--)
    ifac[i] = z.reduce(1ll * ifac[i + 1] * (i + 1));
  for (int i = 1; i <= n; i++)
    iv[i] = z.reduce(1ll * ifac[i] * fac[i - 1]);
  iv[0] = 1;
}

namespace poly {
int I[len], w[len], r[len], up, l;

int findg(int n) {
  static int a[101];
  int cnt = 0, x = n - 1;
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) {
      a[++cnt] = i;
      while (x % i == 0)
        x /= i;
    }
  if (x > 1)
    a[++cnt] = x;

  for (int g = 2;; g++) {
    bool ok = 1;
    for (int i = 1; i <= cnt; i++)
      if (power(g, (n - 1) / a[i]) == 1) {
        ok = 0;
        break;
      }
    if (ok)
      return g;
  }
}

void init() {
  I[0] = 1;
  const int w0 = power(findg(mod), (mod - 1) >> o);
  w[len >> 1] = 1;
  for (int i = (len >> 1) + 1; i != len; i++)
    w[i] = z.reduce(1ll * w[i - 1] * w0);
  for (int i = (len >> 1) - 1; i; i--)
    w[i] = w[i << 1];
  for (int i = 0; i != len; i++)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (o - 1));
}

void ntt(int *a, int n, bool op) {
  static u64 t[len], x, y;
  for (int i = 0; i != n; i += 2) {
    x = a[r[i] >> (o - l)], y = a[r[i + 1] >> (o - l)];
    t[i] = x + y, t[i + 1] = x + mod - y;
  }
  for (int l = 2; l != n; l <<= 1) {
    int *k = w + l;
    for (u64 *f = t; f != t + n; f += l)
      for (int *j = k; j != k + l; j++, f++) {
        u64 x = *f, y = z.reduce(f[l] * *j);
        f[l] = x + mod - y, *f += y;
      }
  }
  if (op) {
    for (int i = 0, x = mod - (mod >> l); i != n; i++)
      a[i] = z.reduce(t[i] * x);
    reverse(a + 1, a + n);
  } else
    for (int i = 0; i != n; i++)
      a[i] = z.reduce(t[i]);
}

void pre(int n) { l = 32 - __builtin_clz(n), up = 1 << l; }

void mul(int *f, int n, int *g, int m, int *h, int q) {
  static int x[len], y[len];
  memcpy(x, f, (n + 1) << 2), memcpy(y, g, (m + 1) << 2);
  pre(n + m), ntt(x, up, 0), ntt(y, up, 0);
  for (int i = 0; i < up; i++)
    h[i] = z.reduce(1ll * x[i] * y[i]);
  ntt(h, up, 1);
  memset(x, 0, up << 2), memset(y, 0, up << 2), fill(h + q + 1, h + up, 0);
}

void div(int *a, int *b, int n, int *f) {
  static int iv[len], x[len], tmp[len];
  static int nb[len << 2], nf[len << 2];
  static u64 s0[len], s1[len];
  if (n <= 16) {
    int x = power(b[0], mod - 2);
    for (int i = 0; i <= n; i++) {
      u64 s = 0;
      for (int j = 0; j != i; j++)
        s += 1ll * f[j] * b[i - j];
      f[i] = z.reduce(1ll * x * (a[i] + mod - z.reduce(s)));
    }
    return;
  }

  int m = 1 << (32 - __builtin_clz(n));
  int k = m >> 4, z = k << 1;
  div(I, b, k - 1, tmp), memcpy(x, a, k << 2);
  memcpy(iv, tmp, k << 2), memset(tmp, 0, k << 2);
  pre(z - 1);
  ntt(iv, up, 0), ntt(x, up, 0);
  for (int i = 0; i != up; i++)
    x[i] = ::z.reduce(1ll * x[i] * iv[i]);
  ntt(x, up, 1);
  memcpy(f, x, k << 2);
  memset(x, 0, up << 2);
  memcpy(nb, b, k << 2);
  ntt(nb, up, 0);
  for (int i = 1;; i++) {
    if (i * k > n) {
      memset(iv, 0, up << 2);
      memset(nb, 0, i * z * 4);
      memset(nf, 0, (i - 1) * z * 4);
      fill(f + n + 1, f + i * k, 0);
      break;
    }
    memcpy(nb + i * z, b + i * k, k << 2);
    memcpy(nf + (i - 1) * z, f + (i - 1) * k, k << 2);
    ntt(nb + i * z, up, 0), ntt(nf + (i - 1) * z, up, 0);
    for (int l1 = 0; l1 != i; l1++)
      for (int j = 0; j != up; j++)
        s0[j] += 1ll * nf[l1 * z + j] * nb[(i - l1) * z + j];
    for (int l1 = 0; l1 != i; l1++)
      for (int j = 0; j != up; j++)
        s1[j] += 1ll * nf[l1 * z + j] * nb[(i - l1 - 1) * z + j];
    for (int j = 0; j != up; j += 2) {
      x[j] = ::z.reduce(s0[j] + ::z.reduce(s1[j]));
      x[j + 1] = ::z.reduce(s0[j + 1] + mod - ::z.reduce(s1[j + 1]));
      s0[j] = s1[j] = s0[j + 1] = s1[j + 1] = 0;
    }
    ntt(x, up, 1);
    memset(x + k, 0, k << 2);
    for (int j = 0; j != k; j++)
      x[j] = sub(a[i * k + j], x[j]);
    ntt(x, up, 0);
    for (int j = 0; j != up; j++)
      x[j] = ::z.reduce(1ll * x[j] * iv[j]);
    ntt(x, up, 1);
    memcpy(f + i * k, x, k << 2);
    memset(x, 0, up << 2);
  }
}

void dcexp(int *a, int l, int r, int n, int *f, int *g, int *h) {
  static u64 s[len];
  static int tp[len];
  if (r - l + 1 <= 32) {
    for (int i = l; i <= r && i <= n; i++) {
      u64 s = 0;
      for (int j = l; j < i; j++) {
        s += 1ll * f[j] * a[i - j];
        if (!(j & 15))
          s = z.reduce(s);
      }
      f[i] = z.reduce(((u64)f[i] + z.reduce(s)) * iv[i]);
    }
    return;
  }
  int *tg[B], *th[B];
  int len = (r - l + 1) / B, k = 2 * len;
  for (int i = 0; i < B - 1; i++)
    tg[i] = g + i * k, th[i] = h + i * k;
  if (!l) {
    pre(k - 1);
    for (int i = 0; i < B - 1; i++) {
      if ((i + 1) * len > n)
        break;
      memcpy(th[i], a + i * len, k << 2);
      ntt(th[i], k, 0);
    }
  }
  for (int i = 0; i < B; i++) {
    if (l + i * len > n)
      break;
    memset(s, 0, k << 3);
    for (int j = 0; j != i; j++)
      for (int t = 0; t != k; t++)
        s[t] += 1ll * tg[j][t] * th[i - j - 1][t];
    for (int t = 0; t != k; t++)
      tp[t] = z.reduce(s[t]);
    pre(k - 1), ntt(tp, k, 1);
    for (int t = 0; t < len; t++)
      f[l + i * len + t] = add(f[l + i * len + t], tp[t + len]);
    dcexp(a, l + i * len, l + (i + 1) * len - 1, n, f, g + k * B, h + k * B);
    if (i != B - 1) {
      memcpy(tg[i], f + l + i * len, len << 2);
      pre(k - 1), ntt(tg[i], k, 0);
    }
  }
  memset(tg[0], 0, (k * B) << 2);
}

void exp(int *a, int n, int *f) {
  static int x[len << 1], v1[len << 2], v2[len << 2];
  for (int i = 1; i <= n; i++)
    x[i] = z.reduce(1ll * a[i] * i);
  f[0] = 1, fill(f + 1, f + n + 1, 0);
  int m = 1 << (32 - __builtin_clz(n));
  dcexp(x, 0, m - 1, n, f, v1, v2);
  memset(x, 0, (n + 1) << 2), fill(f + n + 1, f + m, 0);
}
} // namespace poly

void calc(int n) {
  static int xef[len], eef[len], a[len], b[len], c[len];
  if (n == 2) {
    f[2] = 1;
    return;
  }

  calc((n + 1) / 2);
  poly::exp(f, n - 1, xef);
  for (int i = n; i; i--)
    xef[i] = xef[i - 1];
  xef[0] = 0;
  for (int i = 1; i <= n; i++)
    a[i] = add(xef[i], f[i]);
  poly::exp(a, n - 1, eef);
  for (int i = n; i; i--)
    eef[i] = eef[i - 1];
  eef[0] = 0;
  poly::pre(2 * n);
  int up = poly::up;
  poly::ntt(a, up, 0), poly::ntt(eef, up, 0);
  for (int i = 0; i != up; i++)
    c[i] = z.reduce(1ll * a[i] * eef[i]);
  poly::ntt(c, up, 1), fill(c + n + 1, c + up, 0);
  for (int i = 1; i <= n; i++)
    c[i] = sub(f[i], c[i]);
  xef[0] = 1;
  poly::ntt(xef, up, 0);
  for (int i = 0; i != up; i++)
    b[i] = z.reduce(1ll * xef[i] * (a[i] + 1));
  poly::ntt(b, up, 1);
  fill(b + n + 1, b + up, 0);
  poly::ntt(b, up, 0);
  for (int i = 0; i != up; i++)
    b[i] = z.reduce(1ll * b[i] * eef[i]);
  poly::ntt(b, up, 1);
  fill(b + n + 1, b + up, 0);
  b[0] = 1;
  for (int i = 1; i <= n; i++)
    b[i] = sub(0, b[i]);
  memset(a, 0, up << 2);
  poly::div(c, b, n, a);
  for (int i = 2; i <= n; i++)
    f[i] = sub(f[i], a[i]);

  memset(xef, 0, up << 2), memset(eef, 0, up << 2);
  memset(a, 0, (n + 1) << 2), memset(b, 0, (n + 1) << 2), memset(c, 0, (n + 1) << 2);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> mod, z = fastmod(mod);
  if (n == 1) {
    cout << 0;
    return 0;
  }
  poly::init(), prep(n);

  calc(n);

  poly::exp(f, n, ef);
  for (int i = n; i; i--)
    a[i] = add(f[i], ef[i - 1]);
  poly::exp(a, n, h);
  for (int i = n; i; i--)
    h[i] = h[i - 1];
  h[0] = 0;
  for (int i = 1; i <= n; i++)
    a[i] = add(f[i], h[i]);
  for (int i = n; i; i--)
    xef[i] = ef[i - 1];
  xef[0] = 1;
  poly::mul(a, n, xef, n, a, n);
  a[0] = 1;
  for (int i = 1; i <= n; i++)
    a[i] = sub(0, a[i]);
  poly::mul(a, n, ef, n, a, n);
  h[0] = 1;
  for (int i = 1; i <= n; i++)
    h[i] = sub(0, h[i]);
  poly::div(h, a, n, b);
  for (int i = 1; i <= n; i++)
    cout << z.reduce(1ll * b[i] * fac[i]) << '\n';
}

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.