IOIC 2023 Day 3 Editorial
Problem 301
SOS
為了解釋方便,我們把 符號改成 ,並且會用二進位數字表示集合。
令 ,也就是 的二進位表示中的位數。整題的
Subtask 1 ()
暴力枚舉, 或 都可以過。
Subtask 2 滿分解
令
則,
令 代表和 的前 個位元相同的所有子集 的 的和。
同理, 代表和 的前 個位元相同的所有子集 的 的和。
那麼可以枚舉 由小到大,先計算所有 之後得到 ,再計算所有 。
轉移是:
複雜度
Sample Code
Problem 302
首先可以將問題轉為對於每個 ,計算範圍有交的 元子集有幾個
對於一堆五維長方體,它們的交集具有體積相當於它們在接下來定義的 個平行宇宙中的交的體積乘上該宇宙的係數之和為 (否則為 )
具體來說,對 從 到 ,第 個宇宙中,原本是 的長方體的一些 會變成比原本小 的數字
對 從 到 ,如果 的第 個位元是 ,那麼第 個宇宙中所有長方體的第 維的 要減去
自然的第 個宇宙的係數是
如此,在固定 的時候只要對每個宇宙計算每個 元子集的交的體積和再乘上對應的係數即可表徵有幾個 元子集的交非空 (請自行證明)
固定當前所在的宇宙,一個 元子集的交的體積即是要數有幾個單元正方體同時在這 個長方體中,交換求和順序即知是要對每個單元正方體計算有幾個長方體覆蓋它
(若有 個長方體覆蓋它,則其對答案的貢獻為 )
可以使用五維前綴和計算,每個宇宙會花上 ,於是就有了一個 的作法
可以發現可將所有宇宙的係數視為一體再做組合數的計算,於是變成
接下來注意到 對於 貢獻的係數是 可以寫成一個卷積的形式,即 ,於是優化多項式乘法即可
總複雜度為 ,足以通過
Problem 303
Subtask 1
可以觀察到,令滿足,我們稱這叫做一個循環節。對於每個循環節,只要我們知道其中一個人往目標點移動時所走的路徑,我們就能夠逆向計算出整個循環節的移動路徑。
接下來,我們將整棵樹看成一個由左排列到右的陣列。對於每個循環節上的人,我們可以透過他們與目標點在陣列上的相對位置算出他們的初始移動方向是向左或右。可以發現到,在有其中一個人拿到鑰匙卡之前,所有人都不會改變移動方向。因此,只要找到與目標點上的人相向而行並距離最短的人,我們便可以判斷他的移動路徑是從起點直接走到目標點。這件事只需要儲存每個人在陣列上的位置,並稍微處理一些條件判斷便能完成,時間複雜度為。
Subtask 2
這個子題其實與滿分解非常相似,它主要是用來簡化題目以幫助思考。通常想到這個子題後應該能很快想到滿分解,兩者的差別在於你能肯定某個性質並好好證明,而後用於優化自己的程式碼。這邊提供一個透過純粹觀察完成此子題的思路。
首先,令滿足,則必定可以找到一個,滿足到、到、到的路徑都經過。先只考慮唯一的case,計算到、到、到的距離為。
如果是最小值,那就可以最先走到,此時可以發現,正在往移動,那只要和相向而行,接著再往移動就好。我們於是直接找到了一個人的移動路徑,稱作直接路徑。
如果不是最小值且是最小值,那就可以最先走到,此時可以發現,正在往移動,而正要離開。在這個狀況下,的移動路徑會是的移動路徑的一部份,因此我們可以直接不看。
不過,如果和都不是最小值,那似乎都還不能被拋棄。不過我們可以稍微想一下,在我們找到一個新的人使的移動路徑成為的移動路徑的一部份前,我們可以暫時將的路徑視為的路徑的一部份,而暫時不看。
那麼,我們便可以維護一個stack,這個stack裡面存有還有可能被找出直接路徑的節點,並依序檢查節點,直到順利找到一條直接路徑。
唯一的問題,就是可能會沒辦法找到直接路徑,這時我們努力觀察,你會發現,唯一可能找不到直接路徑的狀況便是每一對都滿足和都不是最小值。那我們直接選一個適當的起點(非葉節點便可)開始檢查便可以避免這個問題。
Subtask 3
對於任意一個原本在點上的人,其在樹上的移動路徑有兩種。一種是從直接走到點,並恰好在路徑上遇到原本在點上的人;另一種是先從走到,並在遇到,再從走回。
現在令一個序列滿足。
則在序列之中,至少存在一個會是第一種路徑。
證明如下:
令代表再走第二種路徑的情況下,離開與路徑的點。
假設所有人都會走第二種路徑,則我們可以定義每個必定處於以下三種狀態的其中一種:
- 狀態1、尚未經過、尚未遇到;
- 狀態2、已經經過、尚未遇到;
- 狀態3、已經經過、已經遇到。
不難發現,所有都必定經歷狀態1狀態2狀態3,並且如果從狀態2變成了狀態3,則必須先變成狀態3,然而,在這樣的限制下,沒有有辦法變成狀態3,因此不能所有人都走第二種路徑。
那麼,假捨我們知道走的是第一種路徑,我們便能很簡單得到的路徑,進而得到,最終得到整個序列的路徑。
那麼,剩下的唯一問題便是對於一個序列,找到其中一個走第一種路徑的。
對於,令並找出一個點,使得到的距離和最小。
則以這三點到的距離可分為三種狀況:
- 1.到的距離非嚴格最小,則必定走第一種路徑
- 2.到的距離非嚴格小於到的距離,嚴格小於到的距離,則必定走第二種路徑
- 3.到的距離嚴格最小,則我們可以將視為,再計算一次同樣的問題
上面的第三種狀況處理的非常不嚴謹,可能存在一種狀況是,能夠走第一種路徑,然而當我們遇到第三種狀況,將當成其他的處理後,卻被判斷成了第二種狀況。但是我們能夠保證,即使這樣計算會忽略某些能走第一種路徑的,我們仍至少能正確找出一個走第一種路徑的。簡單的證明如下:假設存在這樣被我們誤判,則代表當我們計算到某個時,有能力先抵達,進而先離開到的路徑或是先遇到。在這個前提下,如果還能再走第一種路徑並在到路徑上遇到,則此時必定已經遇到。
那麼,如果走的是第二種路徑,由前面的結論我們知道在此之前必定有一個走第一種路徑的已經遇到了。由此可知,對於所有會被誤判的走第一種路徑的,必定存在一個走第一種路徑的,滿足遇到早於遇到,因此,必定存在一個走第一種路徑的最早遇到,使的他不會被誤判。
有了以上結論,最後我們只需要判斷目前的屬於哪種狀況。
狀態1的話,就直接完成計算。
狀態3的話,就把存進一個stack,期待未來的來做計算
狀態2的話,就可以把丟掉,並拿目前的去計算stack裡面的的答案,而不難發現,只要stack裡面最上面的被計算出狀態3的結果,剩下的也必定是狀態3。有了這個性質,我們便能保證計算次數是
最後,計算的細節會牽涉到的計算以及一些條件判斷,整體的時間複雜度將會是
Sample Code
#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){
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];}
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){
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
有了上面的觀察可以得出一個簡單的方法求出單一括號字串的最長合法括號子序列:掃過一遍字串,沿途紀錄當前還沒被配對的左括號數量,當掃到右括號且還有沒被配到的左括號就直接把他們配起來。因此 的作法是先枚舉子字串的左界,之後枚舉右界的時候就可以用相同的方法一邊維護左括號數量,一邊計算出答案了。
參考 code
滿分解
Claim
考慮每次將右括號跟離他最近且還沒匹配的左括號配對,則任意一個子字串的答案會是完全包含在這個子字串內的配對數量 * 2
證明
首先,假設某個子字串內的配對數量為 ,那很顯然答案會有下界 ,因此我們想要證明不存在更大的子序列長度。
我們考慮反證法,假設該子字串的最長合法括號子序列超過 。因為這是最長合法括號子序列,若將此子序列從字串中移除,會有某個前綴都是 )
,其他都是 (
。
接著我們使用「不在最長合法括號子序列內最左邊的 (
」將字串分成兩半。可以發現若我們考慮上面描述的匹配方法,前半的 (
都一定可以被某個 )
配對到,後半的 )
都可以被某個 (
配對到,所以用上方的匹配方法配出來的數量會超過 ,這與假設矛盾,所以就證完 Claim 的正確性。
作法
有了上面的 claim 作法就變得相當簡單,只需要計算出每對括號出現在幾個子字串裡面就好了,因此可以推出一個簡單的 解
另外這題也可以用比較不通靈的分治法在 的時間內解決,詳細可以聽完 Day4 的分治課再自行思考 > <
參考 code - stack
參考 code - 分治
Problem 306
去看題敘。
Sample Code
#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
小心讀題敘,小心不要做錯事就好了
Sample Code