ACM模板-稳赚个人版

稳赚又丑又T的板子

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scd(x) scanf("%lf", &x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-10;
const double PI = acos(-1.0);

字符串操作

char函数

1
2
3
4
5
6
7
8
9
10
11
char s1[maxn], s2[maxn];
char c; int n;
strcat(s1,s2); // s1+=s2;
strncat(s1,s2,n); // 加上s2的前n个字符
strchr(s1,c); // 返回s1中第一次出现c的位置
strnchr(s1,c); // 返回s1中最后一次出现c的位置
strstr(s1,s2); // 返回s1中第一次出现s2的位置
strcmp(s1,s2); // 比较 能比大小的
strncmp(s1,s2,n); // 比前n个
strcpy(s1,s2); // s1=s2;
strncpy(s1,s2,n); // s1为s2前n个字符

string函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
string s1,s2;
int pos,len; char c;
s1.find(s2);
// 返回值为s2第一次出现在s1的位置
// 若s2不是s1子串返回 string::npos
s1.replace(pos,len,s2);
// s1从pos位开始长度len的子串替换成s2
s1.substr(pos,len);
s1.insert(pos,s2);
s1.insert(pos,s2,len);
// 插入s2的前len个字符
s1.insert(pos,len,c);
// 插入len个c
s1.erase(pos,len);

字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 数组版
int trie[maxn][26];
int cnt[maxn];
void insert(char *s){
int u=0;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if(!trie[u][tmp]){
trie[u][tmp]=++n;
cnt[n]++;
}
else cnt[trie[u][tmp]]++;
u=trie[u][tmp];
}
}
int find(char *s){
int u=0,len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if(!trie[u][tmp]) return 0;
u=trie[u][tmp];
} return cnt[u];
}


// 指针版
struct trie {
int cnt; trie *next[26];
trie(){ cnt=0; rep(i,0,26) next[i]=NULL; }
};
trie *root,*p;
void insert(char* s){
p=root; int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if (p->next[tmp]==NULL) p->next[tmp]=new trie();
p=p->next[tmp]; p->cnt++;
}
}
int find(char* s){
p=root;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if (p->next[tmp] == NULL)
return 0;
p=p->next[tmp];
} return p->cnt;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int nex[maxn];
void getnext(char* s){
int i=0,j=-1,len=strlen(s);
nex[0]=-1; while(i<len){
if(j==-1||s[i]==s[j]){
i++; j++; nex[i]=j;
} else j=nex[j];
}
}
int kmp(char *s1,char *s2){
int i=0,j=0; getnext(s2);
int len1=strlen(s1),len2=strlen(s2);
while(i<len1&&j<len2){
if(j==-1||s1[i]==s2[j]){ i++; j++; }
else j=nex[j];
if(j==len2) return i-j+1;
} return 0;
}
/* 关于next数组应用如
if(nex[pos]&&pos%(pos-nex[pos])==0)
即有s的前pos位有(pos/(pos-nex[pos]))个长度为pos-nex[pos]的前缀*/
//求总前缀数 dp
rep(i,1,len+1){
int tmp=nex[i];
while(tmp) sum++,tmp=nex[tmp];
}
// 根据nex求s1和s2尾头衔接重叠部分
s2+='*'+s1; int q=getnext(s2); ans=s2.substr(0,q);
// 套娃nex求前缀和后缀相同部分
// on预处理求每个前缀在字符串中出现了几次
void getnum(int len){
rep(i,1,len+1) num[nex[i]]++;
dep(i,len,1) num[nex[i]]+=num[i];
int t=len; while(t){ vv.push_back(t),t=nex[t]; }
pf("%d\n",vv.size()); sort(vv.begin(),vv.end());
for(int x:vv) pf("%d %d\n",x,num[x]+1); // 长度和次数
}

EXKMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int nex[maxn], extend[maxn];
void getnext(char* s){
int aa=0,len=strlen(s);
nex[0]=len;
while(aa<len-1&&s[aa]==s[aa+1]) aa++;
nex[1]=aa; aa=1;
rep(i,2,len){
int p=aa+nex[aa]-1;
int l=nex[i-aa];
if(i+l-1>=p){
int j=(p-i+1)>0?p-i+1:0;
while(i+j<len&&s[i+j]==s[j]) j++;
nex[i]=j; aa=i;
} else nex[i]=l;
}
}
void getextend(char* s1,char* s2){
int aa=0; mst(nex,0); getnext(s2);
int len1=strlen(s1),len2=strlen(s2);
int minl=min(len1,len2);
while(aa<minl&&s1[aa]==s2[aa]) aa++;
extend[0]=aa; aa=0;
rep(i,1,len1){
int p=aa+extend[aa]-1,l=nex[i-aa];
if(i+l-1>=p){
int j=(p-i+1)>0?p-i+1:0;
while(i+j<len1&&j<len2&&s1[i+j]==s2[j]) j++;
extend[i]=j; aa=i;
} else extend[i]=l;
}
}

马拉车

1
2
3
4
5
6
7
8
9
10
11
12
int che[2*maxn];
char s[maxn],ma[2*maxn];
void manacher(char* s,int len0){
int len=0; ma[len++]='$'; ma[len++]='#';
rep(i,0,len0) ma[len++]=s[i],ma[len++]='#';
ma[len]=0; int maxx=0,num=0;
rep(i,0,len){
che[i]=maxx>i?min(che[2*num-i],maxx-i):1;
while(ma[i+che[i]]==ma[i-che[i]]) che[i]++;
if(i+che[i]>maxx) maxx=i+che[i],num=i;
}
}

AC自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// 计每个单词有无出现 注释里写记单词数的 以*开头
int ans;
struct node{
node* next[26]; // 最大100够的 所有题
node* fail;
int end; // 在单词末尾做标记
//* int id;
node(){
end=0; //* id=0;
fail=0;
mst(next,0);
}
};
node* root;
// 建字典树
//* int tot;
void insert(char* s){
node* p=root;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if(p->next[tmp]==NULL) p->next[tmp]=new node();
p=p->next[tmp];
}
p->end++;
//* p->id=++tot;
}
queue<node*>q;
// fail数组:root指向NULL 没出现过的指向root 出现过的指向前一个
void getfail(){
root->fail=NULL;
q.push(root);
while(!q.empty()){
node* fr=q.front(); q.pop();
rep(i,0,26) if(fr->next[i]){
node* tem=fr->fail;
while(tem){
if(tem->next[i]){
fr->next[i]->fail=tem->next[i];
break;
} tem=tem->fail;
}
if(tem==NULL) fr->next[i]->fail=root;
q.push(fr->next[i]);
}
}
}
//* num[maxn], mark[maxn], cnt;
void ac_auto(char* s){
node* p=root;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
while(!p->next[tmp] && p!=root) p=p->fail;
p=p->next[tmp];
if(!p) p=root;
node* tem=p;
while(tem!=root){
if(tem->end>=0){
ans+=tem->end;
tem->end=-1; // 出现过了第二次遇到不再统计
}
else break;
/* if(tem->id){
*if(!mark[tem->id])
*num[cnt++]=tem->id;
// num按在s串中出现顺序存id
*mark[tem->id]++;
//mark存出现与否 顺便存次数
}*/
tem=tem->fail;
}
}
}
// 虽然指针版怪弱智的 但舍不得了
struct ACAM{
int ch[maxn][26];
int tot,num[maxn],nex[maxn];
void init(){
tot=1; rep(i,0,26) ch[0][i]=1;
rep(i,0,26) ch[1][i]=0;
}
void insert(char* s,int x){
int n=strlen(s+1),p=1;
rep(i,1,n+1){
int tmp=s[i]-'a';
if(!ch[p][tmp]){
ch[p][tmp]=++tot;
rep(j,0,26) ch[tot][j]=0;
num[tot]=0;
}
p=ch[p][tmp];
} num[p]++;
}
void getfail(){
queue<int>q; q.push(1); nex[1]=0;
while(!q.empty()){
int fr=q.front(); q.pop();
rep(i,0,26) if(!ch[fr][i]) ch[fr][i]=ch[nex[fr]][i];
else nex[ch[fr][i]]=ch[nex[fr]][i],q.push(ch[fr][i]);
}
}
void query(char* s){
int n=strlen(s+1),p=1; cnt=0;
rep(i,1,n+1){
int tmp=s[i]-'a',k=ch[p][tmp];
while(k>1) ...,k=nex[k];
p=ch[p][tmp];
}
}
}ac;

