9.9万

disheng
Behappyeveryday
Acwer

crr
ciaocian

Ymer

Kitebin
Forever_Czz

ღSupperღ
faith_9
Protein

XX31MRK
stan_ym

## Kruskal重构树

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int n,m,q,idx;

int f[N][21],cost[N][21],fa[N];
int w[N];

struct Edge{
int a,b,c;
bool operator<(const Edge&t) const {
return c < t.c;
}
}e[N];

int find(int x) {
if(fa[x] == x) return x;

return fa[x] = find(fa[x]);
}

int main() {

scanf("%d%d%d",&n,&m,&q);

for(int i=1;i<=n;i++) scanf("%d",&w[i]);

for(int i=1;i<=m;i++) {
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
}

sort(e + 1,e + m + 1); // 对边排序

for(int i=1;i<N;i++) fa[i] = i;

idx = n;

// 构造重构树
for(int i=1;i<=m;i++) {
int a = find(e[i].a);
int b = find(e[i].b);
int c = e[i].c;
if(a == b) continue;
++idx;
fa[a] = idx; fa[b] = idx;
w[idx] = w[a] + w[b];
f[a][0] = idx;
f[b][0] = idx;
cost[a][0] = c - w[a];
cost[b][0] = c - w[b];
}

w[0] = w[idx]; // 上界设为根

// 倍增求最高可以到达的地方
for(int j=1;j<=20;j++) {
for(int i=1;i<=idx;i++) {
f[i][j] = f[f[i][j - 1]][j - 1];
cost[i][j] = max(cost[i][j - 1],cost[f[i][j - 1]][j - 1]);
}
}

for(int i=1;i<=q;i++) {
int x,k; scanf("%d%d",&x,&k);
for(int j=20;j>=0;j--) if(cost[x][j] <= k) x = f[x][j];
printf("%d\n",w[x] + k);
}

return 0;
}

## 虚树

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 3e5 + 10,M = N * 2;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n,m;
int w[M],h[N],e[M],ne[M],idx;
int id[N],nw[N],cnt;
int dep[N],sz[N],top[N],fa[N],son[N],st[N],tp;
int root;
int is[N];
bool choosen[N];

ll minv[N]; // 表示要删掉这个点要付出的代价

void add(int a,int b,int c) {
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
}

void dfs1(int u,int father ,int depth) {
dep[u] = depth, fa[u] = father, sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father) continue;
minv[j] = min(minv[u],(ll)w[i]);
dfs1(j, u, depth + 1);
sz[u] += sz[j];
if (sz[son[u]] < sz[j]) son[u] = j;
}
}

void dfs2(int u,int t) {
id[u] = ++ cnt, top[u] = t;
if (!son[u]) return;
dfs2(son[u], t);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
}

int lca(int x,int y)
{
while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]];

if (dep[x]<dep[y]) return x;

return y;
}

bool CMP(int a,int b) {
return id[a] < id[b];
}

void ins(int x)
{
if (tp==0)
{
st[tp=1]=x;
return;
}
int ance=lca(st[tp],x);//相当于z
while ((tp>1)&&(dep[ance]<dep[st[tp-1]]))
{
--tp;
}
if ((!tp)||(st[tp]!=ance)) st[++tp]=ance;
st[++tp]=x;
}//增量构建

ll dp(int u)
{
ll temp = 0;

for(int i=h[u];~i;i=ne[i]) {
int x = e[i];
temp += dp(x);
}

h[u] = -1;

if(choosen[u]) return minv[u];

return min(minv[u],temp);
}

int main() {

memset(h,-1,sizeof h);

scanf("%d",&n);

for(int i=0;i<n-1;i++) {
int a,b,c; scanf("%d%d%d",&a,&b,&c);
}

minv[1] = INF;
dfs1(1, -1, 1);
dfs2(1, 1);

idx = 0;
memset(h,-1,sizeof h);

scanf("%d",&m);

while(m--) {
int len; scanf("%d",&len);
for(int i=1;i<=len;i++) {
scanf("%d",&is[i]);
choosen[is[i]] = true;
}

sort(is + 1,is + len + 1,CMP);

if(is[1]!=1) st[tp=1] = 1; //加入根

for(int i=1;i<=len;i++) ins(is[i]);

printf("%lld\n",dp(1));

idx = 0;
for(int i=1;i<=len;i++) {
choosen[is[i]] = false;
}

}

}

## 树链剖分

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 100010,M = N * 2;

int n,m;
int w[N],h[N],e[M],ne[M],idx;
int id[N],nw[N],cnt;
int dep[N],sz[N],top[N],fa[N],son[N];

struct Tree
{
int l, r;
}tr[N * 4];

e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}

void dfs1(int u,int father ,int depth) {
dep[u] = depth, fa[u] = father, sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father) continue;
dfs1(j, u, depth + 1);
sz[u] += sz[j];
if (sz[son[u]] < sz[j]) son[u] = j;
}
}

