owned this note
owned this note
Published
Linked with GitHub
# Code Ton round2 題解
先聲明這篇題解不是我寫的,我只負責把他從簡體中文翻譯成繁體中文XD
(~~基本上就是Google翻譯完檢查一下而已~~)
(UPD: 我錯了,latex不能複製貼上,要重打好累QQ)
## A Two 0-1 sequences
第一個字串後$m-1$位必須和第二個字串一樣,前面的位只要有一個第二個字串的第一個字符就行。
後來加的題,沒代碼
## B Luke is a foodie
直接順著掃到第一個不存在合法的 $v$ 的區間給答案 +1,然後從這裡再開始做就行。
:::spoiler Code
```cpp=
#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
把所有未被感染的連續段拉出來,一定是從長的開始,堵上兩邊,模擬就行。
:::spoiler Code
```cpp=
#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$算一下就行。
:::spoiler Code
```cpp=
#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$輪,然後算出最後到達匯點的值就行。
:::spoiler Code
```cpp=
#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,但之前數據太水了過了,懶得改了。~~
:::spoiler Code
```cpp=
#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)$。
:::spoiler Code
```cpp=
#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';
}
```
:::