后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int s[maxn];
int sa[maxn],rk[maxn];
int height[maxn];
int t1[maxn],t2[maxn],c[maxn];
int best[20][maxn];
char ss[maxn];
void getsa(int *s,int n,int m){
int *x=t1,*y=t2;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[i]=s[i]]++;
rep(i,1,m) c[i]+=c[i-1];
dep(i,n-1,0) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
rep(i,n-k,n) y[p++]=i;
rep(i,0,n) if(sa[i]>=k) y[p++]=sa[i]-k;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[y[i]]]++;
rep(i,1,m) c[i]+=c[i-1];
dep(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1; x[sa[0]]=0;
rep(i,1,n) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n) break; m=p;
}
}
void getheight(int n){
int k=0;
rep(i,1,n+1) rk[sa[i]]=i;
rep(i,0,n){
if(k) k--;
int j=sa[rk[i]-1];
while(s[i+k]==s[j+k]) k++;
height[rk[i]]=k;
}
}
void RMQ(int n){
int lg=(int)(log(n*1.0)/log(2.0));
rep(i,1,n+1) best[0][i]=height[i];
rep(i,1,lg+1) for(int j=1;j+(1<<i)-1<=n;j++)
best[i][j]=min(best[i-1][j],best[i-1][j+(1<<i>>1)]);
}
int lcp(int x,int y){
x=rk[x]; y=rk[y];
if(x>y) swap(x,y); x++;
int lg=(int)(log(1.0*(y-x+1))/log(2.0));
return min(best[lg][x],best[lg][y-(1<<lg)+1]);
}

后缀自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
struct SAM{
int next[maxn<<1][26],link[maxn<<1],len[maxn<<1];
int a[maxn<<1],id[maxn<<1],right[maxn<<1];
int tot,root,last;
inline void init(){
rep(i,0,tot+1) mst(next[i],0),right[i]=0;
mst(len,0); mst(link,0); tot=last=root=1;
}
inline void extend(int x){
int p=last,now=++tot; right[now]=1; len[now]=len[p]+1;
while(p&&!next[p][x]) next[p][x]=now,p=link[p];
if(!p) link[now]=root;
else{
int q=next[p][x];
if(len[q]==len[p]+1) link[now]=q;
else{
int tmp=++tot;
memcpy(next[tmp],next[q],sizeof(next[q]));
link[tmp]=link[q]; link[q]=link[now]=tmp; len[tmp]=len[p]+1;
while(p&&next[p][x]==q) next[p][x]=tmp,p=link[p];
}
} last=now;
}
inline void slove(){
// 拓扑排序
rep(i,1,tot+1) ++a[len[i]];
rep(i,1,tot+1) a[i]+=a[i-1];
rep(i,1,tot+1) id[a[len[i]]--]=i;
// wz可能会记不得的sam简单运用:
// ·s是否包含t:跑一遍t的点看next是不是都有值
// ·s不同子串个数:累加len[id[i]]-len[link[id[i]]]
// ·s不同子串总长度:累加(len[id[i]]+1)*len[id[i]]/2-(len[link[id[i]]]+1)*len[link[id[i]]]/2
// ·s所有子串出现次数:
int las=1; rep(i,0,n){
num[next[las][s[i]-'a']]=1;
las=next[las][s[i]-'a'];
} ll ans(0); dep(i,tot,1){
num[link[id[i]]]+=num[id[i]];
ans+=1ll*(len[id[i]]-len[link[id[i]]])*num[id[i]];
}
// ·字典序第k大子串:
//* op为0指计算本质不同子串 为1计算全部
if(!op) rep(i,1,tot+1) right[i]=1;
else dep(i,tot,1){
int t=id[i]; right[fa[t]]+=right[t];
} right[1]=0;
dep(i,tot,1){
int t=id[i]; num[t]+=right[t];
rep(j,0,26) if(next[t][j]) num[t]+=num[next[t][j]];
} if(k>num[1]) return (void)pf("No such line.\n");
int now=1,cnt=0;
while(k>0){
rep(i,0,26) if(next[now][i]){
if(k<=num[next[now][i]]){
ans[cnt++]='a'+i; now=next[now][i];
k-=right[now]; break;
} else k-=num[next[now][i]];
}
} ans[cnt]=0; pf("%s\n",ans);
// ·t在s出现次数
// ·t在s出现位置
// ·多个字符串间的最长公共子串
}
inline void lcs(){
int las=1,mx(0),cnt(0); rep(i,0,m){
if(!next[las][t[i]-'a']){
while(las&&!next[las][t[i]-'a']) las=link[las];
if(las) cnt=len[las]+1,las=next[las][t[i]-'a'];
else las=1,cnt=0;
} else ++cnt,las=next[las][t[i]-'a'];
mx=max(mx,cnt);
} pf("%d\n",mx);
}
}sam;

最大最小表示法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int getmin(char* s){
int len=strlen(s);
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len){
int tmp=s[(i+k)%len]-s[(j+k)%len];
if(!tmp) k++; else{
if(tmp>0) i+=k+1; else j+=k+1;
if(i==j) j++; k=0;
}
} return min(i,j);
}
int getmax(char* s){
int len=strlen(s);
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len){
int tmp=s[(i+k)%len]-s[(j+k)%len];
if(!tmp) k++; else{
if(tmp<0) i+=k+1; else j+=k+1;
if(i==j) j++; k=0;
}
} return min(i,j);
}

回文树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 回文树初始节点01 表示偶/奇数长度串的根节点
struct PAM{
struct node{
int child[26],cnt,fail,num,len,pos;
// len是从开头开始最长回文串长度
// num是以这个结点结束的回文串数
// cnt是节点表示的本质不同回文串数
}tt[maxn];
int last,n,tot;
char s[maxn];
inline void clear(){
rep(i,0,tot+1){
mst(tt[i].child,0);
tt[i].cnt=tt[i].fail=tt[i].len=tt[i].num=0;
}
last=n=0; tt[0].fail=tot=1; tt[1].len=-1;
}
inline int getfail(int x){
while(s[n-tt[x].len-1]!=s[n]) x=tt[x].fail;
return x;
}
inline void add(char ch){
s[++n]=ch;
int cur=getfail(last);
if(!tt[cur].child[ch-'a']){
int now=++tot;
tt[now].len=tt[cur].len+2;
int p=getfail(tt[cur].fail);
tt[now].fail=tt[p].child[ch-'a'];
tt[cur].child[ch-'a']=now;
tt[now].num=tt[tt[now].fail].num+1;
}
last=tt[n].pos=tt[cur].child[ch-'a'];
++tt[last].cnt;
}
inline void count(){
dep(i,tot,0) tt[tt[i].fail].cnt+=tt[i].cnt;
}
}pam;

hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int seed[2]={27174403,19260817};
// 18052103
// 18271131 小燕学号 不是质数
int mod; // 998244353 100000007
// 大质数 9999999999999937/17
int hs[2][maxn],bas[2][maxn];
void init(){
bas[0][0]=bas[1][0]=1;
rep(j,0,2) rep(i,1,n+1){
bas[j][i]=1ll*bas[j][i-1]*seed[j]%mod;
hs[j][i]=1ll*hs[j][i-1]*seed[j]%mod+s[i];
if(hs[j][i]>=mod) hs[j][i]-=mod;
}
}
int getsum(int j,int l,int r){
int res=hs[j][r]-1ll*hs[j][l-1]*bas[j][r-l+1]%mod;
if(res<0) res+=mod; return res;
}

自闭图论

dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct node{
int id,dt;
bool operator < (const node a) const{
return dt>a.dt;
}
};
priority_queue<node>q;
int n,m,s,t,tot;
int dis[maxn],vis[maxn],head[maxn];
int nex[maxn<<1],to[maxn<<1],val[maxn<<1];
void addedge(int u,int v,int w){
nex[++tot]=head[u];
head[u]=tot; to[tot]=v; val[tot]=w;
}
void dij(int s){
rep(i,1,n+1) dis[i]=1e9; dis[s]=0;
q.push({s,0}); while(!q.empty()){
int fr=q.top().id; q.pop();
if(vis[fr]) continue; vis[fr]++;
for(int j=head[fr];j;j=nex[j])
if(dis[to[j]]>val[j]+dis[fr]&&!vis[to[j]]){
dis[to[j]]=val[j]+dis[fr];
q.push({to[j],dis[to[j]]});
}
}
}

同余最短路

1
2
3
4
5
6
7
8
9
10
// n个数有Σai*xi=b b∈[b0,b1]
void slove(){
rep(i,0,a[0]-1) rep(j,0,n)
addedge(i,(i+a[j])%a[0],a[j]);
dij(0); rep(i,0,a[0]-1){
int t=dis[i];
if(t<b0) ans+=(b1-t)/a[0]-(b0-t-1)/a[0];
else if(t<=b1) ans+=(b1-t)/a[0]+1;
}
}

稳定婚姻问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int b[maxn][maxn],g[maxn][maxn];
// b 每个男生按好感位次排下来的女生
// g 每个女生对应每个男生的好感度
int bm[maxn],gm[maxn];
// 对应异性号数
int vis[maxn][maxn];
void stable_marriage(){
mst(bm,-1); mst(gm,-1); mst(vis,0);
queue<int> q;
rep(i,1,n+1) q.push(i);
int fr,nex;
while(!q.empty()){
fr=q.front(); q.pop();
rep(i,1,m+1){
nex=b[fr][i];
if(vis[fr][nex]) continue; vis[fr][nex]=1;
if(gm[nex]==-1){
gm[nex]=fr; bm[fr]=nex;
break;
}
else if(g[nex][gm[nex]]>g[nex][fr]){
q.push(gm[nex]);
gm[nex]=fr; bm[fr]=nex;
break;
}
}
}
}

二分匹配匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ans;
int mp[maxn][maxn];
int vis[maxn],line[maxn];
void init(){
ans=0; mst(mp,0); mst(line,0);
}
int dfs(int x){
rep(i,1,n+1) if(!vis[i]&&mp[i][x]){
vis[i]=1;
if(!line[i]||dfs(line[i])) {
line[i]=x; return 1;
}
} return 0;
}
void slove(){
rep(i,1,n+1){ mst(vis,0); if(dfs(i)) ans++; }
}

强连通tarjan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n,m,cnt,id;
int dfn[maxn],low[maxn];
int ins[maxn],scc[maxn];
stack<int>s;
vector<int>vv[maxn];
void init(){
cnt=id=0; rep(i,0,n+1){
vv[i].clear();
dfn[i]=low[i]=ins[i]=scc[i]=0;
}
}
void tarjan(int x){
dfn[x]=low[x]=++id; ins[x]=1; s.push(x);
rep(i,0,vv[x].size()){
int tmp=vv[x][i];
if(!dfn[tmp]){ tarjan(tmp); low[x]=min(low[x],low[tmp]); }
else if(ins[tmp]) low[x]=min(low[x],dfn[tmp]);
}
if(low[x]==dfn[x]){
int tmp; cnt++; do{
tmp=s.top(); s.pop();
ins[tmp]=0; scc[tmp]=cnt;
} while(x!=tmp);
}
}
void slove(){
rep(i,1,n+1) if(!dfn[i]) tarjan(i);
mst(ins,0); mst(out,0);
rep(i,1,n+1) rep(j,0,vv[i].size())
if(scc[i]!=scc[vv[i][j]]){
ins[scc[vv[i][j]]]++; out[scc[i]]++;
}
}

双连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 割点:这个点一旦被删除,这张图的连通块数量会增加
// 桥:这条边一旦被删除,这张图的连通块数量会增加
// 带*边双
int n,m,cnt,id,child;
int dfn[maxn],low[maxn],isc[maxn];
int num[maxn],ans,sum;
vector<int>vv[maxn];
//* vector<pii>bri;
void init(){
cnt=id=child=0; rep(i,0,n+1){
vv[i].clear();
dfn[i]=low[i]=isc[i]=0;
}
}
void tarjan(int x,int f){
dfn[x]=low[x]=++id; int ff(0);
rep(i,0,vv[x].size()){
int tmp=vv[x][i];
if(tmp==f&&!ff){ ff++; continue; } // 重边
if(!dfn[tmp]){
child++; tarjan(tmp,x);
low[x]=min(low[x],low[tmp]);
if(low[tmp]>dfn[x]){
isc[x]=1; // 判断这个点是否为割点
//* bri.push_back(pii(x,tmp));
}
} else if(dfn[tmp]<dfn[x]) low[x]=min(low[x],dfn[tmp]);
} if(f==-1&&child==1) isc[x]=0; // 关于根节点的特判
// 带缩点
if(dfn[x]==low[x]){
scc++; do...while...;
}
}
void slove(){
rep(i,1,n+1) if(!dfn[i]) tarjan(i,-1);
}

LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int n,m,tot,best[20][maxn<<1];
int dis[maxn],vis[maxn],head[maxn];
int nex[maxn<<1],to[maxn<<1],val[maxn<<1];
int id[maxn<<1],num[maxn],dep[maxn<<1],cnt;
void addedge(int u,int v,int w){
nex[++tot]=head[u];
head[u]=tot; to[tot]=v; val[tot]=w;
}
void dfs(int x,int f,int d){
id[++cnt]=x; num[x]=cnt; dep[cnt]=d;
for(int i=head[x];i;i=nex[i]){
int y=to[i],z=val[i]; if(y==f) continue;
dis[y]=dis[x]+z; dfs(y,x,d+1); id[++cnt]=x; dep[cnt]=d;
}
}
void ST(int n){
int lg=(int)(log(n*1.0)/log(2.0));
rep(i,1,n+1) best[0][i]=i;
rep(i,1,lg+1) for(int j=1;j+(1<<i)-1<=n;j++){
int t1=best[i-1][j],t2=best[i-1][j+(1<<i>>1)];
best[i][j]=dep[t1]<dep[t2]?t1:t2;
}
}
int RMQ(int x,int y){
if(x>y) swap(x,y);
int lg=(int)(log(1.0*(y-x+1))/log(2.0));
int t1=best[lg][x],t2=best[lg][y-(1<<lg)+1];
return dep[t1]<dep[t2]?t1:t2;
}
int LCA(int x,int y){
int t1=num[x],t2=num[y];
return id[RMQ(t1,t2)];
}
int getdis(int x,int y){
return dis[x]+dis[y]-2*dis[LCA(x,y)];
}
void slove(){
dfs(1,-1,1); ST(2*n-1);
}

数据结构

并查集

1
2
3
4
5
6
7
int find(int x){ 
return vis[x]==x?x:vis[x]=find(vis[x]);
}
void change(int x, int y){
int c=find(x),d=find(y);
if(c!=d) vis[c]=d;
}

树状数组

1
2
3
4
5
6
7
8
9
10
int tree[maxn];
int lowbit(int i){ return i&(-i); }
void update(int i,int x){
for(;i<=maxn;i+=lowbit(i)) tree[i]+=x;
}
int query(int n){
int ans=0;
for(int i=n;i>0;i-=lowbit(i)) ans+=tree[i];
return ans;
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 单点更新,加*区间更新
#define lson (rt<<1)
#define rson ((rt<<1)|1)
#define mid ((begin+end)>>1)
int segtree[4*maxn];
//* int lazy[4*maxn];
void pushup(int rt){
segtree[rt]=segtree[lson]+segtree[rson];
}
/** void pushdown(int rt,int begin,int end){
if (!lazy[rt]) return;
segtree[lson]+=(mid-begin+1)*lazy[rt];
segtree[rson]+=(end-mid)*lazy[rt];
lazy[lson]+=lazy[rt];
lazy[rson]+=lazy[rt];
lazy[rt]=0;
}*/
void build(int rt,int begin,int end){
//* lazy[rt]=0;
if(begin==end){ sc(segtree[rt]); return; }
build(lson,begin,mid);
build(rson,mid+1,end);
pushup(rt);
}
void update(int rt,int begin,int end,int pos,int a){
if(pos<begin||pos>end) return;
if(begin==end){ segtree[rt]+=a; return; }
update(lson,begin,mid,pos,a);
update(rson,mid+1,end,pos,a);
pushup(rt);
}
/** void update(int rt,int begin,int end,int left,int right,int a){
if(left>end||right<begin) return;
if(left<=begin&&right>=end){
segtree[rt]+=(end-begin+1)*a;
lazy[rt]+=a; return;
}
pushdown(rt,begin,end);
update(lson,begin,mid,left,right,a);
update(rson,mid+1,end,left,right,a);
pushup(rt);
}*/
int slove(int rt,int begin,int end,int left,int right){
if(left>end||right<begin) return 0;
if(left<=begin&&right>=end) return segtree[rt];
//* pushdown(rt,begin,end);
int ans=0;
ans+=slove(lson,begin,mid,left,right);
ans+=slove(rson,mid+1,end,left,right);
return ans;
}

DP

数位dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[20]; // 位数 一般题目最大1e18
ll dp[20][state];
ll dfs(int pos,int pre,/*int state,*/int limit){
// pos位数 pre之前状态 与dp数组对应
// state各种情况包括前导零 具体看题目 limit前一位限制
if(pos==-1) return 1; // 计数,具体看题目
if(!limit&&dp[pos][pre]!=-1/*&&!state*/) return dp[pos][pre];
int last=limit?a[pos]:9;
ll ans=0; rep(i,0,last+1){
if(...) ans+=dfs(pos-1,...,/*...,*/limit&&i==a[pos]);
else(...)
}
if(!limit/*&&!state*/) dp[pos][pre]=ans;
return ans;
}
ll slove(ll x){
mst(dp,-1);
// 多组数据只用最开始mst一次 因为保证边界就可以了
int pos=0;
while(x){ a[pos++]=x%10; x/=10; }
return dfs(pos-1,0,/*...,*/1);
}

数学

常见公式

1
2
// 1-n的平方和 n*(n+1)*(2*n+1)/6
// 1-n的立方和 n*n*(n+1)*(n+1)/4

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
ll qpow(ll a,ll b){
ll ans=1; for(;b>0;b>>=1){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
} return ans;
}
// 十进制ksm 大数幂次
ll qpow(ll a,char* s){
int len=strlen(s); ll res=1,q=1; dep(i,len-1,0){
rep(j,1,s[i]-'0'+1) res=res*a%mod;
a=a*a%mod; q=a*a%mod; q=q*q%mod; a=q*a%mod;
} return res;
}

快速乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll qmul(ll a,ll b,ll p){
a%=p; ll ans(0); while(b>0){
if(b&1) ans+=a; if(ans>=p) ans-=p;
b>>=1; a+=a; if(a>=p) a-=p;
} return ans;
} // olog
ll modMul(ll a,ll b,ll p){
if(p<=1000000000) return a*b%p;
else if(p<=1000000000000ll) return (((a*(b>>20)%p)<<20)+(a*(b&((1<<20)-1))))%p;
else{
ll d=(ll)floor(a*(long double)b/p+0.5);
ll ret=(a*b-d*p)%p; if (ret<0) ret+=p;
return ret;
}
} // o1

模逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
// exgcd
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1; y=0; return; }
exgcd(b,a%b,y,x); y-=(a/b)*x; return;
}
ll inv(ll a,ll p){
ll x,y; exgcd(a,p,x,y);
return (x%p+p)%p;
} // 好像比ksm快的
// qpow
inv=qpow(a,mod-2,mod);
// 递推
inv[i]=(mod-mod/i)*inv[mod%i]%mod;

组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 预处理写法
int jc[maxn],inv[maxn];
void init(){
jc[0]=inv[0]=1; rep(i,1,maxn) jc[i]=1ll*jc[i-1]*i%mod;
inv[maxn-1]=qpow(jc[maxn-1],mod-2,mod);
dep(i,maxn-2,1) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int C(int s,int x){
return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod;
}
// lucas
ll Lucas(ll n,ll m,ll p){
ll ans=1;
while(n|m) ans=ans*C(n%p,m%p)%p,n/=p,m/=p;
return ans;
}

素数判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool isPrime(ll n){
if(n==2||n==3||n==5) return 1;
if(n%2==0||n%3==0||n%5==0||n==1) return 0;
ll c=7,a[8]={4,2,4,2,4,6,2,6};
while(c*c<=n) for(auto i:a){ if(n%c==0) return 0; c+=i; }
return 1;
} // 抠
// n极大时素数测试算法
ll Rand(){
static ll x=(srand((int)time(0)),rand());
x+=1000003; if(x>mod) x-=mod; return x;
}
bool Witness(ll a,ll n){
ll t=0,u=n-1;
while(!(u&1)) u>>=1,t++;
ll x=fpow(a,u,n),y;
while(t--){
y=x*x%n;
if(y==1&&x!=1&&x!=n-1) return true;
x=y;
} return x!=1;
}
bool MillerRabin(ll n,ll s){
if(n==2||n==3||n==5) return 1;
if(n%2==0||n%3==0||n%5==0||n==1) return 0;
while(s--) if(Witness(Rand()%(n-1)+1,n)) return false;
return true;
}

求最小素因数

1
2
3
4
5
6
7
8
9
int p[maxn/3],mpf[maxn],pn;
void init(){
int tmp; rep(i,2,maxn){
if(!mpf[i]) p[pn++]=i,mpf[i]=i;
for(int j=0;(tmp=i*p[j])<maxn;j++){
mpf[tmp]=p[j]; if(!(i%p[j])) break;
}
}
}

Pollard’s rho

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 对于比较大的数分解因数
typedef pair<ll,int> pli;
namespace pollard_rho{
const int C=2307;
const int S=10;
mt19937 rd(time(0));
vector<ll>ve;
ll gcd(ll a,ll b){ while((a%=b)&&(b%=a)); return a+b; }
ll mul(ll a,ll b,ll mod){ return (__int128)a*b%mod; }
ll qpow(ll a,ll b,ll mod){
ll res=1; a%=mod;
while(b>0){
if(b&1) res=mul(res,a,mod);
b>>=1; a=mul(a,a,mod);
} return res;
}
bool check(ll a,ll n){
ll m=n-1,x,y; int j=0;
while(!(m&1))m>>=1,j++;
x=qpow(a,m,n);
for(int i=1;i<=j;x=y,i++){
y=mul(x,x,n);
if(y==1&&x!=1&&x!=n-1) return 1;
} return y!=1;
}
bool miller_rabin(ll n){
ll a;
if(n==1) return 0;
if(n==2) return 1;
if(!(n&1)) return 0;
for(int i=0;i<S;i++) if(check(rd()%(n-1)+1,n)) return 0;
return 1;
}
ll pollard_rho(ll n,int c){
ll i=1,k=2,x=rd()%n,y=x,d;
while(1){
i++; x=(mul(x,x,n)+c)%n,d=gcd(y-x,n);
if(d>1&&d<n) return d;
if(y==x) return n;
if(i==k) y=x,k<<=1;
}
}
void findfac(ll n,int c){
if(n==1) return;
if(miller_rabin(n)){
ve.push_back(n);
return;
} ll m=n;
while(m==n) m=pollard_rho(n,c--);
findfac(m,c);
findfac(n/m,c);
}
vector<pli> solve(ll n){
vector<pli>res;
ve.clear();
findfac(n,C);
sort(ve.begin(),ve.end());
for(auto x:ve){
if(res.empty()||res.back().first!=x) res.push_back({x,1});
else res.back().second++;
} return res;
}
}

中国剩余定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll a[maxn],r[maxn];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1; y=0; return a; }
else{
ll ans=exgcd(b,a%b,y,x);
y-=(a/b)*x; return ans;
}
}
int excrt(){
ll m1,r1,m2,r2;
ll x,y,t,c,d;
m1=a[0],r1=r[0];
rep(i,1,tot){
m2=a[i],r2=r[i];
c=r2-r1; d=exgcd(m1,m2,x,y);
if(c%d) return puts("-1");
t=m2/d; x*=c/d; x=(x%t+t)%t;
r1=x*m1+r1; m1=m1*m2/d;
r1=(r1%m1+m1)%m1;
} return pf("%d\n",r1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 大数版
import java.math.*;
import java.util.*;
public class Main {
public static BigInteger[] exgcd(BigInteger a,BigInteger b){
BigInteger ans;
BigInteger[] result=new BigInteger[3];
if(b.compareTo(BigInteger.ZERO)==0){
result[0]=a; result[1]=BigInteger.ONE; result[2]=BigInteger.ZERO;
return result;
}
BigInteger[] tmp=exgcd(b,a.mod(b));
ans=tmp[0]; result[0]=ans; result[1]=tmp[2];
result[2]=tmp[1].subtract((a.divide(b).multiply(tmp[2])));
return result;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
BigInteger a[]=new BigInteger[105];
BigInteger r[]=new BigInteger[105];
int n; n=sc.nextInt();
for(int i=0;i<n;i++){
a[i]=sc.nextBigInteger();
r[i]=sc.nextBigInteger();
}
BigInteger m1,m2,r1,r2,t,c;
BigInteger[] d;
m1=a[0]; r1=r[0];
for(int i=1;i<n;i++){
m2=a[i]; r2=r[i]; c=r2.subtract(r1); d=exgcd(m1,m2);
if(c.mod(d[0]).compareTo(BigInteger.ZERO)!=0){
System.out.println("-1");
return;
}
t=m2.divide(d[0]); d[1]=d[1].multiply(c.divide(d[0])).mod(t);
r1=d[1].multiply(m1).add(r1); m1=m1.multiply(t);
r1=r1.mod(m1);
}
d=exgcd(BigInteger.ONE,m1);
if(r1.mod(d[0]).compareTo(BigInteger.ZERO)!=0){
System.out.println("-1");
return;
}
t=m1.divide(d[0]); d[1]=d[1].multiply(r1.divide(d[0])).mod(t);
System.out.println(d[1]);
}
}

(ex)bsgs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 求解a^x=b(mod p)
ll bsgs(ll a,ll b,ll p){
unordered_map<ll,ll>tab; tab.clear();
ll u=(ll)ceil(sqrt(p)),ans;
rep(i,0,u+1){
if(!i) ans=b%p,tab[ans]=i;
else ans=ans*a%p,tab[ans]=i;
} ll sum=qpow(a,u,p); ans=1;
if(!sum) return b?-1:1;
rep(i,1,u+1){
ans=ans*sum%p;
if(tab[ans]) return u*i-tab[ans];
} return -1;
}

打表素数及莫比乌斯函数

1
2
3
4
5
6
7
8
9
10
11
int p[maxn],u[maxn],vis[maxn],pn;
void init(){
u[1]=1; rep(i,2,maxn){
if(!vis[i]) p[pn++]=i,u[i]=-1;
for(int j=0;j<pn&&i*p[j]<maxn;j++){
vis[i*p[j]]=1;
if(i%p[j]) u[i*p[j]]=-u[i];
else { u[i*p[j]]=0; break; }
}
}
}

反素数

1
2
3
4
5
6
7
8
9
10
11
12
int n,p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll ans=1e18; // n个因数
void dfs(int pos,ll v,int num){
if(num>n||pos>15) return;
if(num==n) return ans=min(ans,v),(void)0;
for(int i=1;i<64;i++){
if(v>ans/p[pos]||num*(i+1)>n) break; v*=p[pos];
if(!(n%(num*(i+1)))) dfs(pos+1,v,num*(i+1));
}
}
void slove(){ dfs(0,1,1); }
// ans是因数有n个的最小正整数

欧拉函数

1
2
3
4
5
6
7
8
9
10
ll getphi(ll x){
ll res=x; rep(i,2,x+1){
if(1ll*i*i>x) break;
if(x%i==0){
res=res/i*(i-1);
while(x%i==0) x/=i;
}
} if(x>1) res=res/x*(x-1);
return res;
}

欧拉降幂

1
2
3
4
// 求qpow(a,b,p)有
if(__gcd(a,p)==1) ans=qpow(a,b%phi(p),p);
else if(__gcd(a,p)>1&&b<phi(p)) ans==qpow(a,b,p);
else ans=qpow(a,b%phi(p)+phi(p),p);

BM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
namespace linear_seq{
const int N=101100;
ll res[N],base[N],_c[N],_md[N];
vector<int>Md;
void mul(ll *a,ll *b,int k){
rep(i,0,k+k) _c[i]=0;
rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
for (int i=k+k-1;i>=k;i--) if(_c[i])
rep(j,0,Md.size()) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
rep(i,0,k) a[i]=_c[i];
}
int slove(ll n,vector<int> a,vector<int> b){
// a系数 b初值 b[n+1]=a[0]*b[n]+...
ll ans=0,pnt=0; int k=a.size();
assert((int)a.size()==(int)b.size()); Md.clear();
rep(i,0,k) _md[k-1-i]=-a[i]; _md[k]=1;
rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
rep(i,0,k) res[i]=base[i]=0; res[0]=1;
while((1ll<<pnt)<=n) pnt++; dep(p,pnt,0){
mul(res,res,k); if((n>>p)&1){
dep(i,k-1,0) res[i+1]=res[i];res[0]=0;
rep(j,0,Md.size()) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
} rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
if(ans<0) ans+=mod; return ans;
}
vector<int> BM(vector<int> s){
vector<int> C(1,1),B(1,1);
int L=0,m=1,b=1;
rep(n,0,s.size()){
ll d=0; rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
if(d==0) ++m; else if(2*L<=n){
vector<int> T=C;
ll c=mod-d*qpow(b,mod-2)%mod;
while((int)C.size()<(int)B.size()+m) C.push_back(0);
rep(i,0,B.size()) C[i+m]=(C[i+m]+c*B[i])%mod;
L=n+1-L; B=T; b=d; m=1;
} else{
ll c=mod-d*qpow(b,mod-2)%mod;
while((int)C.size()<(int)B.size()+m) C.push_back(0);
rep(i,0,B.size()) C[i+m]=(C[i+m]+c*B[i])%mod;
++m;
}
} return C;
}
int qaq(vector<int> a,ll n){
vector<int> c=BM(a); c.erase(c.begin());
rep(i,0,c.size()) c[i]=(mod-c[i])%mod;
return slove(n,c,vector<int>(a.begin(),a.begin()+(int)c.size()));
}
};
int slove(){
vector<int>vv; ll tmp(0); rep(i,1,maxn){
tmp=...; vv.push_back(tmp);
} ll ans=linear_seq::qaq(vv,n-1);
return printf("%lld\n",ans);
}

二次剩余

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool judge(ll a,ll p){
// 判断a是否为p的二次剩余 p是素数
return qpow(a,(p-1)>>1,p)==1;
}
ll Shanks(ll a,ll p){
// 求解二次同余方程x^2=a(mod p) p是素数
if(a==0) return 0;
ll q=p-1,e=0;
while(!(q&1)) q>>=1,e++;
static mt19937_64 rd(time(0));
ll n=rd()%(p-1)+1;
// 随机选取p的一个非二次剩余,若p为定值,n也可为定值
while(judge(n,p)) n=rd()%(p-1)+1;
ll z=qpow(n,q,p),y=z,r=e,x=qpow(a,(q-1)>>1,p),b=a*x%p*x%p;
x=a*x%p; while(b!=1){
ll temp=b*b%p,m=1;
while(temp!=1) (temp*=temp)%=p,m++;
if(m==r) return -1;
ll t=y; rep(i,1,r-m-1)(t*=t)%=p;
y=t*t%p,r=m%p,x=x*t%p,b=b*y%p;
} return x;
}

fft

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef complex<double> cd;
const double PI = acos(-1.0);
void change(cd* f,int n){
int j=n>>1; rep(i,1,n-1){
if(i<j) swap(f[i],f[j]);
int k=n>>1; while(j>=k){
j-=k; k>>=1;
} if(j<k) j+=k;
}
}
void fft(cd* f,int n,int dft){ // n为多项式位数
change(f,n);
for(int step=1;step<n;step<<=1){ // 合并
cd wn=exp(cd(0,dft*PI/step));
for(int j=0;j<n;j+=step<<1){
cd wnk(1,0);
for(int k=j;k<j+step;k++){
cd x=f[k],y=wnk*f[k+step];
f[k]=x+y; // F(x)=G(x)+ωH(x)
f[k+step]=x-y;
wnk*=wn;
}
}
} if(dft==-1) rep(i,0,n) f[i]/=n;
// IDFT需要整个矩阵的内容乘上1/n
}
cd a[maxn],b[maxn]; int ans[maxn];
void slove(){
int mx=...,L=1; while(L<mx*2) L<<=1;
mst(ans,0); fft(a,L,1); fft(b,L,1);
rep(i,0,L) a[i]=a[i]*b[i]; fft(a,L,-1);
rep(i,0,L) ans[i]=(int)(a[i].real()+0.5);
}

fwt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void fwt_or(int *a,int op){
for(int i=1;i<N;i<<=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;++k)
if(op==1) a[i+j+k]=(a[j+k]+a[i+j+k])%mod;
else a[i+j+k]=(a[i+j+K]-a[j+K]+mod)%mod;
}
void fwt_and(int *a,int op){
for(int i=1;i<N;i<<=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;++k)
if(op==1) a[j+k]=(a[j+k]+a[i+j+k])%mod;
else a[j+k]=(a[j+K]-a[i+j+K]+mod)%mod;
}
void fwt_xor(int *a,int op){
for(int i=1;i<N;i<<=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;++k){
int x=a[j+k],y=a[i+j+k];
a[j+k]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
if(op==-1) a[j+k]=1ll*a[j+k]*inv2%mod,
a[i+j+k]=1ll*a[i+j+k]*inv2%mod;
}
}

拉格朗日插值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
namespace polysum{
const int D = 1e5 + 5;
ll a[D],f[D],g[D],p1[D],p2[D],b[D],h[D][2],C[D];
ll qpow(ll a,ll b){
ll ans=1; for(;b;b>>=1){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
} return ans;
}
void init(int M){
f[0]=f[1]=g[0]=g[1]=1;
rep(i,2,M+5) f[i]=f[i-1]*i%mod;
g[M+4]=qpow(f[M+4],mod-2);
dep(i,M+3,2) g[i]=g[i+1]*(i+1)%mod;
}
// 已知f(0),f(1)..f(d) 求 f(n)
ll calcn(ll d,ll *a,ll n){ // a[0].. a[d] a[n]
if(n<=d) return a[n];
p1[0]=p2[0]=1;
rep(i,0,d+1){
ll t=(n-i+mod)%mod;
p1[i+1]=p1[i]*t%mod;
}
rep(i,0,d+1){
ll t=(n-d+i+mod)%mod;
p2[i+1]=p2[i]*t%mod;
}
ll ans(0);
rep(i,0,d+1){
ll t=g[i]*g[d-i]%mod*p1[i]%mod*p2[d-i]%mod*a[i]%mod;
if((d-i)&1) ans=(ans-t+mod)%mod;
else ans=(ans+t)%mod;
} return ans;
}
// 已知 f(0),f(1)...f(m),求\sum_{i=0 }^{n} f[i]
ll polysum(ll m,ll *a,ll n){ // a[0].. a[m]
ll b[D];
rep(i,0,m+1) b[i]=a[i];
b[m+1]=calcn(m,b,m+1);
rep(i,1,m+2) b[i]=(b[i-1]+b[i])%mod;
return calcn(m+1,b,n-1);
}
// a[0].. a[m] \sum_{i=0}^{n-1} a[i]*R^i
ll qpolysum(ll R,ll n,ll *a,ll m) {
if(R==1) return polysum(n,a,m);
a[m+1]=calcn(m,a,m+1);
ll r=qpow(R,mod-2),p3=0,p4=0,c,ans;
h[0][0]=0; h[0][1]=1;
rep(i,1,m+2){
h[i][0]=(h[i-1][0]+a[i-1])*r%mod;
h[i][1]=h[i-1][1]*r%mod;
}
rep(i,0,m+2){
ll t=g[i]*g[m+1-i]%mod;
if(i&1) p3=((p3-h[i][0]*t)%mod+mod)%mod,p4=((p4-h[i][1]*t)%mod+mod)%mod;
else p3=(p3+h[i][0]*t)%mod,p4=(p4+h[i][1]*t)%mod;
}
c=qpow(p4,mod-2)*(mod-p3)%mod;
rep(i,0,m+2) h[i][0]=(h[i][0]+h[i][1]*c)%mod;
rep(i,0,m+2) C[i]=h[i][0];
ans=(calcn(m,C,n)*qpow(R,n)%mod-c)%mod;
if(ans<0) ans+=mod;
return ans;
}
}

博弈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* 巴什博弈:一堆物品n两人轮流取物,一次最多m
根据n%(m+1)是否为零判断胜者 */
/* 威佐夫博奕:两堆物品a、b两人轮流取物,一次只能在一堆任意取或是两堆取同样多 //默认a<b
根据(int)((double)(1.0+sqrt(4.0))/2.0)*(b-a))是否等于a判断胜者
扩展威佐夫博弈:两堆物品a、b两人轮流取物,一次只能在一堆任意取或是两堆取相差不超过k的 //默认a<b */
if(a>b) swap(a,b);
if(a==1) return puts(b==k+2?"0":"1");
if(a==k+2||b==k+2) return puts("1");
ll r=(b-a)%(k+1); if(r) return puts("1");
double t=(1.0-k+sqrt(1ll*(k+1)*(k+1)+4.0))/2.0;
ll q=(b-a)/(k+1); q=(ll)q*t;
return puts(q==a?"0":"1");
/* Fibonacci博弈:一堆物品n,两人轮流取物,每一次能取的个数是上一次的两倍以内,最后取完胜
n为Fibonacci数时先手败 */
// k倍动态减法
// 一堆石头 第一步可以拿1~n-1个石头 之后每步最多拿上一步的k倍
int a[maxn],b[maxn];
int slove(){
int n,k; sc(n); sc(k); a[0]=b[0]=1;
int i=0,j=0; while(n>a[i]){
i++; a[i]=b[i-1]+1;
while(a[j+1]*k<a[i]) j++;
if(a[j]*k<a[i]) b[i]=b[j]+a[i];
else b[i]=a[i];
} if(a[i]==n) return puts("lose"); // 先手败
int ans; while(n){
if(n>=a[i]) n-=a[i],ans=a[i]; i--;
} return pf("%d\n",ans); // 第一步所拿最少数
}

斐波那契求循环节

1
2
3
4
5
6
7
/*
给定一个数n 求%n的斐波那契循坏节长度len
·n为质数且5是模n的二次剩余 len为(n-1)的因子
·n为质数且5不为模n的二次剩余 len为(2n+2)的因子
·n为质数p的k次 len为lenp*p^(k-1)
·n分解为质因数 len为每个质因数循环节长度的lcm
*/

计算几何

二维几何

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// 一般形式
// 直线L上两点(x1,y1),(x2,y2);
// 直线外一点P(x0,y0);
// L表示为Ax+By+C=0;
double A,B,C;
A=y2-y1; B=x1-x2; C=x2*y1-x1*y2;
// 点到直线距离d
double d=fabs(A*x0+B*y0+C)/sqrt(A*A+B*B);
// 点到直线垂足H(x, y)
double x,y;
x=(B*B*x0-A*B*y0-A*C)/(A*A+B*B);
y=(-A*B*x0+A*A*y0-B*C)/(A*A+B*B);
// 点关于直线的对称点P'(_x, _y);
double k,_x,_y;
k=-2*(A*x0+B*y0+C)/(A*A+B*B); _x=x0+k*A; _y=y0+k*B;
// 求三角形内整数点个数
// 三角形三个顶点坐标(x1, y1), (x2, y2), (x3, y3) 都为整数点
int t1,t2,t3; // 三边上整数点个数
t1=gcd(abs(x1-x2),abs(y1-y2));
t2=gcd(abs(x3-x2),abs(y3-y2));
t3=gcd(abs(x1-x3),abs(y1-y3));
int num; // 三角形内整数点
num=abs((x2-x1)*(y3-y2)-(x3-x2)*(y2-y1))/2;
num-=(t1+t2+t3)/2-1;
// 皮克定理
// 一个格点多边形有 S=a+b/2-1;
// S面积 a内部格点数 b边上格点数

// 结构体形式
struct point{
double x,y;
point(double _x=0,double _y=0){ x=_x,y=_y; }
point operator+ (const point& a) const{ return point(x+a.x,y+a.y); }
point operator- (const point& a) const{ return point(x-a.x,y-a.y); }
point operator* (double a) const{ return point(x*a,y*a); }
}; // 点
struct line{
point s,e;
line(point a,point b){ s=a,e=b; }
line(){}
}; // 线
int dcmp(double x){
if(x>eps) return 1; return x<-eps?-1:0;
}
double getdis(point a, point b){
double xx=a.x-b.x,yy=a.y-b.y;
return sqrt(xx*xx+yy*yy);
} // 两点距离
double multi(point a,point b,point c){
double xa,ya,xb,yb;
xa=b.x-a.x; ya=b.y-a.y;
xb=c.x-b.x; yb=c.y-b.y;
return xa*xb+ya*yb;
} // 点乘
double cross(point a,point b,point c){
double xa,ya,xb,yb;
xa=b.x-a.x; ya=b.y-a.y;
xb=c.x-a.x; yb=c.y-a.y;
return xa*yb-xb*ya;
} // 叉乘
int judgec(line a,line b){
if (max(a.s.x,a.e.x)>=min(b.s.x,b.e.x) &&
max(a.s.y,a.e.y)>=min(b.s.y,b.e.y) &&
max(b.s.x,b.e.x)>=min(a.s.x,a.e.x) &&
max(b.s.y,b.e.y)>=min(a.s.y,a.e.y) &&
cross(a.s,b.s,b.e)*cross(a.e,b.s,b.e)<=0
&& cross(b.s,a.s,a.e)*cross(b.e,a.s,a.e)<=0
) return 1;
else return 0;
} // 判断线段是否相交
point getpoi(point a,point b,point c,point d){
double u=cross(a,b,c),v=cross(b,a,d);
return point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));
} // 求交点
double parea(point p[],int n){
if(n<3) return 0;
double ans=0; p[n]=p[0];
rep(i,0,n) ans+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
return ans/2;
} // 多边形面积
// 求两个多边形面积交/并
double CPIA(point a[],point b[],int n1,int n2){
if(n2<3) return 0;
point p[15],t[15];
a[n1]=a[0]; b[n2]=b[0];
memcpy(p,b,sizeof(point)*(n2+1));
rep(i,0,n1){
int f1=dcmp(cross(a[i],a[i+1],p[0])),tn=0;
rep(j,0,n2){
if(f1>=0) t[tn++]=p[j];
int f2=dcmp(cross(a[i],a[i+1],p[j+1]));
if((f1^f2)==-2) t[tn++]=getpoi(a[i],a[i+1],p[j],p[j+1]);
f1=f2;
} memcpy(p,t,sizeof(point)*tn);
n2=tn; p[n2]=p[0];
} return parea(p,n2);
}
double SPIA(point a[],point b[],int n1,int n2){
point t1[5],t2[5]; a[n1]=t1[0]=a[0]; b[n2]=t2[0]=b[0];
double res=0; rep(i,2,n1){
t1[1]=a[i-1]; t1[2]=a[i]; int f1=dcmp(cross(t1[0],t1[1],t1[2]));
if(f1<0) swap(t1[1],t1[2]); rep(j,2,n2){
t2[1]=b[j-1]; t2[2]=b[j]; int f2=dcmp(cross(t2[0],t2[1],t2[2]));
if(f2<0) swap(t2[1],t2[2]); res+=CPIA(t1,t2,3,3)*f1*f2;
}
} return fabs(res); //面积交
//return fabs(parea(a,n1)+parea(b,n2)-res); //面积并
}
double gx, gy;
void find_gra(){
double area=0,tmp;
rep(i,1,n-1){
tmp=(p[i].x-p[0].x)*(p[i+1].y-p[0].y)-(p[i+1].x-p[0].x)*(p[i].y-p[0].y); area+=tmp;
gx+=(p[0].x+p[i].x+p[i+1].x)*tmp;
gy+=(p[0].y+p[i].y+p[i+1].y)*tmp;
} gx=gx/3/area, gy=gy/3/area;
} // 求重心坐标

二维凸包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 以下凸包Graham
int top;
point p[maxn],s[maxn];
int iszero(double x){ return fabs(x)<eps; }
int cmp(point a,point b){
double tt=multi(a,b,p[0]);
if(tt>0||iszero(tt)&&getdis(a,p[0])<getdis(b,p[0])) return 1;
return 0;
}
void graham() {
point tmp;
rep(i,1,n) if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x)) swap(p[0],p[i]);
sort(p+1,p+n,cmp);
s[0]=p[0]; s[1]=p[1]; s[2]=p[2]; top=2;
rep(i,3,n){
while(top>=2&&multi(s[top-1],s[top],p[i])<=eps) top--;
s[++top]=p[i];
}
}

Java

快读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// 这句是io流包装,记住就好
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
/*in.resetSyntax();
in.whitespaceChars(0, 32);
in.wordChars('0', '9');
in.wordChars('-', '.');
in.wordChars('+', '+');
in.wordChars('a', 'z');
in.wordChars('A', 'Z');
in.wordChars(0xa0, 0xff);
in.slashSlashComments(true);
in.slashStarComments(true);
in.quoteChar('"');
in.quoteChar('\'');*/
// 以上加上可以将数字当字符串读
// StreamTokenizer.TT_EOF这个是个参数,就是EOF
while (in.nextToken() != StreamTokenizer.TT_EOF) {
String n = in.sval;
in.nextToken(); // 没记错是换行
double m = in.nval;
int a = (int) in.nval;
out.println(m);
out.flush(); // 刷新,不然max会留在缓冲区
}
}
}

高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in); // 普通读入
while(sc.hasNext()){
// 大数常见函数
BigInteger.valueOf(); // int转大数
BigInteger a = new BigInteger(/*val:*/"");
BigInteger b = new BigInteger(/*String*/);
BigInteger array[]=new BigInteger[maxn];
add(); subtract(); multiply(); divide();
compareTo(); mod(); pow(); gcd(); // 理论上大部分有补全的
System.out.println(a.stripTrailingZeros().toPlainString()); // 实数的输出去除末尾0
Arrays.sort(a,0,n); // 数组排序
}
}
}

其他

各种函数

1
2
3
4
5
is_sorted(a+l,a+r); // 判断数组a在区间是否有序
__builtin_popcount(x); // 计算二进制x有几个1
__builtin_popcountll(x); // ll模式 末尾加个ll
prev_permutation(iterator strat,iterator end);
next_permutation(iterator strat,iterator end);

pbds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 平衡树
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
tree</*int*/,null_type,greater</*int*/>,rb_tree_tag,tree_order_statistics_node_update> T;
// 第一个参数是数据类型
// 第二个要填null_type,低版本编译器填null_mapped_type
// 第三个填比较函数 std::greater<> or std::less<> or cmp
// 第四个填树的类型,有rb_tree_tag红黑树和splay_tree_tag
// 第五个是为了支持查询第k大和排名的一个参数
T.insert(x); T.erase(x); T.lower_bound(x);
int rk=(int)T.order_of_key(x)+1; // 查询一个数的排名
int num=(int)*T.find_by_order(x-1)); //查询第k大的数 返回迭代器
// rope
#include<ext/rope>
using namespace __gnu_cxx;
rope</*int*/>r;
r.push_back(x); // 在末尾添加x
r.insert(pos,x); // 在pos插入x,自然支持整个char数组的一次插入
r.erase(pos,x); // 从pos开始删除x个
r.copy(pos,len,x); // 从pos开始到pos+len为止用x代替
r.replace(pos,x); // 从pos开始换成x
r.substr(pos,x); // 提取pos开始x个