void dfs2(int u,int t) {
id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
if (!son[u]) return;
dfs2(son[u], t);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
}

void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
auto &root = tr[u], &left = tr[u << 1],&right = tr[u << 1 | 1];
}
}

void build(int u, int l, int r)
{
tr[u] = {l, r, 0, nw[r]};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}

void update(int u,int l,int r,int k) {
if(l <= tr[u].l && r >= tr[u].r) {
tr[u].sum += k * (tr[u].r - tr[u].l + 1);
return ;
}

pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) update(u << 1,l,r,k);
if(r > mid) update(u << 1 | 1,l,r,k);
pushup(u);
}

ll query(int u, int l, int r)
{
if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
ll res = 0;
if (l <= mid) res += query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}

void update_path(int u,int v,int k) {

while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) swap(u,v);
update(1,id[top[u]],id[u],k);
u = fa[top[u]];
}

if(dep[u] < dep[v]) swap(u,v);
update(1,id[v],id[u],k);
}

ll query_path(int u,int v) {
ll res = 0;
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) swap(u,v);
res += query(1,id[top[u]],id[u]);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u,v);
res += query(1,id[v],id[u]);
return res;
}

void update_tree(int u,int k) {
update(1,id[u],id[u] + sz[u] - 1,k);
}

ll query_tree(int u) {
return query(1,id[u],id[u] + sz[u] - 1);
}

int main() {

memset(h,-1,sizeof h);

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&w[i]);

for(int i=0;i<n-1;i++) {
int a,b; scanf("%d%d",&a,&b);
}

dfs1(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);

scanf("%d",&m);

while(m--) {
int t,u,v,k;
scanf("%d%d",&t,&u);
if(t == 1) {
scanf("%d%d",&v,&k);
update_path(u,v,k);
}
else if(t == 2) {
scanf("%d",&k);
update_tree(u,k);
}
else if(t == 3) {
scanf("%d",&v);
printf("%lld\n",query_path(u,v));
}
else printf("%lld\n",query_tree(u));
}

return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;

int Next[N];
map<string,int> mp;
int idx;
string str[N];
int s[N];
bool st[N];

void work(string &s) {

for(int i=1;i<=m;i++) {
bool flag = true;
for(int j=0;j<m;j+=i) {
int len = min(i,m - j);
if(!(s.substr(0,len) == s.substr(j,len) ))
{
// cout << s.substr(0,len) << " " << s.substr(j,len) << endl;
flag = false;
break;
}
}
if(!flag) {
st[i] = true;
}
}
}

int main(){

cin >> n >> m;

for(int i=1;i<=n;i++)
{
cin >> str[i];
if(!mp.count(str[i])) {
mp[str[i]] = ++ idx;
}
s[i] = mp[str[i]];
}

for(int i=2,j=0;i<=n;i++)
{
while(j && s[i] != s[j + 1]) j = Next[j];
if(s[i] == s[j + 1]) j ++ ;
Next[i] = j;
}

int len = n - Next[n];

for(int i=1;i<=n;i++) {
work(str[i]);
}

int maxv = 1;

while(st[maxv]) maxv ++ ;

cout << len * maxv << endl;

return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;

string get_min(string &s) {

int i = 0 , j = 1;

while(i < n && j < n) {

int k = 0;
while(k < n && s[i + k] == s[j + k]) k ++ ;
if(k == n) break;
if(s[i + k] > s[j + k]) i = i + k + 1;
else j = j + k + 1;

if(i == j) j ++ ;
}

int k = min(i,j);

return s.substr(k,n);
}

int main() {

string s,t; cin >> s >> t;

n = s.size();

s = s + s;
t = t + t;

s = get_min(s);
t = get_min(t);

if(s == t) {
puts("Yes");
cout << s << endl;
return 0;
}
puts("No");

return 0;
}

#include <bits/stdc++.h>

#define ull unsigned long long

using namespace std;

const int N=1010;

const int base=131;

set<ull,bool> s;

int n,m,A,B;
char g[N];
ull h[N][N],p[N * N];

ull get(ull h[],int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}

int main(){

scanf("%d%d%d%d",&n,&m,&A,&B);

p[0] = 1;

for(int i=1;i<N*N;i++) p[i] = p[i - 1] * base;

for(int i=1;i<=n;i++) {
scanf("%s",g + 1);
for(int j=1;j<=m;j++)
h[i][j] = h[i][j - 1] * base + (g[j] - '0');
}

unordered_set<ull> s;

for(int j=B;j<=m;j++) {
ull temp = 0;
for(int i=1;i<=n;i++) {
temp = p[B] * temp + get(h[i],j - B + 1,j);

if(i > A) temp -= get(h[i - A],j - B + 1,j) * p[A * B];
if(i >= A) s.insert(temp);
}
}

int T; scanf("%d",&T);

while(T--) {
ull res = 0;
for(int i=1;i<=A;i++) {
scanf("%s",g + 1);
for(int j=1;j<=B;j++) {
res = res * base + (g[j] - '0');
}
}
if(s.count(res)) puts("1");
else puts("0");
}

return 0;
}

## 线段树

• 维护序列，线段树区间乘合加，维护区间和
#include <iostream>
#include <cstring>
#include <algorithm>

#define ll long long

using namespace std;

const int N = 100010;

struct Tree{
int l,r;
};

Tree tr[N << 2];
int n,mod,m;
int w[N];

void pushup(int u)
{
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}

{
a.sum = ((ll)a.sum * mul % mod + (ll)(a.r - a.l + 1) * add % mod) % mod;
a.mul = ((ll)a.mul * mul) % mod;
}

void pushdown(int u)
{
tr[u].mul = 1;
}

void build(int u,int l,int r)
{
tr[u].l = l;
tr[u].r = r;
tr[u].mul = 1;
if(l == r){
tr[u].sum = w[l] % mod;
return ;
}

int mid = l + r >> 1;

build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);

pushup(u);
}

void modify(int u,int l,int r,int mul,int add)
{
if(l <= tr[u].l  && r >= tr[u].r) eval(tr[u],mul,add);
else
{
pushdown(u);

int mid = tr[u].l + tr[u].r >> 1;

if(l <= mid) modify(u << 1,l,r,mul,add);
if(r > mid) modify(u << 1 | 1,l,r,mul,add);

pushup(u);
}

}

ll query(int u,int l,int r)
{
if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;

pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;

if(r <= mid) return query(u << 1,l,r);
else if(l > mid) return query(u << 1 | 1,l,r);
else
{
ll left = query(u << 1,l,r);
ll right = query(u << 1 | 1,l,r);
ll res = (left + right) % mod;

return res;
}

}

int main(){

ios :: sync_with_stdio(false);
cin.tie(0);

cin >> n >> mod;

for(int i=1;i<=n;i++) cin >> w[i];

build(1,1,n);

cin >> m;

while(m--)
{
int op,l,r;
cin >> op >> l >> r;
if(op == 1)
{
int c;
cin >> c;
modify(1,l,r,c,0);
}
else if(op == 2)
{
int c;
cin >> c;
modify(1,l,r,1,c);
}
else
{
cout << query(1,l,r) << endl;
}
}

return 0;
}

• 线段树+矩阵
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 200010;

typedef array<ll, 3> vec;
typedef array<vec, 3> mat;

vec operator+(const vec& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = a[i] + b[i];
return c;
}

vec operator-(const vec& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = a[i] - b[i];
return c;
}

vec operator*(const mat& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
c[i] += a[i][j] * b[j];
return c;
}

mat operator*(const mat& a, const mat& b)
{
mat c;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
c[i][j] = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
c[i][k] += a[i][j] * b[j][k];
return c;
}

struct Tree{
int l,r;
bool used;
vec sum; // sum{[f[i] ^ 0 ,f[i] ^ 1,f[i] ^ 2]}
};

Tree tr[N << 2];
bool st[N];
mat S = {vec({1,0,0}),vec({0,1,0}),vec({0,0,1})};
mat SUB = {vec({1,0,0}),vec({-1,1,0}),vec({1,-2,1})};
int Q,D,n;

vec get(int u) {
if(!tr[u].used) return {0,0,0};

return tr[u].sum;
}

void pushup(int u)
{
tr[u].sum = (get(u << 1) + get(u << 1 | 1));
}

{
}

void pushdown(int u)
{
}

void build(int u,int l,int r)
{
tr[u].l = l;
tr[u].r = r;
tr[u].sum = {0,0,0};
tr[u].used = true;
if(l == r){
tr[u].sum = {1,0,0};
tr[u].used = false;
return ;
}

int mid = l + r >> 1;

build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);

pushup(u);
}

void modify(int u,int l,int r,mat &add)
{
if(l <= tr[u].l  && r >= tr[u].r) {
}
else
{
pushdown(u);

int mid = tr[u].l + tr[u].r >> 1;

if(l <= mid) modify(u << 1,l,r,add);
if(r > mid) modify(u << 1 | 1,l,r,add);

pushup(u);
}
}

void modify(int u, int x, bool used)
{
if (tr[u].l == x && tr[u].r == x) {
tr[u].used = used;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, used);
else modify(u << 1 | 1, x, used);
pushup(u);
}
}

int main(){

n=2e5;

build(1,1,n);

scanf("%d%d",&Q,&D);

while(Q--) {
int x; scanf("%d",&x);
int l = max(1,x - D);
int r = x;
if(!st[x]) {
if(l < r)
modify(1,x,true);
st[x] = true;
}
else {
if(l < r)
modify(1,l,r-1,SUB);
modify(1,x,false);
st[x] = false;
}
auto res = tr[1].sum;
ll ans = (res[2] - res[1]) / 2;
printf("%lld\n",ans);
}

return 0;
}
• 线段树维护二进制

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 3e5 + 10;

