owned this note
owned this note
Published
Linked with GitHub
# CSES ADVANCED TECHNIQUES
@the_ffting_pooh 說他沒穿衣服
# [Meet in the Middle](https://cses.fi/problemset/task/1628)
先輩知識:[Sum of Two Values](https://cses.fi/problemset/task/1640)
題目範圍的$n \le 40$，感覺$n$再小一點就可以枚舉了。
所以就讓它變小。
把n折半，可以每半先個別枚舉，兩個合併時就用Sum of Two Values的方法做，然後就可以求出來了。
複雜度 : $O({n\times 2^{n/2}})$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,s,ans;
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin>>n>>m;
vector<ll> a(n/2),b(n-n/2),sumsA,sumsB;
for(ll& i:a)cin>>i;
for(ll& i:b)cin>>i;
for(int i=0;i<(1<<a.size());i++){
s=0;
for(int j=0;j<a.size();j++)if(i&(1<<j))s+=a[j];
sumsA.emplace_back(s);
}
for(int i=0;i<(1<<b.size());i++){
s=0;
for(int j=0;j<b.size();j++)if(i&(1<<j))s+=b[j];
sumsB.emplace_back(s);
}
sort(sumsA.begin(),sumsA.end()),sort(sumsB.begin(),sumsB.end());
for(const ll& i:sumsA)ans+=upper_bound(sumsB.begin(),sumsB.end(),m-i)-lower_bound(sumsB.begin(),sumsB.end(),m-i);
cout<<ans;
}
```
:::
# [Hamming Distance](https://cses.fi/problemset/task/2136)
因為這題給的string只由0和1構成，長度還小於30，於是可以把他當成整數的二進位表示法，所以只需要做一次xor之後popcount，就能算出hamming distance了。
裸的枚舉是$O({n^2})$，位元運算可以套bitset。
複雜度 : $O({n^2})$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=2e4+5,maxK=35;
int ans=maxK,cnt,n,k,q[maxN];
string s;
inline void decomp(I id){
rep(j,0,k)if(s[j]=='1')q[id]+=1<<j;
}
int main(){
IOS
cin>>n>>k;
rep(i,0,n)cin>>s,decomp(i);
rep(i,0,n)rep(j,i+1,n){
ans=min(ans,__builtin_popcount(q[i]^q[j]));
}
cout<<ans;
}
```
:::
# [Corner Subgrid Check](https://cses.fi/problemset/task/3360)
對每個字母做。
枚舉兩排的作法似乎不夠快，也沒辦法優化。
試著從圖論去思考他，發現如果你把這個矩陣當成一張二分圖的鄰接矩陣，那你要找的就是有沒有$C_4$，可以在$O(\lvert V \rvert ^2)$做完。
所以時間複雜度總共是$O(n^2k)$。
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using i64 = long long;
using namespace std;
template <class T>
using vec = vector<T>;
template <class T>
istream& operator>>(istream& is, vec<T>& X) {
for (auto& x : X) {
is >> x;
}
return is;
}
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;
constexpr int kN = 3'000;
int vis[kN][kN];
bool check(int N, const vec<vec<int>>& g) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
vis[i][j] = -1;
}
}
for (int i = 0; i < N; i++) {
for (auto j : g[i]) {
for (auto k : g[i]) { // 是g[i]，不要寫成g[j] by剛剛才寫錯的人
if (j == k) {
continue;
}
if (vis[j][k] != -1) {
return true;
}
vis[j][k] = i;
}
}
}
return false;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, k; cin >> N >> k;
vec<vec<vec<int>>> gs(k, vec<vec<int>>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char c; cin >> c;
gs[c - 'A'][i].emplace_back(j);
}
}
for (int i = 0; i < k; i++) {
cout << (check(N, gs[i]) ? "YES\n" : "NO\n");
}
}
```
:::
# [Corner Subgrid Count/Beautiful Subgrids](https://cses.fi/problemset/task/2137)
喔他現在原來叫Corner Subgrid Count
暴力$O({n^3})$解 :
$O({n^2})$ 枚舉任意兩條，$O(n)$找每個位置&起來等於$1$的數量。
然後發現位元運算可以套bitset優化。
複雜度 : $O({n^3})$
按照上面那題，這可以被規約到數一張二分圖上的$C_4$數量所以你可以做得跟矩陣乘法一樣快。
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=3e3+5;
I n;
ll ans;
string s;
bitset<maxN> grid[maxN];
I main(){
IOS
cin>>n;
rep(i,1,n+1){
cin>>s;
rep(j,1,n+1)grid[i][j]=s[j-1]&1;
}
rep(i,1,n+1)rep(j,i+1,n+1){
ll cnt=(grid[i]&grid[j]).count();
ans+=(cnt-1)*cnt/2;
}
cout<<ans;
}
```
:::
# [Reachable Nodes](https://cses.fi/problemset/task/2138/)
這題其實挺詭譎的，看起來很像正常圖論題，但其實是鴨腸暴力題 :cold_sweat:
開一個鄰接bitset，dfs紀錄每個點可以到的點有誰，答案就會是$bitset[point].count()$;
複雜度 : $O({n(n+m)})$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=5e4+5;
I n,m,indeg[maxN];
vector<I> adj[maxN];
bitset<maxN> ans[maxN],vis;
void dfs(I now){
if(vis[now])return;
vis[now]=1,ans[now][now]=1;
for(I i:adj[now])dfs(i),ans[now]|=ans[i];
}
I main(){
IOS
cin>>n>>m;
for(I a,b;m--;)cin>>a>>b,adj[a].emplace_back(b),indeg[b]++;
rep(i,1,n+1)if(!indeg[i])dfs(i);
rep(i,1,n+1)cout<<ans[i].count()<<' ';
}
```
:::
# [Reachability Queries](https://cses.fi/problemset/task/2143/)
跟前一題不同的是
$1.$他不是$DAG$
$2.$多筆詢問
第$2$點很顯然用上一題的方法就可以解決了，但第$1$點就要想一下了。
如果出現環的話，代表整個環裡面每個人都會互相走到，那不就是$SCC$。
那解法就會是 : 把$SCC$縮起來再做一次上一題。
複雜度 : $O(n(n+m)+q)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=5e4+5;
I n,m,q,indeg[maxN],scc[maxN];
vector<I> adj[maxN],jda[maxN],g[maxN],order;
bitset<maxN> ans[maxN],vis,chk[maxN];
void dfs(I now){
if(vis[now])return;
vis[now]=1,ans[now][now]=1;
for(I i:g[now])dfs(i),ans[now]|=ans[i];
}
void dfs1(I now){
vis[now]=1;
for(I i:adj[now])if(!vis[i])dfs1(i);
order.emplace_back(now);
}
void dfs2(I now,I id){
scc[now]=id;
for(I i:jda[now])if(!scc[i])dfs2(i,id);
}
I main(){
IOS
cin>>n>>m>>q;
for(I a,b;m--;)cin>>a>>b,adj[a].emplace_back(b),jda[b].emplace_back(a);
rep(i,1,n+1)if(!vis[i])dfs1(i);
reverse(all(order));
for(I i:order)if(!scc[i])dfs2(i,i);
vis.reset();
rep(i,1,n+1)for(I j:adj[i])if(scc[i]!=scc[j])g[scc[i]].emplace_back(scc[j]);
rep(i,1,n+1)if(!indeg[scc[i]])dfs(scc[i]),indeg[scc[i]]++;
for(I a,b;q--;)cin>>a>>b,cout<<(ans[scc[a]][scc[b]]?"YES\n":"NO\n");
}
```
:::
# [Cut and Paste](https://cses.fi/problemset/task/2072)
裸treap題，全部都是treap操作
$cut$ 作法 : 把區間split出來
$paste$ 作法 : 把區間merge到尾端
複雜度 : $O(m \log n)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,cnt,root;
string s;
mt19937 rng(time(0)*71227122);
struct NODE{
I pri,lc,rc,sz;
char c;
NODE(){}
}fn[maxN*40];
inline void pull(I ind){
fn[ind].sz=1;
if(fn[ind].lc)fn[ind].sz+=fn[fn[ind].lc].sz;
if(fn[ind].rc)fn[ind].sz+=fn[fn[ind].rc].sz;
}
I merge(I a,I b){
if(!a||!b)return a?a:(b?b:0);
if(fn[a].pri<fn[b].pri)return fn[b].lc=merge(a,fn[b].lc),pull(b),b;
return fn[a].rc=merge(fn[a].rc,b),pull(a),a;
}
void split(I nd,I k,I& a,I& b){
if(!nd)return a=0,b=0,void();
if(fn[fn[nd].lc].sz<k)a=nd,split(fn[nd].rc,k-fn[fn[nd].lc].sz-1,fn[a].rc,b);
else b=nd,split(fn[nd].lc,k,a,fn[b].lc);
pull(nd);
}
inline void insert(I pos,char c){
I l=0,r=0,now=++cnt;
fn[now].pri=rng(),fn[now].c=c;
split(root,pos-1,l,r);
root=merge(merge(l,now),r);
}
inline void change(I l,I r){
I a=0,b=0,c=0,d=0;
split(root,l-1,a,b);
split(b,r-l+1,c,d);
root=merge(merge(a,d),c);
}
void dfs(I now){
if(fn[now].lc)dfs(fn[now].lc);
cout<<fn[now].c;
if(fn[now].rc)dfs(fn[now].rc);
}
I main(){
IOS
cin>>n>>m>>s;
rep(i,0,n)insert(i+1,s[i]);
for(I a,b;m--;){
cin>>a>>b;
change(a,b);
}
dfs(root);
}
```
:::
# [Substring Reversals](https://cses.fi/problemset/task/2073)
懶標treap題
推懶標 : 推下去的時候把子節點的懶標^=1，並$swap$左右子樹。
複雜度 : $O(m \log n)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,cnt,root;
string s;
mt19937 rng(time(0)*1ll*712271227);
struct NODE{
I pri,lc,rc,sz,tag;
char c;
NODE(){}
}fn[maxN*40];
inline void pull(I ind){
fn[ind].sz=1;
if(fn[ind].lc)fn[ind].sz+=fn[fn[ind].lc].sz;
if(fn[ind].rc)fn[ind].sz+=fn[fn[ind].rc].sz;
}
inline void push(I ind){
if(!fn[ind].tag)return;
swap(fn[ind].lc,fn[ind].rc);
if(fn[ind].lc)fn[fn[ind].lc].tag^=1;
if(fn[ind].rc)fn[fn[ind].rc].tag^=1;
fn[ind].tag=0;
}
I merge(I a,I b){
if(!a||!b)return a?a:(b?b:0);
push(a),push(b);
if(fn[a].pri<fn[b].pri)return fn[b].lc=merge(a,fn[b].lc),pull(b),b;
return fn[a].rc=merge(fn[a].rc,b),pull(a),a;
}
void split(I nd,I k,I& a,I& b){
if(!nd)return a=0,b=0,void();
push(nd);
if(fn[fn[nd].lc].sz<k)a=nd,split(fn[nd].rc,k-fn[fn[nd].lc].sz-1,fn[a].rc,b);
else b=nd,split(fn[nd].lc,k,a,fn[b].lc);
pull(nd);
}
inline void insert(I pos,char c){
I l=0,r=0,now=++cnt;
fn[now].pri=rng(),fn[now].c=c;
split(root,pos-1,l,r);
root=merge(merge(l,now),r);
}
inline void change(I l,I r){
I a=0,b=0,c=0,d=0;
split(root,l-1,a,b);
split(b,r-l+1,c,d);
fn[c].tag=1;
root=merge(merge(a,c),d);
}
void dfs(I now){
if(!now)return;
push(now);
dfs(fn[now].lc);
cout<<fn[now].c;
dfs(fn[now].rc);
}
I main(){
IOS
cin>>n>>m>>s;
rep(i,0,n)insert(i+1,s[i]);
for(I a,b;m--;){
cin>>a>>b;
change(a,b);
}
dfs(root);
}
```
:::
# [Reversals and Sums](https://cses.fi/problemset/task/2074)
懶標treap題，跟上一題比就是再加上區間詢問和，所以再多維護一個子樹和就好了。
複雜度 : $O((m+n) \log n)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,cnt,root;
mt19937 rng(time(0)*1ll*712271227);
struct NODE{
I pri,lc,rc,sz,tag;
ll val,sum;
NODE(){}
}fn[maxN*40];
inline void pull(I ind){
fn[ind].sz=1,fn[ind].sum=fn[ind].val;
if(fn[ind].lc)fn[ind].sz+=fn[fn[ind].lc].sz,fn[ind].sum+=fn[fn[ind].lc].sum;
if(fn[ind].rc)fn[ind].sz+=fn[fn[ind].rc].sz,fn[ind].sum+=fn[fn[ind].rc].sum;
}
inline void push(I ind){
if(!fn[ind].tag)return;
swap(fn[ind].lc,fn[ind].rc);
if(fn[ind].lc)fn[fn[ind].lc].tag^=1;
if(fn[ind].rc)fn[fn[ind].rc].tag^=1;
fn[ind].tag=0;
}
I merge(I a,I b){
if(!a||!b)return a?a:(b?b:0);
push(a),push(b);
if(fn[a].pri<fn[b].pri)return fn[b].lc=merge(a,fn[b].lc),pull(b),b;
return fn[a].rc=merge(fn[a].rc,b),pull(a),a;
}
void split(I nd,I k,I& a,I& b){
if(!nd)return a=0,b=0,void();
push(nd);
if(fn[fn[nd].lc].sz<k)a=nd,split(fn[nd].rc,k-fn[fn[nd].lc].sz-1,fn[a].rc,b);
else b=nd,split(fn[nd].lc,k,a,fn[b].lc);
pull(nd);
}
inline void insert(I pos,ll val){
I l=0,r=0,now=++cnt;
fn[now].pri=rng(),fn[now].val=val;
split(root,pos-1,l,r);
root=merge(merge(l,now),r);
}
inline void change(I l,I r){
I a=0,b=0,c=0,d=0;
split(root,l-1,a,b);
split(b,r-l+1,c,d);
fn[c].tag=1;
root=merge(merge(a,c),d);
}
inline void sums(I l,I r){
I a=0,b=0,c=0,d=0;
split(root,l-1,a,b);
split(b,r-l+1,c,d);
cout<<fn[c].sum<<'\n';
root=merge(merge(a,c),d);
}
I main(){
IOS
cin>>n>>m;
rep(i,0,n){
ll tmp;cin>>tmp,insert(i+1,tmp);
}
for(I t,a,b;m--;){
cin>>t>>a>>b;
if(t==1)change(a,b);
else sums(a,b);
}
}
```
:::
# [Necessary Roads](https://cses.fi/problemset/task/2076)
裸的找@the_ffting_pooh題
看$dfs\ tree$，$dfs$時按前序把經過的點上$dfs$序，記錄在$dfn[now]$，並在dfs下去時紀錄走的到的點裡面$dfs$序最低的，記錄在$low[now]$。
判答案的時候要從父節點判，如果$dfn[parent] \lt low[child]$，就代表這條邊是橋。
複雜度 : $O(n+m)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops,inline")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define I int
#define A auto
#define C char
#define ll long long
#define pii pair<I,I>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,cnt,low[maxN],dfn[maxN];
vector<I> adj[maxN];
vector<pii> res;
void dfs(I now,I last){
dfn[now]=low[now]=++cnt;
for(I& i:adj[now]){
if(i==last)continue;
if(!dfn[i]){
dfs(i,now),low[now]=min(low[now],low[i]);
if(low[i]>dfn[now])res.emplace_back(now,i);
}
else low[now]=min(low[now],dfn[i]);
}
}
int main(){
IOS
cin>>n>>m;
for(I a,b;m--;)cin>>a>>b,adj[a].emplace_back(b),adj[b].emplace_back(a);
rep(i,1,n+1)if(!dfn[i])dfs(i,i);
cout<<res.size()<<'\n';
for(A& i:res)cout<<i F<<' '<<i S<<'\n';
}
```
:::
# [Necessary Cities](https://cses.fi/problemset/task/2077)
找割點
大部分和找橋一樣，唯一要特判的點是$root$，判斷的是如果他的子樹會是兩個以上的聯通塊，那他就是割點。
複雜度 : $O(n+m)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops,inline")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define I int
#define A auto
#define C char
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,cnt,dfn[maxN],sml[maxN],chk;
vector<I> adj[maxN],res;
bitset<maxN> isin;
void dfs(I now,I last){
dfn[now]=sml[now]=++cnt;
for(I& i:adj[now]){
if(i==last)continue;
if(!dfn[i]){
dfs(i,now),sml[now]=min(sml[now],sml[i]);
if(sml[i]>=dfn[now]&&now!=1&&!isin[now])res.emplace_back(now),isin[now]=1;
}
else sml[now]=min(sml[now],dfn[i]);
}
}
int main(){
IOS
cin>>n>>m,dfn[1]=-1;
for(int a,b;m--;)cin>>a>>b,adj[adj[a].emplace_back(b)].emplace_back(a);
for(I& i:adj[1])if(!dfn[i])++chk,dfs(i,1);
if(chk!=1)res.emplace_back(1);
cout<<res.size()<<'\n';
for(I& i:res)cout<<i<<' ';
}
```
:::
# [Eulerian Subgraphs](https://cses.fi/problemset/task/2078)
不會，但查了就發現有公式解 : ${2^{m-n+cc}}$
2024/9/20: @cot7302 會了
可以知道建出這張圖的生成森林之後剩下的非樹邊都會和一些樹邊購成一個cycle basis，答案就是$2^{basis數}$
複雜度 : $O(m \alpha (n)+ \log n)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr ll maxN=1e5+5,mod=1e9+7;
I n,m,dsu[maxN],cnt;
ll ans;
inline I find(I pos){
return dsu[pos]<0?pos:(dsu[pos]=find(dsu[pos]));
}
inline void join(I a,I b){
a=find(a),b=find(b);
if(a==b)return ;
cnt--;
if(dsu[a]<dsu[b])swap(a,b);
dsu[b]+=dsu[a],dsu[a]=b;
}
I main(){
IOS
cin>>n>>m,ans=1,cnt=n;
fill(dsu,dsu+n+1,-1);
for(I a,b,i=0;i<m;i++)cin>>a>>b,join(a,b);
for(ll mult=2,t=m-n+cnt;t;t>>=1,(mult*=mult)%=mod)if(t&1)(ans*=mult)%=mod;
cout<<ans;
}
```
:::
# [Monster Game I](https://cses.fi/problemset/task/2084)
令$dp_i=$考慮前$i$個數的時候的答案，轉移式就會是 :
$$
dp_i=\min_{0 \le j \lt i} {dp_j+s_i \times f_j}
$$
可以發現和$i$這個位置有關的是$s_i \times f_j$ 這項，顯然轉移式會是一條直線。
再來看一下範圍 :
$$
1 \le s_1 \le s_2 \le \ \dots \ \le s_n \le {10^6}
$$
$$
x \ge f_1 \ge f_2 \ge \ \dots \ \ge f_n \ge 1
$$
可以發現
$1.$ 斜率會非嚴格遞減
$2.$ 位置會非嚴格遞增
作圖可以發現有優超性，可以用deque維護單調隊列。
複雜度 : $O(n)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
long long n;
struct line{
long long x,b,ind;
inline long long fx(long long m){
return x*m+b;
}
inline double intersec(line& l){
return (l.b-b)/(x-l.x);
}
};
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
line tmp = {0,0,0};
cin>>n>>tmp.x;
vector<long long> vec(2*n);
for(auto& i:vec)cin>>i;
deque<line> dq;
dq.emplace_back(tmp);
for(int i = 0;i<n-1;i++){
while(dq.size()>=2&&dq[0].fx(vec[i])>dq[1].fx(vec[i]))dq.pop_front();
if(dq.back().x==vec[i+n])continue;
tmp ={vec[i+n],dq.front().fx(vec[i]),i};
while(dq.size()>=2&&dq[dq.size()-2].intersec(dq[dq.size()-1])>=dq[dq.size()-1].intersec(tmp))dq.pop_back();
dq.emplace_back(tmp);
}
cout<<dq.front().fx(vec[n-1]);
}
```
:::
# [Monster Game II](https://cses.fi/problemset/task/2085)
同上一題，但沒有了單調性。
可以發現轉移點只會越來越多，不會有轉移點過期的問題，所以可以用李超線段樹對值域維護最佳解。
複雜度 : $O(n \log C)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mxn=1e6+1;
ll n,pos;
struct LINE{
ll m,b;
LINE():m(),b(){}
LINE(ll tm,ll tb):m(tm),b(tb){}
inline ll fx(const ll x){
return m*x+b;
}
inline ll intersec(const LINE& l){
return (l.b-b)/(m-l.m);
}
};
struct LICHAO{
vector<LINE> vec;
LICHAO():vec(mxn*4,LINE(1e9,1e9)){}
void upd(LINE tar,const ll now=1,ll l=1,ll r=mxn-1){
if(l==r){
if(vec[now].fx(l)>tar.fx(l))vec[now]=tar;
return;
}
int mid=l+r>>1;
if(vec[now].m<tar.m)swap(vec[now],tar);
if(vec[now].fx(mid)<tar.fx(mid))upd(tar,now<<1|1,mid+1,r);
else swap(tar,vec[now]),upd(tar,now<<1,l,mid);
}
ll query(ll x,ll now=1,ll l=1,ll r=mxn-1){
if(l==r)return vec[now].fx(x);
int mid=l+r>>1;
if(x<=mid)return min(query(x,now<<1,l,mid),vec[now].fx(x));
else return min(query(x,now<<1|1,mid+1,r),vec[now].fx(x));
}
};
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin>>n>>pos;
LICHAO tree;
vector<LINE> vec(n);
for(auto& i:vec)cin>>i.b;
for(auto& i:vec)cin>>i.m;
tree.upd(LINE(pos,0LL));
for(const auto& i:vec)tree.upd(LINE(i.m,tree.query(i.b)));
cout<<tree.query(vec[n-1].b);
}
```
:::
# [Subarray Squares](https://cses.fi/problemset/task/2086)
令$dp_{i,j}=$把前$j$個數拆成$i$個區間的最小花費，則可以列出轉移式：$$
dp_{i,j}=\min_{0 \le x \le j - 1} {dp_{i-1,x}+(\displaystyle\sum_{k=x+1}^j{a_k})^2}
$$
令$pre_x=\displaystyle\sum_{i=0}^x{a_i}$，稍微拆一下發現
$$
(\displaystyle\sum_{k=x+1}^j{a_k})^2=(pre_j-pre_{x})^2=pre_j^2+pre_x^2-2 \times pre_j \times pre_x
$$
看起來可以斜率優化，令$f_{i,j}(x)=-2 \times pre_j \times pre_x+pre_j^2+dp_{i,j}$，則dp轉移式可以改寫成
$$
dp_{i,j}=pre_j^2+\min_{0 \le x \le j - 1} {f_{i-1,x}(j)}
$$
可以發現$f_{i,j}(x)$的斜率在$i$固定時是單調的，而對這些函數查詢帶入的值也是單調的，所以可以用deque維護直線。
時間複雜度：$O(NK)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include <iostream>
#include <deque>
#include <iterator>
using namespace std;
using i128 = __int128_t;
struct line {
long s, i;
long operator()(long x) const { return x * s + i; }
};
bool better(line a, line b, line l) {
return i128(a.i - l.i) * (b.s - a.s) <= i128(a.i - b.i) * (l.s - a.s);
}
int N, K;
long pre[3001], dp[3001];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> N >> K;
for (int i = 1; i <= N; i++) cin >> pre[i], pre[i] += pre[i - 1];
deque<line> dq;
auto query = [&](long x) -> long {
while (ssize(dq) > 1 && dq[0](x) > dq[1](x)) dq.pop_front();
return dq.front()(x);
};
dq.emplace_back(0, 0);
for (int T = 1; T <= K; T++) {
for (int i = T; i <= N; i++) {
dp[i] = query(pre[i]) + pre[i] * pre[i];
}
dq.clear();
for (int i = T; i <= N; i++) {
line add{-2 * pre[i], dp[i] + pre[i] * pre[i]};
while (ssize(dq) > 1 && better(end(dq)[-2], end(dq)[-1], add)) dq.pop_back();
dq.emplace_back(add);
}
}
cout << dp[N];
}
```
:::
另解：
令$cost(i,j)=(pre_j-pre_i)^2$，可以發現$cost(i,j)$滿足四邊形不等式。
:::spoiler 證明
四邊形不等式左式：
$$
cost(i,j)+cost(i+1,j+1)=pre_i^2+pre_j^2+pre_{i+1}^2+pre_{j+1}^2-2pre_ipre_j-2pre_{i+1}pre_{j+1}
$$
四邊形不等式右式：
$$
cost(i,j+1)+cost(i+1,j)=pre_i^2+pre_j^2+pre_{i+1}^2+pre_{j+1}^2-2pre_ipre_{j+1}-2pre_{i+1}pre_j
$$
兩式相減：
$$
\begin{align}
&cost(i,j)+cost(i+1,j+1)-cost(i,j+1)-cost(i+1,j) \\
&=2pre_ipre_{j+1}+2pre_{i+1}pre_j-2pre_ipre_j-2pre_{i+1}pre_{j+1} \\
&=2pre_i(pre_{j+1}-pre_{j})+2pre_{i+1}(pre_j-pre_{j+1}) \\
&=2(pre_i-pre_{i+1})(pre_{j+1}-pre_{j}) \lt 0
\end{align}
$$
故$cost(i,j)$符合四邊形不等式
:::
因為$cost(i,j)$符合四邊形不等式，所以可以套Aliens。
:::spoiler 證明(from oi wiki)
[這裡](https://oi-wiki.org/dp/opt/quadrangle/#%E9%99%90%E5%88%B6%E5%8C%BA%E9%97%B4%E4%B8%AA%E6%95%B0%E7%9A%84%E6%83%85%E5%BD%A2)定理三的證明
:::
時間複雜度：$O(n \log C)$（斜率優化+Aliens）
:::spoiler code:
```cpp=
#include <iostream>
#include <deque>
#include <iterator>
using namespace std;
using i128 = __int128_t;
struct alien {
long val, cnt;
friend bool operator<(alien a, alien b)
{ return a.val < b.val || (a.val == b.val && a.cnt < b.cnt); }
friend auto operator<=>(alien a, alien b) = default;
};
struct line {
long s, i, cnt;
alien operator()(long x, long pen) const { return {x * s + i + pen, cnt + 1}; }
};
bool better(line a, line b, line l) {
return i128(a.i - l.i) * (b.s - a.s) < i128(a.i - b.i) * (l.s - a.s);
}
int N, K;
long pre[3001];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> N >> K;
for (int i = 1; i <= N; i++) cin >> pre[i], pre[i] += pre[i - 1];
auto calc = [&](long pen) -> alien {
deque<line> dq;
auto query = [&](long x) -> alien {
while (ssize(dq) > 1 && dq[0](x, pen) > dq[1](x, pen)) dq.pop_front();
return dq.front()(x, pen);
};
dq.emplace_back(0, 0, 0);
alien ret{};
for (int i = 1; i <= N; i++) {
auto [val, cnt] = query(pre[i]);
ret = {val + pre[i] * pre[i], cnt};
line add{-2 * pre[i], ret.val + pre[i] * pre[i], cnt};
while (ssize(dq) > 1 && better(end(dq)[-2], end(dq)[-1], add)) dq.pop_back();
dq.emplace_back(add);
}
return ret;
};
auto aliens = [&](int k) -> long {
long l = 0, r = 1e16;
while (l + 1 < r) {
long mid = (l + r) >> 1;
auto [val, cnt] = calc(mid);
if (cnt > k) l = mid;
else r = mid;
}
auto [val, cnt] = calc(r);
return val - r * k;
};
cout << aliens(K) << '\n';
}
```
:::
# [Houses and Schools](https://cses.fi/problemset/task/2087)
令$dp_{i,j}=$設了$i$間學校，最後一間在$j$，且只考慮前$j$個人的最小cost，定義$cost(i,j)=$在$i$和$j$各設一間學校，考慮$i$~$j$的人的cost，則dp轉移式為：
$$
dp_{i,j}=\min_{i-1 \le x \lt j} {dp_{i-1,x}+cost(x,j)}
$$
另外可以發現，$cost(i,j)$就是讓左半邊的人走去$i$，右半邊的人走去$j$的cost，而這個$cost(i,j)$正好符合四邊形不等式，所以可以分治/Knuth/Aliens優化。
時間複雜度：$O(kn \log n)$（分治）/$O(n(n+k))$（Knuth）/$O(n \log n \log C)$（Aliens，好像能做到$O(n \log C)$，但我不會）。
:::spoiler 分治優化：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, k;
long pre[3][3001], dp[2][3001];
long cost(int l, int r) {
if (l + 1 >= r) return 0;
int mid = (l + r + 1) >> 1;
return pre[1][mid] - pre[1][l + 1] - (pre[0][mid] - pre[0][l + 1]) * l + pre[2][r] - pre[2][mid] - (pre[0][r] - pre[0][mid]) * (n - r - 1);
}
bool odd_row;
void divide(int l, int r, int ql, int qr) {
if (ql == qr) {
for (int i = l; i < r; i++) dp[odd_row][i] = dp[!odd_row][ql] + cost(ql, i);
return;
}
int mid = (l + r) >> 1;
int opt = mid;
long best = 1e18;
for (int i = min(qr, mid - 1); i >= ql; i--) {
if (dp[!odd_row][i] + cost(i, mid) <= best) {
tie(opt, best) = tuple{i, dp[!odd_row][i] + cost(i, mid)};
}
}
dp[odd_row][mid] = best;
if (l + 1 == r) return;
divide(l, mid, ql, opt);
divide(mid, r, opt, qr);
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> pre[0][i + 1];
pre[1][i + 1] = pre[0][i + 1] * i + pre[1][i];
pre[2][i + 1] = pre[0][i + 1] * (n - i - 1) + pre[2][i];
pre[0][i + 1] += pre[0][i];
}
for (int i = 0; i < n; i++) {
dp[1][i] = pre[0][i] * i - pre[1][i];
}
for (int i = 2; i <= k; i++) {
odd_row = (i & 1);
divide(i - 1, n, i - 2, n - 1);
}
long ans = 1e18;
for (int i = k - 1; i < n; i++) {
ans = min(ans, dp[k & 1][i] + pre[1][n] - pre[1][i + 1] - (pre[0][n] - pre[0][i + 1]) * i);
}
cout << ans << '\n';
}
```
:::
:::spoiler Knuth-Yao :
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(ll i = l;i<r;i++)
constexpr I maxN=3e3+5;
ll n,k,pre[3][maxN],dp[2][maxN];
I t[2][maxN];
inline ll cost(ll l,ll r){
I mid=l+r>>1;
return pre[1][mid]-pre[1][l-1]-(pre[0][mid]-pre[0][l-1])*l+pre[2][r]-pre[2][mid]-(pre[0][r]-pre[0][mid])*(n-r+1);
}
I main(){
IOS
cin>>n>>k;
rep(i,1,n+1){
cin>>pre[0][i];
pre[1][i]+=i*pre[0][i]+pre[1][i-1];
pre[2][i]+=(n-i+1)*pre[0][i]+pre[2][i-1];
pre[0][i]+=pre[0][i-1];
}
t[0][n+1]=t[1][n+1]=n;
rep(i,1,n+1)dp[1][i]=dp[1][i-1]+pre[0][i-1];
rep(i,2,k+1)for(I j=n;j>=i;j--){
dp[i&1][j]=INF;
rep(m,t[!(i&1)][j],min(j,t[i&1][j+1])+1)
if(ll tmp=dp[!(i&1)][m]+cost(m,j);tmp<dp[i&1][j])
dp[i&1][j]=tmp,t[i&1][j]=m;
}
rep(i,1,n+1)dp[k&1][i]+=pre[1][n]-pre[1][i]-(pre[0][n]-pre[0][i])*i;
cout<<*min_element(dp[k&1]+1,dp[k&1]+n+1);
}
```
:::
:::spoiler Aliens：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
long pre[3][3001];
long cost(int l, int r) {
if (l + 1 >= r) return 0;
int mid = (l + r + 1) >> 1;
return pre[1][mid] - pre[1][l + 1] - (pre[0][mid] - pre[0][l + 1]) * l + pre[2][r] - pre[2][mid] - (pre[0][r] - pre[0][mid]) * (n - r - 1);
}
struct alien {
long val, cnt;
friend bool operator<(alien a, alien b)
{ return a.val < b.val || (a.val == b.val && a.cnt < b.cnt); }
friend auto operator<=>(alien a, alien b) = default;
};
struct seg {
int l, r, p;
alien dp_val;
alien operator()(int x, long pen) const {
if (p == -1) return {pre[0][x] * x - pre[1][x] + pen, 1};
return {dp_val.val + cost(p, x) + pen, dp_val.cnt + 1};
};
};
long aliens(int k) {
auto calc = [&](long pen) -> alien {
alien ret{(long)1e18, 0};
deque<seg> dq;
dq.emplace_back(0, n, -1, alien{0, 0});
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.front().r <= i) dq.pop_front();
auto nxt = seg{i + 1, n, i, dq.front()(i, pen)};
ret = min(ret, alien{nxt.dp_val.val + pre[1][n] - pre[1][i + 1] - (pre[0][n] - pre[0][i + 1]) * i, nxt.dp_val.cnt});
while (!dq.empty() && dq.back().l > i && dq.back()(dq.back().l, pen) >= nxt(dq.back().l, pen)) dq.pop_back();
if (dq.empty()) {
dq.emplace_back(nxt);
continue;
}
auto opt = *ranges::lower_bound(views::iota(i + 1, dq.back().r), true, {}, [&](const auto x) {
return nxt(x, pen) <= dq.back()(x, pen);
});
if (opt == n) continue;
nxt.l = opt;
dq.back().r = opt;
dq.emplace_back(nxt);
}
return ret;
};
long l = 0, r = 1e15;
while (l + 1 < r) {
long mid = (l + r) >> 1;
auto [val, cnt] = calc(mid);
if (cnt > k) l = mid;
else r = mid;
}
auto [val, cnt] = calc(r);
return val - r * k;
}
int main() {
int k; cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> pre[0][i + 1];
pre[1][i + 1] = pre[0][i + 1] * i + pre[1][i];
pre[2][i + 1] = pre[0][i + 1] * (n - i - 1) + pre[2][i];
pre[0][i + 1] += pre[0][i];
}
cout << aliens(k) << '\n';
}
```
:::
# [Knuth Division](https://cses.fi/problemset/task/2088/)
可以Knuth-Yao speedup，詳細證明可以看[OI Wiki](https://cses.fi/problemset/task/2088/)。
時間複雜度：$O(n^2)$。
:::spoiler code:
```cpp=
#include <numeric>
#include <iostream>
#include <tuple>
int opt[2][5000];
long pre[5001], dp[5001][5000];
int main() {
int n; std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> pre[i];
pre[i] += pre[i - 1];
}
std::iota(opt[1], opt[1] + n, 0);
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
dp[len][i] = 1e18;
opt[len & 1][i] = opt[!(len & 1)][i];
for (int k = opt[!(len & 1)][i]; k <= opt[!(len & 1)][i + 1]; k++) {
if (dp[k - i + 1][i] + dp[i + len - k - 1][k + 1] < dp[len][i]) {
dp[len][i] = dp[k - i + 1][i] + dp[i + len - k - 1][k + 1];
opt[len & 1][i] = k;
}
}
dp[len][i] += pre[i + len] - pre[i];
//std::printf("len = %d, i = %d, opt = %d, dp = %ld\n", len, i, opt[len & 1][i], dp[len][i]);
}
}
std::cout << dp[n][0];
}
```
:::
# [Apples and Bananas](https://cses.fi/problemset/task/2111)
令$f(x)=\displaystyle\sum x^{a_i}, g(x)=\displaystyle\sum x^{b_i}$，則對整數$w$，答案就會是$[x^w]f(x)g(x)$。
因為次數很高，所以要用FFT做乘法。
時間複雜度：$O(n \log n)$。
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;
template <class T>
using vec = vector<T>;
template <class cpx>
struct FFT_info {
using real = typename cpx::value_type;
static const inline real pi = acos(real{-1});
static constexpr int level = 24;
static const inline array<cpx, level + 1> omega = []() {
array<cpx, level + 1> ret{};
for (int i = 0; i <= level; i++) ret[i] = {cos(2 * pi / (1 << i)), sin(2 * pi / (1 << i))};
return ret;
}();
static const inline array<cpx, level + 1> inv_omega = []() {
array<cpx, level + 1> ret{};
for (int i = 0; i <= level; i++) ret[i] = {cos(-2 * pi / (1 << i)), sin(-2 * pi / (1 << i))};
return ret;
}();
};
template <class cpx>
struct FFT {
static void dft(vector<cpx>& v) {
int N = (int)size(v);
for (int i = N / 2, lv = __lg(N); i > 0; i >>= 1, lv--) {
cpx wn = FFT_info<cpx>::omega[lv];
for (int j = 0; j < N; j += i * 2) {
cpx w = 1;
for (int k = 0; k < i; k++, w *= wn) {
auto x = v[j + k];
auto y = v[j + k + i];
v[j + k] = x + y;
v[j + k + i] = (x - y) * w;
}
}
}
}
static void idft(vector<cpx>& v) {
int N = (int)size(v);
for (int i = 1, lv = 1; i < N; i <<= 1, lv++) {
cpx wn = FFT_info<cpx>::inv_omega[lv];
for (int j = 0; j < N; j += i * 2) {
cpx w = 1;
for (int k = 0; k < i; k++, w *= wn) {
auto x = v[j + k];
auto y = w * v[j + k + i];
v[j + k] = x + y;
v[j + k + i] = x - y;
}
}
}
for (int i = 0; i < N; i++) v[i] /= N;
}
vector<cpx> operator()(const vector<cpx>& a, const vector<cpx>& b) const {
int n = (int)size(a) + (int)size(b) - 1;
int N = n;
if ((N & (N - 1)) != 0) N = 1 << (__lg(n) + 1);
vector<cpx> lhs(N), rhs(N);
copy(begin(a), end(a), begin(lhs));
copy(begin(b), end(b), begin(rhs));
dft(lhs);
dft(rhs);
for (int i = 0; i < N; i++) lhs[i] *= rhs[i];
idft(lhs);
lhs.resize(n);
return lhs;
}
};
using cpx = complex<double>;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int k, n, m; cin >> k >> n >> m;
vec<cpx> a(k + 1), b(k + 1);
for (int i = 0; i < n; i++) {
int x; cin >> x;
a[x] += 1;
}
for (int i = 0; i < m; i++) {
int x; cin >> x;
b[x] += 1;
}
auto ret = FFT<cpx>{}(a, b);
for (int i = 2; i <= k + k; i++) {
cout << llround(ret[i].real()) << " \n"[i == k + k];
}
}
```
:::
# [One Bit Positions](https://cses.fi/problemset/task/2112)
用兩個bitset做，一個不斷左移，然後互相and起來之後`count()`就能得到答案。
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include <bitset>
#include <string>
#include <iostream>
using namespace std;
bitset<200000> x, y;
int main() {
string s; cin >> s;
int n = ssize(s);
for (int i = 0; i < n; i++) x[i] = (s[i] & 1);
y = x;
for (--n; y <<= 1, n--; ) cout << (x & y).count() << ' ';
}
```
:::
時間複雜度：$O(n^2)$，因為bitset常數太好所以可以過。
另解：FFT
令$f(x)=\displaystyle\sum_{i=0}^n{s[i] \times x^i}, g(x)=\displaystyle\sum_{i=0}^n{s[i] \times x^{n-i}}$，對正整數$k$的答案會是$[x^{n+k}]f(x)g(x)$
時間複雜度：$O(n \log n)$。
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;
template <class T>
using vec = vector<T>;
template <class cpx>
struct FFT_info {
using real = typename cpx::value_type;
static const inline real pi = acos(real{-1});
static constexpr int level = 24;
static const inline array<cpx, level + 1> omega = []() {
array<cpx, level + 1> ret{};
for (int i = 0; i <= level; i++) ret[i] = {cos(2 * pi / (1 << i)), sin(2 * pi / (1 << i))};
return ret;
}();
static const inline array<cpx, level + 1> inv_omega = []() {
array<cpx, level + 1> ret{};
for (int i = 0; i <= level; i++) ret[i] = {cos(-2 * pi / (1 << i)), sin(-2 * pi / (1 << i))};
return ret;
}();
};
template <class cpx>
struct FFT {
static void dft(vector<cpx>& v) {
int N = (int)size(v);
for (int i = N / 2, lv = __lg(N); i > 0; i >>= 1, lv--) {
cpx wn = FFT_info<cpx>::omega[lv];
for (int j = 0; j < N; j += i * 2) {
cpx w = 1;
for (int k = 0; k < i; k++, w *= wn) {
auto x = v[j + k];
auto y = v[j + k + i];
v[j + k] = x + y;
v[j + k + i] = (x - y) * w;
}
}
}
}
static void idft(vector<cpx>& v) {
int N = (int)size(v);
for (int i = 1, lv = 1; i < N; i <<= 1, lv++) {
cpx wn = FFT_info<cpx>::inv_omega[lv];
for (int j = 0; j < N; j += i * 2) {
cpx w = 1;
for (int k = 0; k < i; k++, w *= wn) {
auto x = v[j + k];
auto y = w * v[j + k + i];
v[j + k] = x + y;
v[j + k + i] = x - y;
}
}
}
for (int i = 0; i < N; i++) v[i] /= N;
}
vector<cpx> operator()(const vector<cpx>& a, const vector<cpx>& b) const {
int n = (int)size(a) + (int)size(b) - 1;
int N = n;
if ((N & (N - 1)) != 0) N = 1 << (__lg(n) + 1);
vector<cpx> lhs(N), rhs(N);
copy(begin(a), end(a), begin(lhs));
copy(begin(b), end(b), begin(rhs));
dft(lhs);
dft(rhs);
for (int i = 0; i < N; i++) lhs[i] *= rhs[i];
idft(lhs);
lhs.resize(n);
return lhs;
}
};
using cpx = complex<double>;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
string s; cin >> s;
int n = (int)size(s);
vec<cpx> a(n), b(n);
for (int i = 0; i < n; i++) if (s[i] & 1)
a[i] += 1, b[n - i - 1] += 1;
auto ret = FFT<cpx>{}(a, b);
for (int i = n; i < n + n - 1; i++) {
cout << llround(ret[i].real()) << " \n"[i == n + n - 2];
}
}
```
:::
# [Signal Processing](https://cses.fi/problemset/task/2113)
令$f(x)=\displaystyle\sum_{i=0}^n{a_i \times x ^ i}, g(x)=\displaystyle\sum_{i=0}^m{b_i \times x ^ {m-i-1}}$，則答案就會是$f(x)g(x)$中$x$的$0$~$n+m-1$次方項的係數。
時間複雜度：$O(n \log n)$。
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;
template <class T>
using vec = vector<T>;
template <class cpx>
struct FFT_info {
using real = typename cpx::value_type;
static const inline real pi = acos(real{-1});
static constexpr int level = 24;
static const inline array<cpx, level + 1> omega = []() {
array<cpx, level + 1> ret{};
for (int i = 0; i <= level; i++) ret[i] = {cos(2 * pi / (1 << i)), sin(2 * pi / (1 << i))};
return ret;
}();
static const inline array<cpx, level + 1> inv_omega = []() {
array<cpx, level + 1> ret{};
for (int i = 0; i <= level; i++) ret[i] = {cos(-2 * pi / (1 << i)), sin(-2 * pi / (1 << i))};
return ret;
}();
};
template <class cpx>
struct FFT {
static void dft(vector<cpx>& v) {
int N = (int)size(v);
for (int i = N / 2, lv = __lg(N); i > 0; i >>= 1, lv--) {
cpx wn = FFT_info<cpx>::omega[lv];
for (int j = 0; j < N; j += i * 2) {
cpx w = 1;
for (int k = 0; k < i; k++, w *= wn) {
auto x = v[j + k];
auto y = v[j + k + i];
v[j + k] = x + y;
v[j + k + i] = (x - y) * w;
}
}
}
}
static void idft(vector<cpx>& v) {
int N = (int)size(v);
for (int i = 1, lv = 1; i < N; i <<= 1, lv++) {
cpx wn = FFT_info<cpx>::inv_omega[lv];
for (int j = 0; j < N; j += i * 2) {
cpx w = 1;
for (int k = 0; k < i; k++, w *= wn) {
auto x = v[j + k];
auto y = w * v[j + k + i];
v[j + k] = x + y;
v[j + k + i] = x - y;
}
}
}
for (int i = 0; i < N; i++) v[i] /= N;
}
vector<cpx> operator()(const vector<cpx>& a, const vector<cpx>& b) const {
int n = (int)size(a) + (int)size(b) - 1;
int N = n;
if ((N & (N - 1)) != 0) N = 1 << (__lg(n) + 1);
vector<cpx> lhs(N), rhs(N);
copy(begin(a), end(a), begin(lhs));
copy(begin(b), end(b), begin(rhs));
dft(lhs);
dft(rhs);
for (int i = 0; i < N; i++) lhs[i] *= rhs[i];
idft(lhs);
lhs.resize(n);
return lhs;
}
};
using cpx = complex<double>;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m; cin >> n >> m;
vec<cpx> lhs(n), rhs(m);
for (int i = 0; i < n; i++) {
int x; cin >> x;
lhs[i] += x;
}
for (int i = 0; i < m; i++) {
int x; cin >> x;
rhs[i] += x;
}
reverse(ALL(rhs));
auto ret = FFT<cpx>{}(lhs, rhs);
for (int i = 0; i < n + m - 1; i++) {
cout << llround(ret[i].real()) << " \n"[i == n + m - 2];
}
}
```
:::
# [New Roads Queries](https://cses.fi/problemset/task/2101)
可以發現原題可以轉換成「把邊加入的時間當成邊權，求一張無向圖上兩點所有可能的簡單路徑上邊權最大值的最小值」，所以就把最小生成森林蓋出來，兩點簡單路徑上的最大值就是答案了。要維護這個其實可以只用啟發式或按秩合併的並查集就好了。合併時多紀錄邊權，查詢的時候暴力跳就好。
時間複雜度：$O((m+q) \log n)$
:::spoiler code:
```cpp=
#include <iostream>
#include <vector>
#include <ranges>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, q; cin >> n >> m >> q;
vector<int> dsu(begin(views::iota(0, n + 1)), end(views::iota(0, n + 1))), height(n + 1, 0), weight(n + 1, 0);
auto root = [&](int x) -> int { for (; dsu[x] != x; x = dsu[x]); return x; };
auto join = [&](int x, int y, int t) -> void {
x = root(x), y = root(y);
if (x == y) return;
if (height[x] < height[y]) swap(x, y);
height[x] += height[x] == height[y];
dsu[y] = x;
weight[y] = t;
};
auto query = [&](int x, int y) -> int {
if (root(x) != root(y)) return -1;
int ret = 0;
while (x != y) {
if (height[x] > height[y]) swap(x, y);
ret = max(ret, weight[x]);
x = dsu[x];
}
return ret;
};
for (int a, b, i = 1; i <= m; i++) {
cin >> a >> b;
join(a, b, i);
}
for (int a, b; q--; ) {
cin >> a >> b;
cout << query(a, b) << '\n';
}
```
:::
另解：整體二分
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct disjoint_set {
vector<int> _;
vector<tuple<int, int, int>> op;
disjoint_set(int L) :_(L + 1, -1), op() {}
void reset() { ranges::fill(_, -1); }
int root(int x) { while (_[x] > 0) x = _[x]; return x; }
void merge(int x, int y) {
x = root(x), y = root(y);
if (x == y) {
op.emplace_back(x, y, 0);
return;
}
if (_[x] > _[y]) swap(x, y);
op.emplace_back(x, y, _[y]);
_[x] += _[y];
_[y] = x;
}
bool connect(int x, int y) { return root(x) == root(y); }
int undo() {
auto [x, y, neg_ysz] = op.back(); op.pop_back();
if (neg_ysz) {
_[y] = neg_ysz;
_[x] -= _[y];
}
return ssize(op);
}
int op_cnt() const { return ssize(op); }
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, q; cin >> n >> m >> q;
disjoint_set D(n);
vector<pair<int, int>> edges(m);
for (auto& [x, y] : edges) cin >> x >> y;
vector<pair<int, int>> qry(q);
vector<int> ans(q, -1);
for (auto& [x, y] : qry) cin >> x >> y;
auto solve = [&](auto&& self, int l, int r, vector<int> qid) -> void {
if (r - l == 1) {
for (auto x : qid) ans[x] = r;
return;
}
int mid = (l + r) >> 1;
while (D.op_cnt() <= mid) {
auto [x, y] = edges[D.op_cnt()];
D.merge(x, y);
}
while (D.op_cnt() > mid + 1) D.undo();
vector<int> to_l, to_r;
for (auto x : qid) {
auto [u, v] = qry[x];
if (D.connect(u, v)) to_l.emplace_back(x);
else to_r.emplace_back(x);
}
self(self, l, mid, to_l);
self(self, mid, r, to_r);
};
solve(solve, -1, m, vector(begin(views::iota(0, q)), end(views::iota(0, q))));
for (int i = 0; i < q; i++) cout << (ans[i] == m ? -1 : (qry[i].first == qry[i].second ? 0 : (ans[i] + 1))) << '\n';
}
```
:::
# [Dynamic Connectivity](https://cses.fi/problemset/task/2133/)
動態dsu。
dsu可以回滾，所以可以用時間線段樹維護每條邊生效的時間區間，最後dfs整棵線段樹得出答案。
複雜度 : $O(k \log k \log n)$
:::spoiler code:
```cpp=
#include <map>
#include <tuple>
#include <vector>
#include <cassert>
#include <iostream>
struct disjoint_set {
int cc_cnt;
std::vector<int> _;
std::vector<std::tuple<int, int, int>> operates;
disjoint_set(int n) : cc_cnt(n), _(n + 1, -1), operates() {}
int root(int x) { while (_[x] > 0) x = _[x]; return x; }
void join(int x, int y) {
x = root(x), y = root(y);
if (x == y) {
operates.emplace_back(x, y, 0);
return;
}
if (_[x] > _[y]) std::swap(x, y);
_[x] += _[y];
operates.emplace_back(x, y, _[y]);
_[y] = x;
--cc_cnt;
}
void undo() {
auto [x, y, cnt] = operates.back();
if (x == y) {
operates.pop_back();
return;
}
++cc_cnt;
_[y] = cnt;
_[x] -= cnt;
operates.pop_back();
}
int operate_count() const { return std::ssize(operates); }
};
std::vector<std::pair<int, int>> T[400020];
int ans[100001];
void apply(int l, int r, int al, int ar, int id, std::pair<int, int> e) {
if (al <= l && r <= ar) {
//std::printf("l = %d, r = %d, al = %d, ar = %d, id = %d, e = [%d, %d]\n", l, r, al, ar, id, e.first, e.second);
T[id].emplace_back(e);
return;
}
int mid = (l + r) >> 1;
if (mid <= al) return apply(mid, r, al, ar, id << 1 | 1, e);
if (mid >= ar) return apply(l, mid, al, ar, id << 1, e);
apply(l, mid, al, ar, id << 1, e);
apply(mid, r, al, ar, id << 1 | 1, e);
}
int main() {
int n, m, k; std::cin >> n >> m >> k;
std::map<std::pair<int, int>, int> mp;
for (int u, v, __m = m; __m--; ) {
std::cin >> u >> v;
if (u > v) std::swap(u, v);
mp[{u, v}] = 0;
}
for (int t, u, v, i = 1; i <= k; i++) {
std::cin >> t >> u >> v;
if (u > v) std::swap(u, v);
if (t == 1) mp[{u, v}] = i;
else {
apply(0, k + 1, mp[{u, v}], i, 1, {u, v});
mp.erase({u, v});
}
}
for (auto [e, t] : mp) {
apply(0, k + 1, t, k + 1, 1, e);
}
disjoint_set D(n);
auto dfs = [&](auto&& dfs, int l, int r, int id) -> void {
int cnt = D.operate_count();
for (auto [u, v] : T[id]) D.join(u, v);
if (r - l == 1) ans[l] = D.cc_cnt;
else {
int mid = (l + r) >> 1;
dfs(dfs, l, mid, id << 1);
dfs(dfs, mid, r, id << 1 | 1);
}
while (D.operate_count() > cnt) D.undo();
};
dfs(dfs, 0, k + 1, 1);
for (int i = 0; i <= k; i++) std::cout << ans[i] << ' ';
std::cout << '\n';
}
```
:::
# [Parcel Delivery](https://cses.fi/problemset/task/2121)
MCMF
複雜度 : $O(nmk)$ 合理相信dinic和spfa
:::spoiler 建模方式:
建超級源點，連$flow=k,cost=0$的邊到點$1$，剩下正常建，匯點在$n$。
:::
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=5e2+5;
I n,m,k,ans,id[maxN],dis[maxN];
bitset<maxN> inq;
struct EDGE{
I to,rto,rc,cost;
EDGE(){}
EDGE(I a,I b,I c,I d):to(a),rto(b),rc(c),cost(d){}
};
vector<EDGE> adj[maxN];
inline void addedge(I a,I b,I c,I d){
adj[a].emplace_back(EDGE(b,adj[b].size(),c,d));
adj[b].emplace_back(EDGE(a,adj[a].size()-1,0,-d));
}
inline bool spfa(I s,I t){
fill(dis,dis+t+1,INT_MAX);
inq.reset();
queue<I> q;
q.emplace(s),dis[s]=0;
for(I from;!q.empty();){
from=q.front(),q.pop(),inq[from]=0;
for(auto& [to,rto,rc,cost]:adj[from])if(dis[to]>dis[from]+cost&&rc){
dis[to]=dis[from]+cost;
if(!inq[to])inq[q.emplace(to)]=1;
}
}
return dis[t]!=INT_MAX;
}
I dfs(I now,I t,I flow=INT_MAX){
if(now==t||!flow)return flow;
inq[now]=1;
I ret=0,tmp;
for(I& i=id[now];i<adj[now].size();i++){
auto& [to,rto,rc,cost]=adj[now][i];
if(dis[to]==dis[now]+cost&&rc&&!inq[to]){
tmp=dfs(to,t,min(flow,rc));
rc-=tmp,ret+=tmp,flow-=tmp,adj[to][rto].rc+=tmp,ans+=cost*tmp;
}
}
return ret;
}
inline I mcmf(I s,I t){
I ret=0;
while(spfa(s,t)){
while(I tmp=dfs(s,t))ret+=tmp;
fill(id,id+t+1,0);
}
return ret;
}
I main(){
IOS
cin>>n>>m>>k;
addedge(0,1,k,0);
for(I a,b,c,d;m--;){
cin>>a>>b>>c>>d;
addedge(a,b,c,d);
}
if(mcmf(0,n)==k)return cout<<ans,0;
cout<<-1;
}
```
:::
# [Task Assignment](https://cses.fi/problemset/task/2129)
二分圖最大權匹配
就是MCMF :rage:
複雜度 : $O({n^4})$，CSES上沒有卡人的測資，然後比$O(n^3)$快:EEEEE:
:::spoiler 建模方式:
額就亂建，建超源超匯
:::
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=5e2+5;
I n,ans,id[maxN],dis[maxN];
bitset<maxN> inq;
struct EDGE{
I to,rto,rc,cost,cap;
EDGE(){}
EDGE(I a,I b,I c,I d):to(a),rto(b),rc(c),cap(c),cost(d){}
};
vector<EDGE> adj[maxN];
inline void addedge(I a,I b,I c,I d){
adj[a].emplace_back(EDGE(b,adj[b].size(),c,d));
adj[b].emplace_back(EDGE(a,adj[a].size()-1,0,-d));
}
inline bool spfa(I s,I t){
fill(dis,dis+t+1,INT_MAX);
inq.reset();
queue<I> q;
q.emplace(s),dis[s]=0;
for(I from;!q.empty();){
from=q.front(),q.pop(),inq[from]=0;
for(auto& [to,rto,rc,cost,cap]:adj[from])if(dis[to]>dis[from]+cost&&rc){
dis[to]=dis[from]+cost;
if(!inq[to])inq[q.emplace(to)]=1;
}
}
return dis[t]!=INT_MAX;
}
I dfs(I now,I t,I flow=INT_MAX){
if(now==t||!flow)return flow;
inq[now]=1;
I ret=0,tmp;
for(I& i=id[now];i<adj[now].size();i++){
auto& [to,rto,rc,cost,cap]=adj[now][i];
if(dis[to]==dis[now]+cost&&rc&&!inq[to]){
tmp=dfs(to,t,min(flow,rc));
rc-=tmp,ret+=tmp,flow-=tmp,adj[to][rto].rc+=tmp,ans+=cost*tmp;}
}
return ret;
}
inline I mcmf(I s,I t){
I ret=0;
while(spfa(s,t)){
while(I tmp=dfs(s,t))ret+=tmp;
fill(id,id+t+1,0);
}
return ret;
}
I main(){
cin>>n;
rep(i,1,n+1)addedge(0,i,1,0);
rep(i,1,n+1)rep(j,1,n+1){
I val;cin>>val;
addedge(i,j+n,1,val);
}
rep(i,1,n+1)addedge(i+n,n<<1|1,1,0);
mcmf(0,n<<1|1);
cout<<ans<<'\n';
rep(i,1,n+1)for(auto& [to,rto,rc,cost,cap]:adj[i])if(cap&&!rc)
cout<<i<<' '<<to-n<<'\n';
}
```
:::
另解:
KM直接跑/slack優化
複雜度:$O(n^4)/O(n^3)$
沒寫
# [Distinct Routes II](https://cses.fi/problemset/task/2130)
MCMF
然後要像[Distinct Routes](https://cses.fi/problemset/task/1711)一樣構解
複雜度 : $O(nmk)$
:::spoiler 建模方式:
蓋超源，連一條$flow=k,cost=0$的邊到$1$，然後匯點是$n$。
:::
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
struct EDGE{
I to,rto,rc,cap,cost;
EDGE(){}
EDGE(I a,I b,I c,I d):to(a),rto(b),rc(c),cap(c),cost(d){}
};
I n,m,k,ans,id[maxN],dep[maxN];
vector<EDGE> adj[maxN];
bitset<maxN> vis;
vector<vector<I>> FLOWS;
vector<I> add;
inline void addedge(I a,I b,I c,I d){
adj[a].emplace_back(EDGE(b,adj[b].size(),c,d));
adj[b].emplace_back(EDGE(a,adj[a].size()-1,0,-d));
}
inline bool spfa(I s,I t){
fill(dep,dep+t+1,INT_MAX);
vis.reset();
queue<I> q;
q.emplace(s),dep[s]=0;
for(I from;!q.empty();){
from=q.front(),q.pop(),vis[from]=0;
for(auto& [to,rto,rc,cap,cost]:adj[from])if(dep[to]>dep[from]+cost&&rc){
dep[to]=dep[from]+cost;
if(!vis[to])vis[q.emplace(to)]=1;
}
}
return dep[t]!=INT_MAX;
}
I dfs(I now,I t,I flow=INT_MAX){
if(now==t||!flow)return flow;
vis[now]=1;
I ret=0,tmp;
for(I& i=id[now];i<adj[now].size();i++){
auto& [to,rto,rc,cap,cost]=adj[now][i];
if(dep[to]==dep[now]+cost&&!vis[to]&&rc){
tmp=dfs(to,t,min(flow,rc));
flow-=tmp,rc-=tmp,adj[to][rto].rc+=tmp,ret+=tmp,ans+=cost*tmp;
}
}
return ret;
}
inline I solve(I s,I t){
I ret=0;
while(spfa(s,t)){
while(I tmp=dfs(s,t))ret+=tmp;
fill(id,id+t+1,0);
}
return ret;
}
void cal(I now){
add.emplace_back(now);
if(now==n)return;
for(I& i=id[now];i<adj[now].size();i++){
auto& [to,rto,rc,cap,cost]=adj[now][i];
if(cap&&!rc)return rc++,cal(to);
}
add.pop_back();
}
I main(){
IOS
cin>>n>>m>>k;
addedge(0,1,k,0);
for(I a,b;m--;)cin>>a>>b,addedge(a,b,1,1);
if(solve(0,n)<k)return cout<<-1,0;
while(cal(1),add.size())FLOWS.emplace_back(add),add.clear();
cout<<ans<<'\n';
rep(i,0,k){
cout<<FLOWS[i].size()<<'\n';
for(I j:FLOWS[i])cout<<j<<' ';
cout<<'\n';
}
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