指令集优化

1
2
3
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

关同步

1
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

快读

1
2
3
4
5
6
inline int read(){
int x=0,w=0;char ch=getchar();
while (!isdigit(ch)) w|=ch=='-',ch=getchar();
while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return w?-x:x;
}

__int128输入输出

1
2
3
4
5
6
7
8
9
10
11
void scan(__int128 &x){
x=0; int op=1; char c=getchar();
while(c<'0'||c>'9') op=(c=='-'?-1:1),c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
x*=op;
}
void print(__int128 x){
if(x<0){ x=-x; putchar('-'); }
if(x>9) print(x/10);
putchar(x%10+'0');
}

随机

1
2
mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count());
int rnd(int x){ return mrand()%x; }

给逆元求概率

1
2
3
4
5
6
7
8
9
10
11
12
void slove(ll pa,ll xa,ll pb,ll xb,ll &a,ll &b){
ll tmp=(pa-1)/xa;
if(tmp+1<=pb/xb){ a=tmp+1; b=1; return; }
pa-=tmp*xa; pb-=tmp*xb;
slove(xb,pb,xa,pa,b,a); a+=tmp*b;
}
void getsample(){
ll p,x,a,b; scl(p); scl(x);
// p模的质数 x结果
slove(p,x,p,x-1,a,b);
ll c=x*a-p*b; pf("%lld/%lld\n",c,a);
}