---
title: IOICamp 2023 Day 2 Contest Editorial
tags: editorial, competitive-programming
---
# IOIC 2023 Day 2 Editorial
## Problem 201
### 估計：證明 $n > 30$ 時無解
假設有解：
令 $b_i = a_1 \, \& \, a_2 \, \& \, \cdots \, a_i$。
1. 根據定義，$b_1, b_2, \ldots, b_{31}$ 必須兩兩不同。
2. 因為 $b_{i + 1} = b_i \, \& \, a_{i + 1}$，$b_{i + 1}$ 是 $b_i$ 的 submask。
綜上兩點，$b_{i + 1}$ 是 $b_i$ 的 proper submask。這使得
```
__builtin_popcount(b[1]) > __builtin_popcount(b[2]) > ... > __builtin_popcount(b[31])
```
因為 $0 \leq b_1, b_2, \ldots, b_{31} < 2^{30}$，`__builtin_popcount`的值域是$[0, 30]$
$\Rightarrow \,$ `__builtin_popcount(b[i])`$= 31 - i$
$\Rightarrow \, b_1 = a_1 = 111111111111111111111111111111_2$
$\Rightarrow \, a_1 \, \& \, a_2 = a_2 \quad \rightarrow\leftarrow$
### 構造：證明 $n \leq 30$ 時總是有解
$a_i = 2^{30} - 1 - 2^{i}$ 是個合法構造。
## Problem 202
### Subtask 1
注意到這就是裸的李超線段樹，只不過值域很大，所以要記得先將所有會代入的 $x$ 值離散化。
### Subtask 2
題目叫做 Double 線段樹，所以可以考慮看看同時使用兩棵線段樹。
注意到李超線段樹可以支援 undo，因此可以考慮再套時間線段樹，實作細節就留給讀者思考。
:::spoiler Sample Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define maxn 200005
struct event{
int a, b;
int val(int x){
return a * x + b;
}
};
vector<pair<int, event> > undo[4 * maxn];
int np, rx[maxn], que[maxn], lin, tin;
vector<pair<int, int> > qu, tim;
vector<event> li;
struct Li_Seg_Tree{
vector<event> seg;
Li_Seg_Tree(): seg(4 * maxn) {}
void init(int n){
for(int i = 0; i < 4 * n; i++) seg[i].a = seg[i].b = 0;
}
void insert(int p, int l,int r, event e){
int mi = (l + r) / 2;
if(e.val(rx[mi]) > seg[p].val(rx[mi])){
undo[np].push_back({p, seg[p]});
swap(e,seg[p]);
}
if(l == r) return;
if(e.a < seg[p].a) insert(p * 2, l, mi, e);
else insert(p * 2 + 1, mi + 1, r, e);
}
int query(int p, int l, int r, int x){
int re = seg[p].val(rx[x]);
if(l == r) return re;
int mi = (l + r) / 2;
if(x > mi) return max(re, query(p * 2 + 1, mi + 1, r, x));
else return max(re, query(p * 2, l, mi, x));
}
}litree;
struct Time_Seg_Tree{
vector<event> seg[4 * maxn];
void insert(int p, int l, int r, event e, int ql, int qr){
if(l > qr || r < ql) return;
if(l >= ql && r <= qr){
seg[p].push_back(e);
return;
}
int mi = (l + r) / 2;
insert(p * 2, l, mi, e, ql, qr);
insert(p * 2 + 1, mi + 1, r, e, ql, qr);
return;
}
void travel(int p, int l, int r){
if(l == r){
if(que[l] >= 0){
np = p;
for(auto e: seg[p]) litree.insert(1, 0, lin - 1, e);
int ans = litree.query(1, 0, lin - 1, que[l]);
if(ans) cout << ans << '\n';
else cout << "double is good at problem setting\n";
reverse(undo[p].begin(), undo[p].end());
for(auto pi: undo[p]) litree.seg[pi.first] = pi.second;
}
return;
}
int mi = (l + r) / 2;
np = p;
for(auto e: seg[p]) litree.insert(1, 0, lin - 1, e);
travel(p * 2, l, mi);
travel(p * 2 + 1, mi + 1, r);
reverse(undo[p].begin(), undo[p].end());
for(auto pi: undo[p]) litree.seg[pi.first] = pi.second;
return;
}
}titree;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int q;
cin >> q;
int cnt = 0;
while(q--){
int ty;
cin >> ty;
if(ty == 0){
int x;
cin >> x;
qu.push_back({cnt++, x});
}
else if(ty == 1){
int a, b;
cin >> a >> b;
tim.push_back({cnt++, 1e9});
event te;
te.a = a, te.b = b;
li.push_back(te);
}
else{
int id;
cin >> id;
tim[id].second = cnt++;
}
}
for(auto &pi: tim) if(pi.second > 1e8) pi.second = cnt;
vector<int> v;
for(auto pi: qu) v.push_back(pi.second);
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
lin = ((int) v.size());
tin = cnt + 1;
for(int i = 0; i < tin; i++) que[i] = -1;
for(int i = 0; i < lin; i++) rx[i] = v[i];
for(auto pi: qu) que[pi.first] = lower_bound(v.begin(), v.end(), pi.second) - v.begin();
litree.init(lin);
for(int i = 0; i < ((int) tim.size()); i++) titree.insert(1, 0, tin - 1, li[i], tim[i].first, tim[i].second);
titree.travel(1, 0, tin - 1);
return 0;
}
```
:::
### Remark
Double is good at problem setting. :)
## Problem 203
### 題解
* 以$s_i$代表DE語長度是$i$的前綴
* 以$a_{ij}$代表長度是$i$的字串中，不包含DE語且其最長的後綴使得其為DE語前綴的長度為$j$的字串個數
* 以$f(i, j, c)$代表$s_i+c$的長度是$j$的後綴是否是最長後綴使得其為DE語前綴，其中若滿足則為$1$否則為$0$
* \begin{align*}&\begin{pmatrix}
a_{i+1, 0}\\
a_{i+1, 1}\\
\vdots\\
a_{i+1, m-1}
\end{pmatrix}\\&=\sum\limits_{c='0'}^{'9'}\begin{pmatrix}
f(0, 0, c)&f(0, 1, c)&\cdots&f(0, m-1, c)\\
f(1, 0, c)&f(1, 1, c)&\cdots&f(1, m-1, c)\\
\vdots&\vdots&\ddots&\vdots\\
f(m-1, 0, c)&f(m-1, 1, c)&\cdots&f(m-1, m-1, c)
\end{pmatrix}\\
&\begin{pmatrix}
a_{i, 0}\\
a_{i, 1}\\
\vdots\\
a_{i, m-1}
\end{pmatrix}\end{align*}
* 我們知道
$$\begin{pmatrix}
a_{0, 0}\\
a_{0, 1}\\
\vdots\\
a_{0, m-1}
\end{pmatrix}=\begin{pmatrix}
1\\0\\\vdots\\0
\end{pmatrix}$$
* 所以只需要計算$A=\sum_{c='0'}^{'9'}$的上一頁的大矩陣，快速冪求$A^n$，就可以求得$\begin{pmatrix}
a_{n, 0}\\
a_{n, 1}\\
\vdots\\
a_{n, m-1}
\end{pmatrix}$，而$a_{n, 0}+a_{n, 1}+\cdots+a_{n, m-1}$即為長度是$n$且不包含DE語的字串的個數，因此$1-\frac{a_{n, 0}+\cdots+a_{n, m-1}}{10^n}$即為答案。
### 關於 $q=40000$
* 原先的計算使用快速冪每個詢問會做$64$次矩陣乘法
* 先預處理所有的$A$的$a2^{8b}$冪次的矩陣的值，其中$a\in\{0, 1, \dots, 2^8-1\},\ b\in\{0, 1, \dots, 7\}$，每次計算快速冪時改用$2^8$進位去計算，即可省掉$8$的常數
## Problem 204
* 選一個點 $v$ 往下走 $k$ 步後能到的所有點，一起加值或求和
先算好每個點的深度，並且把每個深度的點分別收集起來，會變成
* 在深度為 $depth(v)+k$ 那堆點中，把所有屬於 $v$ 子樹的點一起加值或求和
判斷是否在子樹可以用 DFS 序（開始與離開時間），所以先把每個深度的點分別照 DFS 序 sort 好，每次二分搜出那個區間，就變成一堆區間操作了，可以用線段樹等資料結構解決
複雜度 $O(N+Q\log N)$
## Problem 205
### Subtask 1
暴力。
### Subtask 2
講義上有寫答案是 $(n + 1) ^ {n - 1}$。
### Subtask 3
仔細想一想，會發現對一個（全部位置已知的） $p$，有解的條件是對於所有 $k$，$p$ 裡面 $\geq k$ 的元素的個數要 $\leq n - k + 1$。
因此可以想到以下dp： $dp[i][j]$ 目前已經有 $j$ 個位置用 $\geq i$ 的數填好了。這裡 $j$ 個位置包含那些本來就指定 $\geq i$ 的位置，以及一些用 $\geq i$的數填入未指定的位置。
轉移如下（跟標程代號一樣）：
定義 $f[i]$ 表示給定包含了幾個 $i$，$g[i]$ 表示給定包含了幾個 $\geq i$，$m$ 表示輸入中位指定的個數。
考慮哪些 state 可以轉移到 $dp[i][j]$。
假設放了 $k$ 個 $i$，那麼轉移來自 $dp[i + 1][j - k]$。在 $dp[i + 1][j - k]$ 還有 $m -(j - k - g[i + 1])$ 個未指定的位置可用，且 $k$ 個 $i$ 中 $k - f[i]$ 個是填在未指定的位置，因此轉移要乘以一個 $\binom {m - (j - k - g[i + 1])}{k - f[i]}$的係數。
### Sample code
:::spoiler Sample Code
```cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int P = 998244353;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
int m = count(a.begin(), a.end(), -1);
vector<int> f(n);
for (int i = 0; i < n; i++) {
if (a[i] != -1) {
f[a[i]]++;
}
}
vector<int> g(n + 1);
for (int i = n - 1; i >= 0; i--) {
g[i] = g[i + 1] + f[i];
// if (g[i] > n - i) {
// cout << "0\n";
// return;
// }
}
vector binom(n + 1, vector<int>(n + 1));
for (int i = 0; i <= n; i++) {
binom[i][0] = 1;
for (int j = 1; j <= i; j++) {
binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % P;
}
}
vector dp(n + 1, vector<int>(n + 1));
dp[n][0] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = g[i]; j <= n - i && j <= m + g[i]; j++) {
for (int k = f[i]; k + g[i + 1] <= j; k++) {
dp[i][j] = (dp[i][j] + 1LL * dp[i + 1][j - k] * binom[m - (j - k - g[i + 1])][k - f[i]] % P) % P;
}
}
}
cout << dp[0][n] << '\n';
};
solve();
return 0;
}
```
:::
## Problem 206
結論：$(p, q) = (2, N - 2)$ 總是一個解。
證明：先使用反證法。如果有一種答案不包含 $2$ 作為其中一個質數，那麼 $p, q$ 都是奇質數 $\Rightarrow p + q = N$ 是 $\geq 6$ 的偶數 $\rightarrow\leftarrow$
因為保證有解，所以 $(p, q) = (2, N - 2)$ 總是一組解。
## Problem 207
首先，有重複的 $a_i$ 時可以先連起來，因為對一個數字來說連到自己的倍數會最好
接下來考慮 Boruvka，每一輪先對每個 $a_i$ 跑過它的所有因數，在因數 $x$ 的地方紀錄下 $a_i$ 所屬的連通塊，代表如果另一個連通塊內也有 $x$ 的倍數則可以連一條至少是 $x$ 的邊到這一塊。每個因數只需要保留前兩個發現的連通塊，因為任一個連通塊至少和那兩個之一可以連邊
再對每個 $a_i$ 跑一遍它的所有因數，找到它最好的一條邊後，和他所屬的連通塊內其他點的邊比較。這時已經找到每個連通塊這一輪要加的邊了，一邊維護並查集確定不會形成環一邊把它們加上去。$\log N$ 輪後就找到最大生成樹
一開始要預處理每個數字有哪些因數，複雜度 $O(C\log C)$，每一輪花的時間是它們的因數個數和，$10^6$ 以內因數最多的 $10^5$ 個數字一共有 $4911307$ 個數字，進行 $O(\log N)$ 輪，實測會 AC
還有使用 Prim 或 Kruskal 思路的各種作法也可以 AC(砸一般 Kruskal 只能拿到部分分)
## Problem 208
### Subtask 1
題目需要支援單點修改，以及區間查詢總和。跟講義的基礎線段樹的例題好像喔！沒有錯，這個 subtask 就是個一般的線段樹。把講義的範例 code 拿出來抄一抄，把取 max 的部份改成加法就可以了！
### Subtask 2
現在題目是要支援區間修改、區間求和。看到區間修改，其實可以馬上聯想到可能會需要懶人標記。沒錯，這題就是個懶人標記的題目，而這種線段樹也是蠻常出現在題目中的！
這題懶標要怎麼設計呢？首先，操作是區間加值，所以 tag 應該就是要存「子樹以下所有數字要加上多少」。
接下來，要怎麼利用懶標快速知道如何更新答案（這題來說是子樹的總和）呢？其實就是把總和加上 tag * 子樹大小（也就是維護的區間長度）！
### 另解 1
可以用兩個 BIT 維護差分陣列解決喔！
https://oi-wiki.org/ds/fenwick/#%E5%8C%BA%E9%97%B4%E5%8A%A0%E5%8C%BA%E9%97%B4%E5%92%8C
### 另解 2
這題也可以用分塊做掉喔！
https://sprout.tw/algo2021/ppt_pdf/week14/root_method.pdf
可以從第 22 頁開始看喔～
### Sample Code
:::spoiler Sample Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kN = 200006;
ll a[kN];
struct Node {
Node *lc, *rc;
ll sum, tag;
Node(): lc(NULL), rc(NULL), sum(0), tag(0){}
void pull() {
sum = lc->sum + rc->sum;
}
};
Node* Build(int L, int R) {
Node* node = new Node();
if (L == R) {
node->sum = a[L];
return node;
}
int mid = (L + R) >> 1;
node->lc = Build(L, mid);
node->rc = Build(mid + 1, R);
node->pull();
return node;
}
void push(Node* node, int L, int R) {
if (L == R) node->tag = 0;
if (node->tag == 0) return;
int mid = (L + R) >> 1;
node->lc->tag += node->tag;
node->lc->sum += node->tag * (mid - L + 1);
node->rc->tag += node->tag;
node->rc->sum += node->tag * (R - mid);
node->tag = 0;
return;
}
void modify(Node* node, int L, int R, int l, int r, ll d) {
if (l > R || L > r) return;
else if (l <= L && R <= r) {
node->tag += d;
node->sum += (R - L + 1) * d;
return;
}
push(node, L, R);
int mid = (L + R) >> 1;
modify(node->lc, L, mid, l, r, d);
modify(node->rc, mid + 1, R, l, r, d);
node->pull();
return;
}
ll query(Node* node, int L, int R, int l, int r) {
if (l > R || L > r) return 0;
else if (l <= L && R <= r) return node->sum;
push(node, L, R);
int mid = (L + R) >> 1;
return query(node->lc, L, mid, l, r) + query(node->rc, mid + 1, R, l, r);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
Node* root = Build(1, n);
while (q--) {
int t; cin >> t;
if (t == 1) {
int l, r, d; cin >> l >> r >> d;
modify(root, 1, n, l, r, d);
} else {
int l, r; cin >> l >> r;
cout << query(root, 1, n, l, r) << '\n';
}
}
}
```
:::
Sign in with Wallet
Connect another wallet