struct Tree{
int l,r;
int ans;
int r_0;
int r_1;
};

Tree tr[N << 2];
int n,q,a[N];

{
int len = a.r - a.l + 1;
if(a.sum >= len) {
a.r_1 = a.r,a.ans = a.r;
a.r_0 = 0;
}
else if(a.sum <= 0){
a.r_0 = a.r,a.ans = 0;
a.r_1 = 0;
}
}

void pushup(int u)
{
if(tr[u << 1].r_0 != tr[u << 1].r) tr[u].r_0 = tr[u << 1].r_0;
else tr[u].r_0 = max(tr[u << 1 | 1].r_0,tr[u << 1].r_0);

if(tr[u << 1].r_1 != tr[u << 1].r) tr[u].r_1 = tr[u << 1].r_1;
else tr[u].r_1 = max(tr[u << 1 | 1].r_1,tr[u << 1].r_1);

tr[u].ans = max(tr[u << 1].ans,tr[u << 1 | 1].ans);
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{

}

void build(int u,int l,int r)
{
tr[u].l = l;
tr[u].r = r;
tr[u].sum = 0;
tr[u].r_0 = r;
tr[u].r_1 = 0;
tr[u].ans = 0;

if(l == r){

return ;
}

int mid = l + r >> 1;

build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);

pushup(u);
}

void modify(int u,int l,int r,int add)
{
if(l <= tr[u].l  && r >= tr[u].r) {
}
else
{
pushdown(u);

int mid = tr[u].l + tr[u].r >> 1;

if(l <= mid) modify(u << 1,l,r,add);
if(r > mid) modify(u << 1 | 1,l,r,add);

pushup(u);
}

}

int query(int u,int l,int r,int v)
{
if(l <= tr[u].l && r >= tr[u].r) {
if(v == 0) return tr[u].r_0;
else {

return tr[u].r_1;
}

}

pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;

if(r <= mid) return query(u << 1,l,r,v);
else if(l > mid) return query(u << 1 | 1,l,r,v);
else
{
int left = query(u << 1,l,r,v);
int right = query(u << 1 | 1,l,r,v);
if(left != tr[u << 1].r) {
return left;
}

return max(left,right);
}

}

void insert(int x) {
int p = query(1,x,3e5,1);
if(p == 0) modify(1,x,x,1);
else {
modify(1,x,p,-1);
modify(1,p+1,p+1,1);
}

}

void del(int x) {
int p = query(1,x,3e5,0);
if(p == 0) modify(1,x,x,-1);
else {
modify(1,x,p,1);
modify(1,p+1,p+1,-1);
}

}

int main() {

build(1,1,3e5);

scanf("%d%d",&n,&q);

for(int i=1;i<=n;i++ ) {
int x; scanf("%d",&x);
a[i] = x;
insert(x);

}

for(int i=1;i<=q;i++) {
int x,y; scanf("%d%d",&x,&y);
del(a[x]);
a[x] = y;
insert(y);
printf("%d\n",tr[1].ans);
}

return 0;
}

## 串串

• trie
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1000010;

int ne[N][26],cnt[N],idx;
char str[N];
int n,m;
void insert()
{
int p=0;
for(int i=0;i<strlen(str);i++)
{
int &temp=ne[p][str[i]-'a'];
if(!temp) temp=++idx;
p=temp;
}
cnt[p]++;
}

int query()
{
int p=0,res=0;
for(int i=0;i<strlen(str);i++)
{
int &temp=ne[p][str[i]-'a'];
if(!temp) break;
res+=cnt[temp];
p=temp;
}

return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",str);
insert();
}
for(int i=0;i<m;i++)
{
scanf("%s",str);
printf("%d\n",query());
}

return 0;
}

• KMP

n - Next[n]可以求出循环节的长度，Next[i]表示以i为后缀能匹配最长的前缀长度

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n,m;

char s[N],t[N];

int Next[N];

int main(){

scanf("%d%s%d%s",&n,s + 1,&m,t + 1);

for(int i=2,j=0;i<=n;i++)
{
while(j && s[i] != s[j + 1]) j = Next[j];
if(s[i] == s[j + 1]) j ++ ;
Next[i] = j;
}

for(int i=1,j=0;i<=m;i++)
{
while(j && t[i] != s[j + 1]) j = Next[j];
if(t[i] == s[j + 1]) j ++ ;
if(j == n)
{
cout << i - j << " ";
j = Next[j];
}
}

return 0;
}
• 最小表示法
string get_min(string &s) { // 这里的s要翻倍s = s + s

int i = 0 , j = 1;

while(i < n && j < n) {

int k = 0;
while(k < n && s[i + k] == s[j + k]) k ++ ;
if(k == n) break;
if(s[i + k] > s[j + k]) i = i + k + 1;
else j = j + k + 1;

if(i == j) j ++ ;
}

int k = min(i,j);

return s.substr(k,n);
}
• 字符串哈希
#include<iostream>
#include<cstring>
#include<cstdio>
#define ull unsigned long long
using namespace std;

