---
title: IOICamp 2023 Day 3 Contest Editorial
tags: editorial, competitive-programming
---
# IOIC 2023 Day 3 Editorial
## Problem 301
### SOS
為了解釋方便，我們把 $AND$ 符號改成 $\subseteq$，並且會用二進位數字表示集合。
令 $N = \lceil \log_2{n+1} \rceil$，也就是 $n$ 的二進位表示中的位數。整題的 $N \leq 20$
### Subtask 1 ($N \leq 10$)
暴力枚舉，$O(3^N)$ 或 $O(4^N)$ 都可以過。
### Subtask 2 滿分解
令 $g(x) = \bigoplus _ {0 \leq y \ , \ x \subseteq y = y} f(y)$
則，$f(x) = a_x + \sum _ {0 \leq y < x \ , \ x \subseteq \ y = y} g(y)$
令 $F[i][j]$ 代表和 $i$ 的前 $n - j$ 個位元相同的所有子集 $y$ 的 $g(y)$ 的和。
同理，$G[i][j]$ 代表和 $i$ 的前 $n - j$ 個位元相同的所有子集 $y$ 的 $f(y)$ 的和。
那麼可以枚舉 $i$ 由小到大，先計算所有 $F[i][*]$之後得到 $f(i) = F[i][N] + a_i$，再計算所有 $G[i][*]$。
轉移是：
$$
F[i][j] = \begin{cases}
F[i][j-1] &,i \& 2^j = 0\\
F[i][j-1] + F[i \oplus 2^j][j-1] &,\text{otherwise}
\end{cases}
$$
$$
G[i][j] = \begin{cases}
G[i][j-1] &,i \& 2^j = 0\\
G[i][j-1] \oplus G[i \oplus 2^j][j-1] &,\text{otherwise}
\end{cases}
$$
複雜度 $O(2^N N)$
:::spoiler Sample Code
```cpp=
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1050005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
int fs[maxn][21], gs[maxn][21];
ll f[maxn], g[maxn];
const int se = (1<<30)-1;
void madd(int &x, int y) {
x = (x + y) & se;
}
int main() {
io;
int n;
cin >> n;
for (int i = 0;i < n;i++) cin >> f[i];
for (int i = 0;i < n;i++) {
for (int j = 0;j < 20;j++) {
if (j) madd(fs[i][j], fs[i][j-1]);
if ((i>>j)&1) madd(fs[i][j], fs[i ^ (1<<j)][j]);
}
f[i] += fs[i][19];
f[i] &= se;
gs[i][0] ^= f[i];
for (int j = 0;j < 20;j++) {
if (j) gs[i][j] ^= gs[i][j-1];
if ((i>>j)&1) gs[i][j] ^= gs[i ^ (1<<j)][j];
}
g[i] = gs[i][19];
for (int j = 0;j < 20;j++) {
madd(fs[i][j], g[i]);
}
}
cout << f[n-1] << "\n";
}
```
:::
## Problem 302
首先可以將問題轉為對於每個 $k$ ，計算範圍有交的 $k$ 元子集有幾個
對於一堆五維長方體，它們的交集具有體積相當於它們在接下來定義的 $32$ 個平行宇宙中的交的體積乘上該宇宙的係數之和為 $1$ (否則為 $0$ )
具體來說，對 $i$ 從 $0$ 到 $31$ ，第 $i$ 個宇宙中，原本是 $[l_1, r_1] \times[l_2, r_2] \times[l_3, r_3] \times[l_4, r_4] \times[l_5, r_5]$ 的長方體的一些 $r$ 會變成比原本小 $1$ 的數字
對 $j$ 從 $1$ 到 $5$ ，如果 $i$ 的第 $j$ 個位元是 $1$ ，那麼第 $i$ 個宇宙中所有長方體的第 $j$ 維的 $r$ 要減去 $1$
自然的第 $i$ 個宇宙的係數是 $(-1)^{popcount(i)}$
如此，在固定 $k$ 的時候只要對每個宇宙計算每個 $k$ 元子集的交的體積和再乘上對應的係數即可表徵有幾個 $k$ 元子集的交非空 (請自行證明)
固定當前所在的宇宙，一個 $k$ 元子集的交的體積即是要數有幾個單元正方體同時在這 $k$ 個長方體中，交換求和順序即知是要對每個單元正方體計算有幾個長方體覆蓋它
(若有 $x$ 個長方體覆蓋它，則其對答案的貢獻為 ${x} \choose {k}$ )
可以使用五維前綴和計算，每個宇宙會花上 $O(5\times 26^5 + 2^5n + n^2)$，於是就有了一個 $O(5\times 2^5 \times 26^5 + 2^{10}n + 2^5 n^2)$ 的作法
可以發現可將所有宇宙的係數視為一體再做組合數的計算，於是變成 $O(5\times 2^5 \times 26^5 + 2^{10}n + n^2)$
接下來注意到 $a_x$ 對於 $b_k$ 貢獻的係數是 ${x} \choose {k}$ 可以寫成一個卷積的形式，即 $(\sum_i (a_i i!)x^i)(\sum_i \frac{x^{-i}}{i!})=\sum_i (b_i i!) x^i$，於是優化多項式乘法即可
總複雜度為 $O(5\times 2^5 \times 26^5 + 2^{10}n + n \log n)$ ，足以通過
## Problem 303
### Subtask 1
可以觀察到，令$[a_1,a_2,..,a_k]$滿足$d_{a_1} = a_2,d_{a_2} = a_3,...,d_{a_{k - 1}} = a_k,d_{a_k} = a_1$，我們稱這叫做一個循環節。對於每個循環節，只要我們知道其中一個人往目標點移動時所走的路徑，我們就能夠逆向計算出整個循環節的移動路徑。
接下來，我們將整棵樹看成一個由左排列到右的陣列。對於每個循環節上的人，我們可以透過他們與目標點在陣列上的相對位置算出他們的初始移動方向是向左或右。可以發現到，在有其中一個人拿到鑰匙卡之前，所有人都不會改變移動方向。因此，只要找到與目標點上的人相向而行並距離最短的人，我們便可以判斷他的移動路徑是從起點直接走到目標點。這件事只需要儲存每個人在陣列上的位置，並稍微處理一些條件判斷便能完成，時間複雜度為$O(N)$。
### Subtask 2
這個子題其實與滿分解非常相似，它主要是用來簡化題目以幫助思考。通常想到這個子題後應該能很快想到滿分解，兩者的差別在於你能肯定某個性質並好好證明，而後用於優化自己的程式碼。這邊提供一個透過純粹觀察完成此子題的思路。
首先，令$x,y,z$滿足$d_x = y, d_y = z$，則必定可以找到一個$w$，滿足$x$到$y$、$x$到$z$、$y$到$z$的路徑都經過$w$。先只考慮$w$唯一的case，計算$x$到$w$、$y$到$w$、$z$到$w$的距離為$di_x,di_y,di_z$。
如果$di_x$是最小值，那$x$就可以最先走到$w$，此時可以發現，$y$正在往$w$移動，那$x$只要和$y$相向而行，接著再往$y$移動就好。我們於是直接找到了一個人的移動路徑，稱作直接路徑。
如果$di_x$不是最小值且$di_y$是最小值，那$y$就可以最先走到$w$，此時可以發現，$x$正在往$w$移動，而$y$正要離開$w$。在這個狀況下，$y$的移動路徑會是$x$的移動路徑的一部份，因此我們可以直接不看$x$。
不過，如果$di_x$和$di_y$都不是最小值，那$x,y,z$似乎都還不能被拋棄。不過我們可以稍微想一下，在我們找到一個新的人$t$使$t$的移動路徑成為$z$的移動路徑的一部份前，我們可以暫時將$z$的路徑視為$x,y$的路徑的一部份，而暫時不看$x,y$。
那麼，我們便可以維護一個stack，這個stack裡面存有還有可能被找出直接路徑的節點，並依序檢查節點，直到順利找到一條直接路徑。
唯一的問題，就是可能會沒辦法找到直接路徑，這時我們努力觀察，你會發現，唯一可能找不到直接路徑的狀況便是每一對$x,y,z$都滿足$di_x$和$di_y$都不是最小值。那我們直接選一個適當的起點(非葉節點便可)開始檢查便可以避免這個問題。
### Subtask 3
對於任意一個原本在點$u$上的人$p_u$，其在樹上的移動路徑有兩種。一種是從$u$直接走到點$d_u$，並恰好在路徑上遇到原本在點$d_u$上的人；另一種是先從$u$走到$v$，並在$v$遇到$p_{d_u}$，再從$v$走回$d_u$。
現在令一個序列$[v_1,v_2,...,v_k]$滿足$d_{v_1}=v_2,d_{v_2}=v_3,...,d_{v_{k-1}}=v_k,d_{v_k}=v_1$。
則在序列$[v_1,v_2,...,v_k]$之中，至少存在一個$v_i$會是第一種路徑。
證明如下：
令$w_i$代表$p_{v_i}$再走第二種路徑的情況下，離開$v_i$與$v_{(i\%k+1)}$路徑的點。
假設所有人都會走第二種路徑，則我們可以定義每個$p_{v_i}$必定處於以下三種狀態的其中一種：
- 狀態1、尚未經過$w_i$、尚未遇到$p_{v_{(i\%k+1)}}$；
- 狀態2、已經經過$w_i$、尚未遇到$p_{v_{(i\%k+1)}}$；
- 狀態3、已經經過$w_i$、已經遇到$p_{v_{(i\%k+1)}}$。
不難發現，所有$p_{v_i}$都必定經歷狀態1$\rightarrow$狀態2$\rightarrow$狀態3，並且如果$p_{v_i}$從狀態2變成了狀態3，則$p_{v_{(i\%k+1)}}$必須先變成狀態3，然而，在這樣的限制下，沒有$p_{v_i}$有辦法變成狀態3，因此不能所有人都走第二種路徑。
那麼，假捨我們知道$p_{v_i}$走的是第一種路徑，我們便能很簡單得到$p_{v_{(i+k-1)\%k}}$的路徑，進而得到$p_{v_{(i+k-2)\%k}}$，最終得到整個序列的路徑。
那麼，剩下的唯一問題便是對於一個序列$[v_1,v_2,...,v_k]$，找到其中一個走第一種路徑的$p_{v_i}$。
對於$v_i$，令$j=(i\%k+2)$並找出一個點$r_i$，使得$r_i$到$v_i,v_{(i\%k+1)},v_j$的距離和最小。
則以這三點到$r_i$的距離可分為三種狀況：
- 1.$v_i$到$r_i$的距離非嚴格最小，則$v_i$必定走第一種路徑
- 2.$v_{i+1}$到$r_i$的距離非嚴格小於$v_j$到$r_i$的距離，嚴格小於$v_i$到$r_i$的距離，則$v_i$必定走第二種路徑
- 3.$v_{j}$到$r_i$的距離嚴格最小，則我們可以將$j$視為$j\%k+1$，再計算一次同樣的問題
上面的第三種狀況處理的非常不嚴謹，可能存在一種狀況是，$v_i$能夠走第一種路徑，然而當我們遇到第三種狀況，將$j$當成其他的$j\%k+c$處理後，卻被判斷成了第二種狀況。但是我們能夠保證，即使這樣計算會忽略某些能走第一種路徑的$v_i$，我們仍至少能正確找出一個走第一種路徑的$v_i$。簡單的證明如下：假設存在這樣被我們誤判$v_i$，則代表當我們計算到某個$j$時，$p_{v_{(i\%k+1)}}$有能力先抵達$r_i$，進而先離開$v_i$到$v_{(i\%k+1)}$的路徑或是先遇到$p_{v_{(i\%k+2)}}$。在這個前提下，如果$p_{v_i}$還能再走第一種路徑並在$v_i$到$v_{(i\%k+1)}$路徑上遇到$p_{v_{(i\%k+1)}}$，則此時$p_{v_{(i\%k+1)}}$必定已經遇到$p_{v_{(i\%k+2)}}$。
那麼，如果$p_{v_{(i\%k+1)}}$走的是第二種路徑，由前面的結論我們知道在此之前必定有一個走第一種路徑的$p_{v_l}$已經遇到$p_{v_{(l\%k+1)}}$了。由此可知，對於所有會被誤判的走第一種路徑的$v_i$，必定存在一個走第一種路徑的$v_l$，滿足$p_{v_l}$遇到$p_{v_{(l\%k+1)}}$早於$p_{v_i}$遇到$p_{v_{(i\%k+1)}}$，因此，必定存在一個走第一種路徑的$p_{v_t}$最早遇到$p_{v_{(t\%k+1)}}$，使的他不會被誤判。
有了以上結論，最後我們只需要判斷目前的$v_i$屬於哪種狀況。
狀態1的話，就直接完成計算。
狀態3的話，就把$v_t$存進一個stack，期待未來的$j$來做計算
狀態2的話，就可以把$v_i$丟掉，並拿目前的$j$去計算stack裡面的$v_l$的答案，而不難發現，只要stack裡面最上面的$v_l$被計算出狀態3的結果，剩下的$v_t$也必定是狀態3。有了這個性質，我們便能保證計算次數是$O(N)$
最後，計算的細節會牽涉到$LCA$的計算以及一些條件判斷，整體的時間複雜度將會是$O(N\log N)$
:::spoiler Sample Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
int n, lca[400010][20], di[400010], l[400010], r[400010], id=1, mid[200010], des[200010], pr[200010];
bool vis[200010];
vector<int> g[400010];
void dfs(int p, int f, int d){
//bug(p,f,d);
lca[p][0] = f;
di[p] = d;
l[p] = id++;
for(int i = 0; i < 19; i++) if(lca[p][i] != -1)lca[p][i + 1] = lca[lca[p][i]][i];
for(int i: g[p]) if(i != f) dfs(i, p, d + 1);
r[p] = id++;
}
int dis1(int x, int y, int lc){return di[x] + di[y] - 2 * di[lc];}
int dis2(int x, int lc){return di[x] - di[lc];}
int dis3(int x, int y){return abs(di[x] - di[y]);}
bool isch(int x, int y){return l[x] < l[y] && l[y] < r[x];}//y is child of x
int fdpt(int x, int d){
for(int j = 19; j >= 0; j--)if(d & (1ll << j)) x = lca[x][j];
return x;
}
int LCA(int x, int y){
if(di[x] > di[y]) swap(x, y);
int le = di[y] - di[x];
for(int j = 19; j >= 0; j--) if(le & (1ll << j)) y = lca[y][j];
if(x == y) return x;
for(int j = 19; j >= 0; j--) if(lca[x][j] != -1 && lca[x][j] != lca[y][j]) x = lca[x][j], y = lca[y][j];
return lca[x][0];
}
int evl(int s, int e, int x){//0 pop 1 find 2 continue
int lc1 = LCA(x, e),lc2 = LCA(s, x);
if(isch(s, e)){
if(di[lc1] <= di[s]) return 1;
}
else if(di[lc2] >= di[s]) return 1;
if(isch(e, s)){
if(di[lc2] <= di[e]) return 0;
}
else if(di[lc1] >= di[e]) return 0;
if(isch(s, e)){
int ds = dis2(lc1, s), de = dis2(e, lc1), dx = dis2(x, lc1);
if(min({ds, de, dx}) == ds)return 1;
else if(min({ds, de, dx}) == de)return 0;
else return 2;
}
else if(isch(e, s)){
int ds = dis2(s, lc2), de = dis2(lc2, e), dx = dis2(x, lc2);
if(min({ds, de, dx}) == ds) return 1;
else if(min({ds, de, dx}) == de) return 0;
else return 2;
}
else{
int ds, de, dx, lc3 = LCA(s, e);
if(lc1 == lc2){
ds = dis2(s, lc3), de = dis2(e, lc3), dx = dis1(lc3, x, lc1);
}
else if(lc1 == lc3){
ds = dis2(s, lc2), de = dis1(lc2, e, lc3), dx = dis2(x, lc2);
}
else{
ds = dis1(s, lc1, lc3), de = dis2(e, lc1), dx = dis2(x, lc1);
}
if(min({ds, de, dx}) == ds) return 1;
else if(min({ds, de, dx}) == de) return 0;
else return 2;
}
}
int nxt(int x){return (x == n - 1? 0: x + 1);}
int pre(int x){return (x == 0? n - 1: x - 1);}
vector<int> sta;
void solve(int s){
int p = -1;
vector<int> tv;
tv.push_back(s);
vis[s] = 1;
int tp = des[s];
while(tp != s){
vis[tp] = 1;
tv.push_back(tp);
tp = des[tp];
}
if(sz(tv) == 1){
mid[tv[0]] = tv[0];
return;
}
if(sz(tv) == 2){
mid[tv[0]] = tv[1];
mid[tv[1]] = tv[0];
return;
}
for(int ii = 1; ii <= sz(tv) || sz(sta); ii++){
int i = ii % (sz(tv));
while(sz(sta)){
int re = evl(sta.back(), des[sta.back()], tv[i]);
if(re == 1){p = sta.back(); break;}
if(re == 2) break;
sta.pop_back();
}
if(p != -1)break;
if(ii <= sz(tv)) sta.push_back(pr[tv[i]]);
}
sta.clear();
mid[p] = des[p];
int rp = p;
p = pr[p];
for(; p != rp; p = pr[p]){
int u = des[p];
int tx = dis1(u, mid[u], LCA(u, mid[u])), ty = dis1(p, mid[u], LCA(p, mid[u]));
if(tx >= ty){
mid[p] = u;
continue;
}
if(tx + dis1(mid[u], des[u], LCA(mid[u], des[u])) >= dis1(p, des[u], LCA(p, des[u]))){
int tar = ty - tx;
tar /= 2;
tar += tx;
int lc = LCA(p, mid[u]);
if(dis2(p, lc) >= tar) mid[p] = fdpt(p, tar);
else mid[p] = fdpt(mid[u], dis2(mid[u], lc) + dis2(p, lc) - tar);
}
else mid[p] = des[u];
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> des[i], des[i]--, pr[des[i]] = i;
for(int i = 0; i < n - 1; i++){
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(n + i);
g[y].push_back(n + i);
g[n + i].push_back(x);
g[n + i].push_back(y);
}
dfs(0,-1,1);
memset(vis, 0, sizeof(vis));
for(int i = 0; i < n; i++)if(!vis[i]) solve(i);
int ans = 0;
for(int i = 0; i < n; i++){
ans = max(ans, dis1(i, mid[i], LCA(i, mid[i])) + dis1(mid[i], des[i], LCA(mid[i], des[i])));
}
cout << ans / 2 << '\n';
return 0;
}
```
:::
## Problem 304
講義 p295 例題
## Problem 305
首先，可以發現合法括號子字串可以由許多個 disjoint 的 `()` 子序列組出來，舉例來說 `(())` 可以將 1、4 拆成一組，2、3 拆成一組。
### subtask 1
有了上面的觀察可以得出一個簡單的方法求出單一括號字串的最長合法括號子序列：掃過一遍字串，沿途紀錄當前還沒被配對的左括號數量，當掃到右括號且還有沒被配到的左括號就直接把他們配起來。因此 $O(N^2)$ 的作法是先枚舉子字串的左界，之後枚舉右界的時候就可以用相同的方法一邊維護左括號數量，一邊計算出答案了。
:::spoiler 參考 code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
ios::sync_with_stdio(false), cin.tie(0);
int n;
string s;
cin >> n >> s;
long long ans = 0;
for (int i = 0; i < n; ++i) {
int cnt = 0, cur_len = 0;
for (int j = i; j < n; ++j) {
if (s[j] == '(') {
cnt++;
} else {
if (cnt) {
cnt--, cur_len += 2;
}
}
ans += cur_len;
}
}
cout << ans << '\n';
}
```
:::
### 滿分解
#### Claim
考慮每次將右括號跟離他最近且還沒匹配的左括號配對，則任意一個子字串的答案會是完全包含在這個子字串內的配對數量 * 2
#### 證明
首先，假設某個子字串內的配對數量為 $x$，那很顯然答案會有下界 $2x$，因此我們想要證明不存在更大的子序列長度。
我們考慮反證法，假設該子字串的最長合法括號子序列超過 $2x$。因為這是最長合法括號子序列，若將此子序列從字串中移除，會有某個前綴都是 `)`，其他都是 `(`。
接著我們使用「不在最長合法括號子序列內最左邊的 `(`」將字串分成兩半。可以發現若我們考慮上面描述的匹配方法，前半的 `(` 都一定可以被某個 `)` 配對到，後半的 `)` 都可以被某個 `(` 配對到，所以用上方的匹配方法配出來的數量會超過 $x$，這與假設矛盾，所以就證完 Claim 的正確性。
#### 作法
有了上面的 claim 作法就變得相當簡單，只需要計算出每對括號出現在幾個子字串裡面就好了，因此可以推出一個簡單的 $O(N)$ 解
另外這題也可以用比較不通靈的分治法在 $O(N \log N)$ 的時間內解決，詳細可以聽完 Day4 的分治課再自行思考 > <
:::spoiler 參考 code - stack
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
ios::sync_with_stdio(false), cin.tie(0);
int n;
string s;
cin >> n >> s;
long long ans = 0;
vector <int> stk;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
stk.push_back(i);
} else {
if (!stk.empty()) {
int x = stk.back(); stk.pop_back();
ans += 1ll * (x + 1) * (n - i) * 2;
}
}
}
cout << ans << '\n';
}
```
:::
:::spoiler 參考 code - 分治
```cpp=
#include <bits/stdc++.h>
using namespace std;
long long solve(int l, int r, string &s) {
if (r - l == 1) {
return 0;
}
int m = l + r >> 1;
long long ans = solve(l, m, s) + solve(m, r, s);
vector <int> cl(r - l + 1), cr(r - l + 1);
for (int i = m, cur = 0, cntl = 0, cntr = 0; i < r; ++i) {
if (s[i] == '(') {
cntl++;
} else {
if (cntl) {
cntl--, cur += 2;
} else {
cntr++;
}
}
ans += 1ll * cur * (m - l);
cr[cntr]++;
}
for (int i = m - 1, cur = 0, cntl = 0, cntr = 0; i >= l; --i) {
if (s[i] == ')') {
cntr++;
} else {
if (cntr) {
cntr--, cur += 2;
} else {
cntl++;
}
}
ans += 1ll * cur * (r - m);
cl[cntl]++;
}
for (int i = r - l, cnt0 = 0, cnt1 = 0; i; --i) {
cnt0 += cl[i];
cnt1 += cr[i];
ans += 1ll * cnt0 * cnt1 * 2;
}
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
string s;
cin >> n >> s;
cout << solve(0, n, s) << '\n';
}
```
:::
## Problem 306
去看題敘。
::: spoiler Sample Code
```cpp=
#include <bits/stdc++.h>
const int MOD = 998244353;
const int G = 3;
inline int mad(int u, int v) {
u += v - MOD;
u += MOD & (u >> 31);
return u;
}
inline int mul(int u, int v) {
return (int) ((int64_t) u * v % MOD);
}
inline int mow(int x, int e) {
int r = 1;
while (e) {
if (e & 1) r = mul(r, x);
x = mul(x, x);
e >>= 1;
}
return r;
}
void ntt(std::vector<int>& a) {
int n = (int) a.size(), L = 31 - __builtin_clz(n);
static std::vector<int> rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, ++s) {
rt.resize(n);
int z[] = {1, mow(G, MOD >> s)};
for (int i = k; i < 2 * k; ++i)
rt[i] = mul(rt[i / 2], z[i & 1]);
}
std::vector<int> rev(n);
for (int i = 0; i < n; ++i)
rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
for (int i = 0; i < n; ++i)
if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2) {
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; ++j) {
int z = mul(rt[j + k], a[i + j + k]), &ai = a[i + j];
a[i + j + k] = mad(ai, MOD - z);
ai += (ai + z >= MOD ? z - MOD : z);
}
}
}
}
std::vector<int> conv(const std::vector<int> &a, const std::vector<int> &b) {
if (a.empty() or b.empty()) return {};
int s = (int) (a.size() + b.size() - 1), B = 32 - __builtin_clz(s), n = 1 << B;
int inv = mow(n, MOD - 2);
std::vector<int> L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
for (int i = 0; i < n; ++i)
out[-i & (n-1)] = mul(mul(L[i], R[i]), inv);
ntt(out);
return {std::begin(out), std::begin(out) + s};
}
std::vector<int> inv(const std::vector<int> &a) {
if (a.size() < 1) return {};
std::vector<int> b = {mow(a[0], MOD - 2)};
for (int i = 1; i < (int) a.size(); i *= 2) {
auto c = conv({std::begin(a), std::begin(a) + std::min<int>(a.size(), i * 2)}, b);
c.erase(std::begin(c), std::begin(c) + i);
c = conv(b, c);
for (int& i: c) i = (i == 0 ? 0 : MOD - i);
c.resize(i);
b.insert(std::end(b), std::begin(c), std::end(c));
}
b.resize(a.size());
return b;
}
std::vector<int> divide(std::vector<int> a, std::vector<int> b) {
int n = (int) a.size(), m = (int) b.size();
if (n < m) return {};
std::reverse(std::begin(a), std::end(a));
std::reverse(std::begin(b), std::end(b));
b.resize(n - m + 1);
b = inv(b);
auto d = conv(a, b);
d.resize(n - m + 1);
std::reverse(std::begin(d), std::end(d));
return d;
}
std::vector<int> remain(std::vector<int> a, const std::vector<int>& b, const std::vector<int>& q) {
auto c = conv(b, q);
if (c.empty()) return a;
for (int i = 0; i < (int) a.size(); ++i)
a[i] = mad(a[i], MOD - c[i]);
while (!a.empty() and a.back() == 0)
a.pop_back();
return a;
}
std::vector<int> modular(const std::vector<int>& a, const std::vector<int>& mod) {
auto b = divide(a, mod);
return remain(a, mod, b);
}
int fast_linear_recurrence(const std::vector<int>& a, const std::vector<int>& c, int64_t K) {
int N = (int) a.size();
std::vector<int> x(N+1), e(N+1), mod(N + 1);
x[0] = e[1] = 1;
for (int i = 0; i < N; ++i)
mod[i] = (c[i] == 0 ? 0 : MOD - c[i]);
mod[N] = 1;
for (--K; K > 0; K /= 2) {
if (K & 1) x = modular(conv(x, e), mod);
e = modular(conv(e, e), mod);
}
x.resize(N, 0);
int ans = 0;
for (int i = 0; i < N; ++i)
ans = mad(ans, mul(a[i], x[i]));
return ans;
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin.exceptions(std::cin.failbit);
int N;
int64_t K;
std::cin >> N >> K;
K++;
std::vector<int> a(N), c(N);
for (int& i: a) std::cin >> i;
for (int& i: c) std::cin >> i;
std::cout << fast_linear_recurrence(a, c, K) << '\n';
return 0;
}
```
:::
## Problem 307
（待補）
## Problem 308
相當於要將樹上的一些點配對，使得距離和最大
對於任何一個點，如果把它當作根的話，距離和就是所有點到根的距離和扣掉
兩倍的根到點對的LCA的距離和，所以答案的上界是所有點到某個點的距離和
取這個點為樹上數字存在的點的帶權重心的話可以達到這個上界
因為樹高只有對數級別，每次從根往下找重心即可
## Problem 309
小心讀題敘，小心不要做錯事就好了
:::spoiler Sample Code
```cpp
#include <bits/stdc++.h>
using namespace std;
map<int, string> fr;
void init(){
fr[1] = "un";
fr[2] = "deux";
fr[3] = "trois";
fr[4] = "quatre";
fr[5] = "cinq";
fr[6] = "six";
fr[7] = "sept";
fr[8] = "huit";
fr[9] = "neuf";
fr[10] = "dix";
fr[11] = "onze";
fr[12] = "douze";
fr[13] = "treize";
fr[14] = "quatorze";
fr[15] = "quinze";
fr[16] = "seize";
fr[20] = "vingt";
fr[30] = "trente";
fr[40] = "quarante";
fr[50] = "cinquante";
fr[60] = "soixante";
}
string translate(int x){
if (fr.find(x) != fr.end())
return fr[x];
else if (x <= 69)
return translate(x / 10 * 10) + (x % 10 == 1 ? "-et-" : "-") + translate(x % 10);
else if (x <= 79)
return translate(60) + (x % 10 == 1 ? "-et-" : "-") + translate(x - 60);
else if (x == 80)
return "quatre-vingts";
else
return "quatre-vingt-" + translate(x - 80);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
init();
int x; cin >> x;
cout << translate(x) << '\n';
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet