ACM模板-稳赚个人版

w 本文总阅读量次

稳赚又丑又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);
}
w