const int N=1000010;
const int base=131;
char str[N];
ull h[N],p[N];
ull get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
scanf("%s",str+1);
int n=strlen(str+1);
p[0]=1;
for(int i=1;i<=n;i++)
{
h[i]=h[i-1]*base+str[i]-'a'+1;
p[i]=p[i-1]*base;
}
int m;
cin>>m;
int l1,l2,r1,r2;
for(int i=0;i<m;i++)
{
cin>>l1>>r1>>l2>>r2;
if(get(l1,r1)==get(l2,r2))
puts("Yes");
else
puts("No");
}
return 0;
}

## 分解质因数

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int primes[N],cnt;
bool st[N];

void init() {

st[1] = true;
st[0] = true;

for(int i=2;i<N;i++)
{
if(!st[i]) primes[cnt ++ ] = i;

for(int j=0;primes[j] * i < N ; j ++ )
{
st[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
}
}
}

int main(){

init();

int T;

cin >> T;

while(T -- )
{
int n;

cin >> n;

for(int i=0;primes[i]*primes[i]<=n;i++)
{
int x = primes[i];
if(n % x == 0)
{
int c = 0;

while(n % x == 0) c ++ ,n /= x;

cout << x << " " << c << endl;
}
}

if(n > 1) cout << n << " " << 1 << endl;

cout << endl;
}

return 0;
}

## NTT

• 多项式乘法
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int g = 3, gi = 332748118, mod = 998244353; // g为原根，gi为g的逆元
const int M = 1 << 22;

int tot,bit;
int a[M], b[M],rev[M];
int n,m;

int qmi(int a, int b) //快速幂，a为底数，k为指数
{
int res = 1;
while (b)
{
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}

void NTT(int *a, int n, int type) // NTT，type=1时系数表示法转点值表示法，否则点值表示法转系数表示法
{
for (int i = 0; i < n; ++i) //先将a变成最后的样子
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1)
{                                                            //在这之前NTT与FFT无异
int gn = qmi(type ? g : gi, (mod - 1) / (i << 1)); //单位原根g_n
for (int j = 0; j < n; j += (i << 1))                    //枚举具体区间，j也就是区间右端点
{
int g0 = 1;
for (int k = 0; k < i; ++k, g0 = 1ll * g0 * gn % mod) //合并，记得要取模
{
int x = a[j + k], y = 1ll * g0 * a[i + j + k] % mod;
a[j + k] = (x + y) % mod;
a[i + j + k] = (x - y + mod) % mod;
}
}
}
}

int main()
{

cin >> n >> m;

while((1 << bit) < n + m + 1) bit ++ ;
tot = 1 << bit;

for(int i=0;i<tot;i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

memset(a,0,sizeof a);
memset(b,0,sizeof b);

for(int i=0;i<=n;i++) cin >> a[i];
for(int i=0;i<=m;i++) cin >> b[i];

NTT(a, tot, 1);
NTT(b, tot, 1);

for (int i = 0; i < tot; ++i)
a[i] = 1ll * a[i] * b[i] % mod; // O(n)乘法

NTT(a, tot, 0); //点值表示法转系数表示法

int inv = qmi(tot, mod - 2); // inv为len的逆元（费马小定理求逆元）

for (int i = 0; i <= n + m; ++i) //输出
printf("%d ",1ll * a[i] * inv % mod);
puts("");

return 0;
}

• 多项式求逆和多项式快速幂
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 400003, mod = 998244353, G = 3, Gi = 332748118;

int n, k, A[N]; // n表示有多少项 0 ~ n-1,k表示快速幂次数
int ans[N];
int rev[N];
int Ln[N];
int Exp[N];

int ch = getchar(), res = 0;
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9'){
res = (res * 10ll + ch - '0') % mod;
ch = getchar();
}
return res;
}

int qmi(int a, int b){
int res = 1;
while(b){
if(b & 1) res = (LL) res * a % mod;
a = (LL) a * a % mod;
b >>= 1;
}
return res;
}

void NTT(int *A, int limit, int type){
for(int i = 0;i < limit;i ++)
if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int mid = 1;mid < limit;mid <<= 1){
int Wn = qmi(type == 1 ? G : Gi, (mod - 1) / (mid << 1));
for(int j = 0;j < limit;j += mid << 1){
int w = 1;
for(int k = 0;k < mid;k ++, w = (LL) w * Wn % mod){
int x = A[j + k], y = (LL) w * A[j + k + mid] % mod;
A[j + k] = (x + y) % mod;
A[j + k + mid] = (x - y + mod) % mod;
}
}
}
if(type == -1){
int inv = qmi(limit, mod - 2);
for(int i = 0;i < limit;i ++) A[i] = (LL) A[i] * inv % mod;
}
}

void poly_inv(int *A, int deg){
static int tmp[N];
if(deg == 1){
ans[0] = qmi(A[0], mod - 2);
return;
}
poly_inv(A, deg + 1 >> 1);
int limit = 1, L = -1;
while(limit <= (deg << 1)){limit <<= 1; L ++;}
for(int i = 0;i < limit;i ++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
for(int i = 0;i < deg;i ++) tmp[i] = A[i];
for(int i = deg;i < limit;i ++) tmp[i] = 0;
NTT(tmp, limit, 1); NTT(ans, limit, 1);
for(int i = 0;i < limit;i ++) ans[i] = (2 - (LL) ans[i] * tmp[i] % mod + mod) % mod * ans[i] % mod;
NTT(ans, limit, -1);
for(int i = deg;i < limit;i ++) ans[i] = 0;
}

void poly_Ln(int *A, int deg){
static int tmp[N];
poly_inv(A, deg);
for(int i = 1;i < deg;i ++) tmp[i - 1] = (LL) i * A[i] % mod;
tmp[deg - 1] = 0;
int limit = 1, L = -1;
while(limit <= (deg << 1)){limit <<= 1; L ++;}
for(int i = 0;i < limit;i ++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
NTT(ans, limit, 1); NTT(tmp, limit, 1);
for(int i = 0;i < limit;i ++) Ln[i] = (LL) ans[i] * tmp[i] % mod;
NTT(Ln, limit, -1);
for(int i = deg + 1;i < limit;i ++) Ln[i] = 0;
for(int i = deg;i;i --) Ln[i] = (LL) Ln[i - 1] * qmi(i, mod - 2) % mod;
Ln[0] = 0;
for(int i = 0;i < limit;i ++) ans[i] = tmp[i] = 0;
}

void poly_Exp(int *A, int deg){
if(deg == 1){
Exp[0] = 1;
return;
}
poly_Exp(A, deg + 1 >> 1);
poly_Ln(Exp, deg);
for(int i = 0;i < deg;i ++) Ln[i] = (A[i] + (i == 0) - Ln[i] + mod) % mod;
int limit = 1, L = -1;
while(limit <= (deg << 1)){limit <<= 1; L ++;}
for(int i = 0;i < limit;i ++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
NTT(Exp, limit, 1); NTT(Ln, limit, 1);
for(int i = 0;i < limit;i ++) Exp[i] = (LL) Exp[i] * Ln[i] % mod;
NTT(Exp, limit, -1);
for(int i = deg;i < limit;i ++) Exp[i] = 0;
for(int i = 0;i < limit;i ++) Ln[i] = ans[i] = 0;
}

void poly_ni(int n){ // 多项式求逆

memset(A,0,sizeof A);
memset(ans,0,sizeof ans);
memset(rev,0,sizeof rev);
memset(Exp,0,sizeof Exp);
memset(Ln,0,sizeof Ln);

for(int i = 1;i < n;i ++) {
A[i] = -x + mod;
}

A[0] = 1 % mod;

poly_inv(A,n);

for(int i=0;i<n;i++) printf("%d ",ans[i]);

}

void poly_mi(int n,int k) { // 多项式快速幂

memset(A,0,sizeof A);
memset(ans,0,sizeof ans);
memset(rev,0,sizeof rev);
memset(Exp,0,sizeof Exp);
memset(Ln,0,sizeof Ln);

for(int i = 0;i < n;i ++) A[i] = read();

poly_Ln(A, n);

for(int i = 0;i < n;i ++) A[i] = (LL) Ln[i] * k % mod, Ln[i] = 0;

poly_Exp(A, n);

for(int i = 0;i < n;i ++) printf("%d ", Exp[i]);

puts("");
}

int main(){

poly_ni(n);

}

## 分治NTT

// 分治ntt处理ai和bi

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 262144, K = 17, mod = 998244353, G = 3; // K设为log(N)

int n, i, x;

int pos[N + 5], A[N + 5], B[N + 5], W[N + 5], g[K + 5], ng[K + 5], inv[N + 5], inv2;

int p[N + 5], invp[N + 5], cost[N + 5], w[N + 5], pre[N + 5];

int ea[N + 5], eb[N + 5], fa[N + 5], fb[N + 5];

int qmi(int a, int b)
{
int res = 1;

while (b)
{
if (b & 1)
res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}

return res;
}

inline void NTT(int *a, int n, int t)
{
for (int i = 1; i < n; i++)
if (i < pos[i])
swap(a[i], a[pos[i]]);
for (int d = 0; (1 << d) < n; d++)
{
int m = 1 << d, m2 = m << 1, _w = t == 1 ? g[d] : ng[d];
for (int i = 0; i < n; i += m2)
for (int w = 1, j = 0; j < m; j++)
{
int &A = a[i + j + m], &B = a[i + j], t = 1LL * w * A % mod;
A = B - t;
if (A < 0)
A += mod;
B = B + t;
if (B >= mod)
B -= mod;
w = 1LL * w * _w % mod;
}
}
if (t == -1)
for (int i = 0, j = inv[n]; i < n; i++)
a[i] = 1LL * a[i] * j % mod;
}

void solve(int l, int r)
{
if (l == r)
{
if (l)
{
ea[l+1]=((ea[l]-(1LL-p[l])*fa[l]%mod*pre[l])%mod+mod)*invp[l]%mod; // fa[l]就是ntt处理出来的那个求和
eb[l+1]=((eb[l]-cost[l]-(1LL-p[l])*fb[l]%mod*pre[l])%mod+mod)*invp[l]%mod;
}
return;
}
int mid = (l + r) >> 1;
solve(l, mid);
int k = 1;
while (k < r - l + 1) k <<= 1;
for (int i = 0; i < k; i++)
A[i] = B[i] = W[i] = 0;

for (int i = l; i <= mid; i++)
{
A[i - l] = ea[i];
B[i - l] = eb[i];
}

for (int i = 1; i <= r - l; i++)
W[i] = w[i];

int j = __builtin_ctz(k) - 1;
for (int i = 0; i < k; i++)
pos[i] = pos[i >> 1] >> 1 | ((i & 1) << j);

NTT(A,k,1);
NTT(B,k,1);
NTT(W,k,1);

for (int i = 0; i < k; i++)
{
A[i] = 1ll * A[i] * W[i] % mod;
B[i] = 1ll * B[i] * W[i] % mod;
}

NTT(A,k,-1);
NTT(B,k,-1);

for (int i = mid + 1; i <= r; i++)
{
fa[i] = (fa[i] + A[i - l]) % mod;
fb[i] = (fb[i] + B[i - l]) % mod;
}
solve(mid + 1, r);
}

int main()
{

// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);

for (g[K] = qmi(G, (mod - 1) / N), ng[K] = qmi(g[K], mod - 2), i = K - 1; ~i; i--)
g[i] = 1LL * g[i + 1] * g[i + 1] % mod, ng[i] = 1LL * ng[i + 1] * ng[i + 1] % mod;

for (int i = 1; i <= N; i++)
inv[i] = qmi(i, mod - 2);
inv2 = inv[2];

int T;

scanf("%d", &T);

while (T--)
{

scanf("%d", &n);

for (int i = 0; i < n; i++)
{
int x;
scanf("%d%d", &x, &cost[i]);
p[i] = 1ll * x * inv[100] % mod;
invp[i] = 100ll * inv[x] % mod;
}

for(int i=1;i<n;i++) {
scanf("%d",&w[i]);
pre[i] = (pre[i - 1] + w[i]) % mod;
}
for(i=1;i<n;i++)pre[i]=qmi(pre[i],mod-2);

for (i = 0; i <= n; i++) fa[i] = fb[i] = 0;
ea[0] = 1, eb[0] = 0;
ea[1] = 1, eb[1] = (mod-cost[0])%mod;

solve(0,n-1);

int res = 1ll * (mod - eb[n]) * qmi(ea[n],mod - 2) % mod;
printf("%d\n",res);
}

return 0;
}

## 线性基(求最大异或和)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 100010;

int n;
LL a[N];

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);

int k = 0;
for (int i = 62; i >= 0; i -- )
{
for (int j = k; j < n; j ++ )
if (a[j] >> i & 1)
{
swap(a[j], a[k]);
break;
}
if (!(a[k] >> i & 1)) continue;
for (int j = 0; j < n; j ++ )
if (j != k && (a[j] >> i & 1))
a[j] ^= a[k];
k ++ ;
if (k == n) break;
}

LL res = 0;
for (int i = 0; i < k; i ++ ) res ^= a[i];
printf("%lld\n", res);
return 0;
}

## MIN25求1-n的质数和

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

typedef long long LL;

namespace Min25 {

int prime[N], id1[N], id2[N], flag[N], ncnt, m;

LL g[N], sum[N], a[N], T, n;

inline int ID(LL x) {
return x <= T ? id1[x] : id2[n / x];
}

inline LL calc(LL x) {
return x * (x + 1) / 2 - 1;
}

inline LL f(LL x) {
return x;
}

inline void init() {
m = ncnt = 0;
T = sqrt(n + 0.5);
for (int i = 2; i <= T; i++) {
if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
a[++m] = n / l;
if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (int i = 1; i <= ncnt; i++)
for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++)
g[j] = g[j] - (LL)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
}

inline LL solve(LL x) {
if (x <= 1) return x;
return n = x, init(), g[ID(n)];
}

}

int main() {
LL n; scanf("%lld", &n);
printf("%lld\n", Min25::solve(n));
}

## 数学小结论

• (a + b) = (a ^ b) + 2 * (a & b)
• $\lfloor x / y \rfloor$ = z,已知x和z求y的范围是[x / (z + 1) + 1,x / z]
• 网格中从（0，0）出发向下和向右走，到达（x,y)的方案数未C(x,x + y)
• 组合数求和：$\sum_{i=0}^k\binom{n+i}n=\binom{n+k+1}{n+1}$
• 错排公式: D(n) = (n-1) [D(n-2) + D(n-1)]，特殊地，D(1) = 0, D(2) = 1.
• 博弈论公平组合游戏可以视为一颗有向数，一个节点的sg(u) = 子节点mex{sg(v)}，可以将多个状态拆分成，多个局面下的一个状态，并且sg(root_1) ^ sg(root_2) …。

11天前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 100010;

int n;
LL a[N];

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);

int k = 0;
for (int i = 62; i >= 0; i -- )
{
for (int j = k; j < n; j ++ )
if (a[j] >> i & 1)
{
swap(a[j], a[k]);
break;
}
if (!(a[k] >> i & 1)) continue;
for (int j = 0; j < n; j ++ )
if (j != k && (a[j] >> i & 1))
a[j] ^= a[k];
k ++ ;
if (k == n) break;
}

LL res = 0;
for (int i = 0; i < k; i ++ ) res ^= a[i];
printf("%lld\n", res);
return 0;
}

14天前
#include <bits/stdc++.h>

using namespace std;

const int N = 5010, M = 100010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;

for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[i] && d[ver] > d[t] + w[i])
{
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if (!st[ver])
{
q[tt ++ ] = ver;
if (tt == N) tt = 0;
st[ver] = true;
}
}
}
}

return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
flow = cost = 0;
while (spfa())
{
int t = incf[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
}

int main()
{
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
}

int flow, cost;
EK(flow, cost);
printf("%d %d\n", flow, cost);

return 0;
}

15天前
#include <bits/stdc++.h>

#define pii pair<int,int>
#define ll long long

using namespace std;

const int N = 100010, M = 200010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
pii edge[N];

int p[N];

void add(int a, int b, int c,int d)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (d[ver] == -1 && f[i])
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T)  return true;
q[ ++ tt] = ver;
}
}
}
return false;
}

int find(int u, int limit)
{
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;  // 当前弧优化
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i])
{
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}

void build(int D) {

memset(h,-1,sizeof h);
idx = 0;

for(int i=1;i<=m;i++) {
int a = edge[i].first;
int b = edge[i].second;
}

for(int i=1;i<=n;i++) {
if(p[i] > 0) {
if(p[i] >> D & 1) add(i,T,INF,0);
}
}
}

int dinic(int D)
{
build(D);

int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}

int main() {

scanf("%d%d",&n,&m);

S = 0,T = n + 1;

for(int i=1;i<=m;i++) scanf("%d%d",&edge[i].first,&edge[i].second);

int K; scanf("%d",&K);

memset(p,-1,sizeof p);

while(K--) {
int a,b; scanf("%d%d",&a,&b);
p[a] = b;
}

ll ans = 0;

for(int i=0;i<=30;i++) {
ll res = (ll)dinic(i);
ans += res << i;
}

printf("%lld\n",ans);

return 0;
}

15天前
#include <bits/stdc++.h>

using namespace std;

const int N = 10010,M=200010,INF=1e8;

int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],cur[N];

void add(int a,int b,int c) {
e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx ++ ;
}

bool bfs() {
int hh = 0,tt = 0;
memset(d,-1,sizeof d);
q[0] = S,d[S] = 0,cur[S] = h[S];

while(hh <= tt) {
int t = q[hh ++ ];
for(int i=h[t];~i;i=ne[i]) {
int ver = e[i];
if(d[ver] == -1 && f[i]) {
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if(ver == T) return true;
q[++ tt] = ver;
}
}
}
return false;
}

int find(int u,int limit) {
if(u == T) return limit;
int flow = 0;
for(int i=cur[u];~i && flow < limit ; i = ne[i] ) {
cur[u] = i;
int ver = e[i];
if(d[ver] == d[u] + 1 && f[i] ) {
int t = find(ver,min(f[i],limit - flow));
if(!t) d[ver] = -1;
f[i] -= t,f[i ^ 1] += t,flow += t;
}
}
return flow;
}

int dinic() {

int r =0,flow;
while(bfs()) while(flow = find(S,INF)) {
r += flow;
}
return r;
}

int main() {
scanf("%d%d%d%d",&n,&m,&S,&T);

memset(h,-1,sizeof h);

while(m -- ) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);