个人模板整理

Diposting di | Edited on

数据结构

字符串处理

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
38
39
40
41
42
43
44
45
46
/*
* next[] 的含义：x[i-next[i]...i-1]=x[0...next[i]-1] 
* next[i] 为满足 x[i-z...i-1]=x[0...z-1] 的最大 z 值（就是 x 的自身匹配）
*/ 
void kmp_pre(char x[],int m,int next[]){
    int i,j;
    j=next[0]=-1;
    i=0;
    while(i<m){
        while(-1!=j&&x[i]!=x[j])j=next[j];
        next[++i]=++j;
    }
}
/* 
 * kmpNext[i] 的意思:next'[i]=next[next[...[next[i]]]](直到 next'[i]<0 或者 x[next'[i]]!=x[i])
 * 这样的预处理可以快一些 
 */ 
void preKmp(char x[],int m,int kmpNext[]){
    int i,j;
    j=kmpNext[0]=-1;
    i=0;
    while(i<m){
        while(-1!=j && x[i]!=x[j])j=kmpNext[j];
        if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];
        else kmpNext[i]=j;
    }
}
/*
返回x 在 y 中出现的次数，可以重叠
*/
int mynext[maxn];
int kmp(char x[],int m,char y[],int n){ // x是模式串 ，y是主串
    int i,j;
    int ans=0;
    kmp_pre(x,m,mynext);
    i=j=0;
    while(i<n){
        while(-1!=j&&y[i]!=y[j])j=mynext[j];
        i++;j++;
        if(j>=m){
            ans++;
            j=mynext[j];
        }
    }
    return ans;
}

e-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
38
39
40
/*
 * 扩展KMP算法
 */
// next[i]:x[i...m-1] 与x[0...m-1]的最长公共前缀
void pre_EKMP(char x[],int m,int next[]){
    next[0]=m;
    int j=0;
    while(j+1<m && x[j] == x[j+1])j++;
    next[1]=j;
    int k=1;
    for(int i=2;i<m;i++){
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L < p+1)next[i]=L;
        else{
            j=max(0,p-i+1);
            while( i+j < m && x[i+j] == x[j])j++;
            next[i]=j;
            k=i;
        }
    }
}
void EKMP(char x[],int m,int y[],int n,int next[],int extend[]){
    pre_EKMP(x,m,next);
    int j=0;
    while(j < n && j < m && x[j] == y[j])j++;
    extend[0]=j;
    int k=0;
    for(int i = 1;i < n;i++){
        int p = extend[k]+k-1;
        int L=next[i-k];
        if(i+L < p+1)extend[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j < n && j < m && y[i+j] == x[j])j++;
            extend[i]=j;
            k=i;
        }
    }
}

Z-算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//求每个位置匹配前缀的长度的最大值  s[0…z[i]-1]=s[i…i+z[i]-1]
vector<int> ZF(const string &s){
    vector<int>z(s.size());
    int l=0,r=1;
    for(int i=1;i<(int)s.size();i++){
        if(r>i)z[i]=min(z[i-l],r-i);
        if(z[i]+i>=r){
            l=i,r=z[i]+i;
            while(r<(int)s.size()&&s[r]==s[r-l])r++;
            z[i]=r-l;
        }
    }
    return z;
}

最大最小表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getminmax(bool flag,string s){
    int i=0,j=1,k=0;
    int len=s.length();
    while(i<len&&j<len&&k<len){
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(t==0)k++;
        else{
            if(!flag){
                if(t>0)i=i+k+1;
                else   j=j+k+1;
            }
            else{
                if(t>0)j=j+k+1;
                else   i=i+k+1;
            }
            if(i==j)j++;
            k=0;
        }
    }
    return i<j?i:j;
}

Manacher

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
char Ma[maxn*2];
int Mp[maxn*2]; ///需要-1才是最长回文的长度
int Manacher(char s[],int len){
    int l=0,ans=0;
    Ma[l++]='$';
    Ma[l++]='#';
    for(int i=0;i<len;i++){
        Ma[l++]=s[i];
        Ma[l++]='#';
    }
    Ma[l]=0;
    int mx=0,id=0;
    for(int i=0;i<l;i++){
        Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;
        if(i+Mp[i]>mx){
            mx=i+Mp[i];
            id=i;
        }
        ans+=Mp[i]/2;
    }
    return ans;///计算共有多少回文串
}
/* 
 * abaaba
 * i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 
 * Ma[i]: $ # a # b # a # a # b # a # 
 * Mp[i]: 1 1 2 1 4 1 2 7 2 1 4 1 2 1 
 */

Manacher返回最长回文串

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
string Manacher(string s) {
    // Insert '#'
    string t = "$#";
    for (int i = 0; i < s.size(); ++i) {
        t += s[i];
        t += "#";
    }
    int mx=0;
    // Process t
    vector<int> p(t.size(), 0);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    for (int i = 1; i < t.size(); ++i) {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
        while (t[i + p[i]] == t[i - p[i]]) ++p[i];
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }
        mx=max(mx,p[i]);
    }
    cout<<mx-1<<endl;
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef unsigned long long ull;
const ull Seed_Pool[] = {146527, 19260817};
const ull Mod_Pool[] = {1000000009, 998244353};
struct Hash
{
    ull SEED, MOD;
    vector<ull> p, h;
    Hash() {}
    Hash(const string& s, const int& seed_index, const int& mod_index)
    {
        SEED = Seed_Pool[seed_index];
        MOD = Mod_Pool[mod_index]; 
        int n = s.length();
        p.resize(n + 1), h.resize(n + 1);
        p[0] = 1;
        for (int i = 1; i <= n; i++) p[i] = p[i - 1] * SEED % MOD;
        for (int i = 1; i <= n; i++) h[i] = (h[i - 1] * SEED % MOD + s[i - 1]) % MOD;
    }
    ull get(int l, int r) { return (h[r] - h[l] * p[r - l] % MOD + MOD) % MOD; }
    ull substr(int l, int m) { return get(l, l + m); }
};

回文树

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
const int MAXN = 100005 ;  
const int N = 26 ;  

struct Palindromic_Tree {  
    //cnt最后count一下之后是那个节点代表的回文串出现的次数
    int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成  
    int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点  
    int cnt[MAXN] ; //表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的） 
    int num[MAXN] ; //表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数
    int len[MAXN] ;//len[i]表示节点i表示的回文串的长度（一个节点表示一个回文串）
    int S[MAXN] ;//存放添加的字符  
    int last ;//指向新添加一个字母后所形成的最长回文串表示的节点。
    int n ;//表示添加的字符个数。
    int p ;//表示添加的节点个数。

    int newnode ( int l ) {//新建节点  
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;  
        cnt[p] = 0 ;  
        num[p] = 0 ;  
        len[p] = l ;  
        return p ++ ;  
    }  

    void init () {//初始化  
        p = 0 ;  
        newnode (  0 ) ;  
        newnode ( -1 ) ;  
        last = 0 ;  
        n = 0 ;  
        S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判  
        fail[0] = 1 ;  
    }  

    int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的  
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;  
        return x ;  
    }  

    void add ( int c ) {  
        c -= 'a' ;  
        S[++ n] = c ;  
        int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置  
        if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串  
            int now = newnode ( len[cur] + 2 ) ;//新建节点  
            fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转  
            next[cur][c] = now ;  
            num[now] = num[fail[now]] + 1 ;  
        }  
        last = next[cur][c] ;  
        cnt[last] ++ ;  
    }  

    void count () {  
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;  
        //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！  
    }  
} ;

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
struct Trie{
    int next[maxm][26],fail[maxm],end[maxm];
    int root,L;
    int newnode(){
    for(int i=0;i<26;i++)
        next[L][i]=-1;
    end[L++]=0;
    return L-1;
    }
    void init(){
        L=0;
        root=newnode();
    }
    void insert(char buf[]){
        int len=strlen(buf);
        int now=root;
        for(int i=0;i<len;i++){
            if(next[now][buf[i]-'a']==-1)
                next[now][buf[i]-'a']=newnode();
            now=next[now][buf[i]-'a'];
        }
        end[now]++;
    }
    void build(){
        queue<int>Q;
        fail[root]=root;
        for(int i=0;i<26;i++)
            if(next[root][i]==-1)
                next[root][i]=root;
            else{
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        while(!Q.empty()){
            int now=Q.front();
            Q.pop();
            for(int i=0;i<26;i++)
                if(next[now][i]==-1)
                    next[now][i]=next[fail[now]][i];
                else{
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
        }
    }
    int query(char buf[]){
        int len=strlen(buf);
        int now=root;
        int res=0;
        for(int i=0;i<len;i++){
            now=next[now][buf[i]-'a'];
            int temp=now;
            while(temp!=root){
                res+=end[temp];
                end[temp]=0;
                temp=fail[temp];
            }
        }
        return res;
    }
    void debug(){
        for(int i=0;i<L;i++){
            printf("id =%3d,fail = %3d,end = %3d ,chi = [",i,fail[i],end[i]);
            for(int j=0;j<26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
};

后缀数组

倍增法

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
struct DA{
//sa[i]就表示排名为i的后缀的起始位置的下标
//映射数组rk[i]就表示起始位置的下标为i的后缀的排名
/*height 数组的定义：h[i]表示rk为i的后缀与rk为i−1的后缀的最长公共前缀，可以用sa数组和rk数组来O(n)求得，这要用到一个性质：h[rk[i]]>=h[rk[i−1]]−1。也就是说如果根据rk从前往后求，每次暴力匹配来增加长度，结果是近似递增的，可以证明时间复杂度的正确性。性质的证明详见论文
*/
    bool cmp(int *r,int a,int b,int l){
        return r[a]==r[b]&&r[a+l]==r[b+l];
    }
    int t1[maxn],t2[maxn],c[maxn];
    int rank[maxn],height[maxn],RMQ[maxn],mm[maxn];
    int best[20][maxn];
    int r[maxn];
    int sa[maxn];
    int str[maxn];
    void da(int n,int m){
        n++;
        int i,j,p,*x=t1,*y=t2;
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[i]=str[i]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
        for(j=1;j<=n;j<<=1){
            p=0;
            for(i=n-j;i<n;i++)y[p++]=i;
            for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
            for(i=0;i<m;i++)c[i]=0;
            for(i=0;i<n;i++)c[x[y[i]]]++;
            for(i=1;i<m;i++)c[i]+=c[i-1];
            for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=1;x[sa[0]]=0;
            for(i=1;i<n;i++)
                x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
            if(p>=n)break;
            m=p;
        }
        int k=0;
        n--;
        for(i=0;i<=n;i++)rank[sa[i]]=i;
        for(i=0;i<n;i++){
            if(k)k--;
            j=sa[rank[i]-1];
            while(str[i+k]==str[j+k])k++;
            height[rank[i]]=k;
        }
    }
    void initRMQ(int n){
        for(int i=1;i<=n;i++)RMQ[i]=height[i];
        mm[0]=-1;
        for(int i=1;i<=n;i++)
            mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
        for(int i=1;i<=n;i++)best[0][i]=i;
        for(int i=1;i<=mm[n];i++)
        for(int j=1;j+(1<<i)-1<=n;j++){
            int a=best[i-1][j];
            int b=best[i-1][j+(1<<(i-1))];
            if(RMQ[a]<RMQ[b])best[i][j]=a;
            else best[i][j]=b;
        }
    }
    int askRMQ(int a,int b){
        int t;
        t=mm[b-a+1];
        b-=(1<<t)-1;
        a=best[t][a];b=best[t][b];
        return RMQ[a]<RMQ[b]?a:b;
    }
    int lcp(int a,int b){
        a=rank[a];b=rank[b];
        if(a>b)swap(a,b);
        return height[askRMQ(a+1,b)];
    }
    void print(int n){
        cout<<"sa[] ";
        for(int i=0;i<=n;i++)cout<<sa[i]<<" ";cout<<endl;
        cout<<"rank[] ";
        for(int i=0;i<=n;i++)cout<<rank[i]<<" ";cout<<endl;
        cout<<"height[] ";
        for(int i=0;i<=n;i++)cout<<height[i]<<" ";cout<<endl;
    }
}AA,BB;
//n=8;
//* num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ }; 注意 num 最后一位为 0，其他 大于 0
//*rank[] = 4, 6, 8, 1, 2, 3, 5, 7, 0 ;rank[0 n-1] 为有效值，rank[n] 必定为 0 无效值
// *sa[] =  8, 3, 4, 5, 0, 6, 1, 7, 2 ;sa[1 n] 为有效值，sa[0] 必定为 n 是 无效值 
//*height[]= 0, 0, 3, 2, 3, 1, 2, 0, 1 ;height[2 n] 为有效值

DC3

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
struct DA{
    #define F(x) ((x)/3+((x)%3==1?0:tb))
    #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
    int sa[maxn*20],rank[maxn*20],height[maxn*20],str[maxn*20];
    int wa[maxn*20],wb[maxn*20],wv[maxn*20],wss[maxn*20];
    int c0(int *r,int a,int b){
        return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
    }
    int c12(int k,int *r,int a,int b){
        if(k==2)
            return r[a]<r[b]||(r[a]==r[b]&&c12(1,r,a+1,b+1));
        else return r[a]<r[b]||(r[a]==r[b]&&wv[a+1]<wv[b+1]);
    }
    void sort(int *r,int *a,int *b,int n,int m){
        int i;
        for(i=0;i<n;i++)wv[i]=r[a[i]];
        for(i=0;i<m;i++)wss[i]=0;
        for(i=0;i<n;i++)wss[wv[i]]++;
        for(i=1;i<m;i++)wss[i]+=wss[i-1];
        for(i=n-1;i>=0;i--)
            b[--wss[wv[i]]]=a[i];
    }
    void dc3(int *r,int *sa,int n,int m){
        int i,j,*rn=r+n;
        int *san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
        r[n]=r[n+1]=0;
        for(i=0;i<n;i++)if(i%3!=0)wa[tbc++]=i;
        sort(r+2,wa,wb,tbc,m);
        sort(r+1,wb,wa,tbc,m);
        sort(r,wa,wb,tbc,m);
        for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
            rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
        if(p<tbc)dc3(rn,san,tbc,p);
        else for(i=0;i<tbc;i++)san[rn[i]]=i;
        for(i=0;i<tbc;i++)if(san[i]<tb)wb[ta++]=san[i]*3;
        if(n%3==1)wb[ta++]=n-1;
        sort(r,wb,wa,ta,m);
        for(i=0;i<tbc;i++)wv[wb[i]=G(san[i])]=i;
        for(i=0,j=0,p=0;i<ta&&j<tbc;p++)
            sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
        for(;i<ta;p++)sa[p]=wa[i++];
        for(;j<tbc;p++)sa[p]=wb[j++];
    }
    void da(int n,int m){
        for(int i=n;i<n*3;i++)str[i]=0;
        dc3(str,sa,n+1,m);
        int i,j,k=0;
        for(i=0;i<=n;i++)rank[sa[i]]=i;
        for(i=0;i<n;i++){
            if(k)k--;
            j=sa[rank[i]-1];
            while(str[i+k]==str[j+k])k++;
            height[rank[i]]=k;
        }
    }
    void print(int n){
        cout<<"sa[] ";
        for(int i=0;i<=n;i++)cout<<sa[i]<<" ";cout<<endl;
        cout<<"rank[] ";
        for(int i=0;i<=n;i++)cout<<rank[i]<<" ";cout<<endl;
        cout<<"height[] ";
        for(int i=0;i<=n;i++)cout<<height[i]<<" ";cout<<endl;
    }
}DA;

树链剖分

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
int n,q,a[maxn];
vector<int>G[maxn];
int size[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int id[maxn],pre[maxn],cnt=0;
void dfs1(int u,int f,int deep){
    size[u]=1;
    fa[u]=f;son[u]=0;dep[u]=deep;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f)continue;
        dfs1(v,u,deep+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}
void dfs2(int u,int root){
    id[u]=++cnt;top[u]=root;pre[cnt]=u;
    if(son[u])dfs2(son[u],root);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
int sumv[maxn<<2],maxv[maxn<<2];
inline void pushup(int o){
    sumv[o]=sumv[o<<1]+sumv[o<<1|1];
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}
void build(int o,int l,int r){
    int mid=(l+r)/2;
    if(l==r){
        sumv[o]=maxv[o]=a[pre[l]];return;
    }
    build(o<<1,l,mid);build(o<<1|1,mid+1,r);
    pushup(o);
}
void update(int o,int l,int r,int q,int v){
    int mid=(l+r)/2;
    if(l==r){
        sumv[o]=maxv[o]=v;return;
    }
    if(q<=mid)update(o<<1,l,mid,q,v);
    else update(o<<1|1,mid+1,r,q,v);
    pushup(o);
}
int querysum(int o,int l,int r,int ql,int qr){
    int mid=(l+r)/2,ans=0;
    if(ql<=l&&r<=qr)return sumv[o];
    if(ql<=mid)ans+=querysum(o<<1,l,mid,ql,qr);
    if(qr>mid)ans+=querysum(o<<1|1,mid+1,r,ql,qr);
    return ans;
}
int querymax(int o,int l,int r,int ql,int qr){
    int mid=(l+r)/2,ans=-inf;
    if(ql<=l&&r<=qr)return maxv[o];
    if(ql<=mid)ans=max(ans,querymax(o<<1,l,mid,ql,qr));
    if(qr>mid)ans=max(ans,querymax(o<<1|1,mid+1,r,ql,qr));
    return ans;
}
int qsum(int u,int v){
    int ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans+=querysum(1,1,n,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    ans+=querysum(1,1,n,id[v],id[u]);
    return ans;
}
int qmax(int u,int v){
    int ans=-inf;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans=max(ans,querymax(1,1,n,id[top[u]],id[u]));
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    ans=max(ans,querymax(1,1,n,id[v],id[u]));
    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
52
53
54
int Laxt[maxn<<1],Next[maxn<<1],To[maxn<<1],Len[maxn<<1],ppp;

void add(int u,int v,int w){
    Next[++ppp]=Laxt[u];Laxt[u]=ppp;To[ppp]=v;Len[ppp]=w;
    Next[++ppp]=Laxt[v];Laxt[v]=ppp;To[ppp]=u;Len[ppp]=w;
}
int sz[maxn],d[maxn],vis[maxn],root,sum;
void findroot(int u,int fa){//找重心
    sz[u]=1;d[u]=0;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(vis[v]||v==fa)continue;
        findroot(v,u);
        sz[u]+=sz[v];
        d[u]=max(d[u],sz[v]);
    }
    d[u]=max(d[u],sum-sz[u]);
    if(d[u]<d[root])root=u;
}
int dep[maxn],a[maxn];
void dfsdeep(int u,int fa){//计算长度
    a[++a[0]]=dep[u];
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(vis[v]||v==fa)continue;
        dep[v]=dep[u]+Len[i];
        dfsdeep(v,u);
    }
}
int L;
int cal(int u,int now){//计算答案
    dep[u]=now;a[0]=0;
    dfsdeep(u,0);
    sort(a+1,a+1+a[0]);
    int l=1,r=a[0],ans=0;
    while(l<r){
        if(a[l]+a[r]<=L)ans+=r-l,l++;
        else r--;
    }
    return ans;
}
int ans;
void solve(int u){//解决者
    vis[u]=1;
    ans+=cal(u,0);
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(vis[v])continue;
        ans-=cal(v,Len[i]);
        sum=sz[v];
        root=0;findroot(v,0);
        solve(root);
    }
}

可持续化字典树

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
int sum[maxn * 35], son[maxn * 35][2],root[maxn];

void insert(int pos,int pre,int &now,int v){

	now = ++num;
	son[now][0] = son[pre][0];
	son[now][1] = son[pre][1];
	sum[now] = sum[pre] + 1;
	if(pos==-1)
		return;
	bool k = v & (1 << pos);
	insert(pos - 1, son[pre][k], son[now][k], v);
}
int query(int pos,int st,int en,int v){
	//cout << "pos=" << pos << " v=" << v << endl;
	if(pos<0)
		return 0;
	int k = !(v & (1 << pos));
	int tmp = sum[son[en][k]] - sum[son[st][k]];

	if(tmp>0)
		return query(pos - 1, son[st][k], son[en][k], v) + (1 << pos);
	else
		return query(pos - 1, son[st][k ^ 1], son[en][k ^ 1], v);
}
int cnt;

int val[maxn],in[maxn],out[maxn],id[maxn];

void dfs(int u){
	in[u]=++cnt;
	id[cnt]=u;
	insert(30, root[in[u] - 1], root[cnt], val[u]);
	for (int i = Laxt[u]; i;i=Next[i]){
		dfs(To[i]);
	}
	out[u] = cnt;
}

主席树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int sum[maxn*40],rt[maxn*40];
int lss[maxn*40],rss[maxn*40];
int cnt;
void update(int &o,int pre,int l,int r,int val){
    o=++cnt;
    lss[o]=lss[pre];rss[o]=rss[pre];
    sum[o]=sum[pre];
    if(l==r){sum[o]++;return;}
    int mid=(l+r)/2;
    if(val<=mid)update(lss[o],lss[pre],l,mid,val);
    else update(rss[o],rss[pre],mid+1,r,val);
}
int query(int o,int l,int r,int val){
    if(l==r){
        return sum[o];
    }
    int mid=(l+r)/2;
    if(val<=mid)return query(lss[o],l,mid,val);
    else return query(rss[o],mid+1,r,val);
}
 update(rt[i],rt[i-1],1,1e9,a[i]);
query(rt[r],1,1e9,gc)
    //查询区间这个数的个数

权值线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll sum[maxn*40],val[maxn*40];
int ls[maxn*40],rs[maxn*40];
int cnt;
void update(int &o,int l,int r,int k,int num){
    if(!o)o=++cnt;
    sum[o]+=k;
    val[o]+=1LL*k*num;
    val[o]%=mod;
    if(l==r)return;
    int mid=(l+r)/2;
    if(num<=mid)update(ls[o],l,mid,k,num);
    else update(rs[o],mid+1,r,k,num);
}
ll query(int o,int l,int r,ll k){
    if(l==r)return 1LL*k*l%mod;
    int mid=(l+r)/2;
    ll res=0;
    if(k>sum[ls[o]])res=(val[ls[o]]+query(rs[o],mid+1,r,k-sum[ls[o]]));
    else res=query(ls[o],l,mid,k);
    return res%mod;
}

图论

前向星

1
2
3
4
5
int Next[maxn<<1],To[maxn<<1],Laxt[maxn<<1];
int cnt;
void add(int u,int v){
    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;
}

深度优先遍历相关

无向图的双连通分量

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
struct Edge{
    int u,v;
};
///割顶 bccno 无意义
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cut;
vector<int>G[maxn],bcc[maxn];
stack<Edge>S;
void init(int n){
    for (int i = 0; i < n; i++) G[i].clear();
}
inline void add_edge(int u, int v) { G[u].push_back(v), G[v].push_back(u); }
int dfs(int u,int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v =G[u][i];
        Edge e = (Edge){u,v};
        if(!pre[v]){ ///没有访问过
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu=min(lowu, lowv);                ///用后代更新
            if(lowv >= pre[u]){
                iscut[u]=true;
                bcc_cut++;bcc[bcc_cut].clear();   ///注意 bcc从1开始
                for(;;){
                    Edge x=S.top();S.pop();
                    if(bccno[x.u] != bcc_cut){bcc[bcc_cut].push_back(x.u);bccno[x.u]=bcc_cut;}
                    if(bccno[x.v] != bcc_cut){bcc[bcc_cut].push_back(x.v);bccno[x.v]=bcc_cut;}
                    if(x.u==u&&x.v==v)break;
                }
            }
        }
        else if(pre[v] < pre[u] && v !=fa){
            S.push(e);
            lowu = min(lowu,pre[v]);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}
void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cut = 0;
    for(int i = 0; i < n;i++)
        if(!pre[i])dfs(i,-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
75
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<vector>
#define N 201
vector<int>G[N];
int n,m,low[N],dfn[N];
bool is_cut[N];
int father[N];
int tim=0;
void input()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);/*邻接表储存无向边*/
        G[b].push_back(a);
    }
}
void Tarjan(int i,int Father)
{
    father[i]=Father;/*记录每一个点的父亲*/
    dfn[i]=low[i]=tim++;
    for(int j=0;j<G[i].size();++j)
    {
        int k=G[i][j];
        if(dfn[k]==-1)
        {
            Tarjan(k,i);
            low[i]=min(low[i],low[k]);
        }
        else if(Father!=k)/*假如k是i的父亲的话，那么这就是无向边中的重边，有重边那么一定不是桥*/
            low[i]=min(low[i],dfn[k]);//dfn[k]可能！=low[k]，所以不能用low[k]代替dfn[k],否则会上翻过头了。
    }
}
void count()
{
    int rootson=0;
    Tarjan(1,0);
    for(int i=2;i<=n;++i)
    {
        int v=father[i];
        if(v==1)
        rootson++;/*统计根节点子树的个数，根节点的子树个数>=2,就是割点*/
        else{
            if(low[i]>=dfn[v])/*割点的条件*/
            is_cut[v]=true;
        }
    }
    if(rootson>1)
    is_cut[1]=true;
    for(int i=1;i<=n;++i)
    if(is_cut[i])
    printf("%d\n",i);
    for(int i=1;i<=n;++i)
    {
        int v=father[i];
        if(v>0&&low[i]>dfn[v])/*桥的条件*/
        printf("%d,%d\n",v,i);
    }
    
}
int main()
{
    input();
    memset(dfn,-1,sizeof(dfn));
    memset(father,0,sizeof(father));
    memset(low,-1,sizeof(low));
    memset(is_cut,false,sizeof(is_cut));
    count();
    return 0;
}

有向图的强连通分量

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
vector<int>G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int>S;
inline void init(int n){
    for (int i = 0; i < n; i++) G[i].clear();
}
inline void add_edge(int u, int v) { G[u].push_back(v); }
void dfs(int u){
    pre[u]=lowlink[u]=++dfs_clock;
    S.push(u);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }
        else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}
void find_scc(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;i++)
        if(!pre[i])dfs(i);
}

2-SAT匹配

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
struct TwoSAT{
    int n;
    vector<int> G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2],c;

    bool dfs(int x){
        if(mark[x^1])return false;
        if(mark[x])return true;
        mark[x]=true;
        S[c++]=x;
        for(int i=0;i<G[x].size();i++)
            if(!dfs(G[x][i]))return false;
        return true;
    }

    void init(int n){
        this->n=n;
        for(int i=0;i<n*2;i++)G[i].clear();
        memset(mark,0,sizeof(mark));
    }
    /// x=xval or y= yval;
    void add_caluse(int x,int xval,int y,int yval){
        x=x*2+xval;
        y=y*2+yval;
        G[x^1].push_back(y);///如果x为真 那么y必须为假;
        G[y^1].push_back(x);///如果y为真 那么x必须为假;
    }

    bool solve(){
        for(int i=0;i<n*2;i+=2)
        if(!mark[i]&&!mark[i+1]){
            c=0;
            if(!dfs(i)){
                while(c>0)mark[S[--c]]=false;
                if(!dfs(i+1))return false;
            }
        }
        return true;
    }
};

最短路

Dijkstra +单源最短路+记录路径O(mlogn)

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
struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,u;
    bool operator <(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m;              ///点数和边数  点编号0~N-1
    vector<Edge>edges;    ///边列表
    vector<int>G[maxn];   ///每个节点出发的边编号
    bool done[maxn];      /// 是否已永久标号
    int d[maxn];          /// s到各个点的距离
    int p[maxn];          /// 最短路中的上一条边

    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int dist){ ///无向图调用两次
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s){
        priority_queue<HeapNode>Q;
        for(int i=0;i<n;i++)d[i]=inf;
        d[s]=0;
        memset(done,0,sizeof(done));
        Q.push((HeapNode){0,s});
        while(!Q.empty()){
            HeapNode x=Q.top();Q.pop();
            int u=x.u;
            if(done[u])continue;
            done[u]=true;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }
    /// dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t）
    void GetShortestPaths(int s,int* dist,vector<int>* paths){///paths是二维链表
        dijkstra(s);
        for(int i=0;i<n;i++){
            dist[i]=d[i];
            paths[i].clear();
            int t=i;
            paths[i].push_back(t);
            while(t!=s){
                paths[i].push_back(edges[p[t]].from);
                t=edges[p[t]].from;
            }
            reverse(paths[i].begin(),paths[i].end());
        }
    }
};

BellmanFord （单源最短路判负环）O(nm)

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
struct Edge
{
    int from, to;
    int dist;
    Edge() {}
    Edge(int u, int v, int d) : from(u), to(v), dist(d) {}
};
struct BellmanFord{
    int n,m;
    vector<Edge>edges;
    vector<int> G[maxn];
    bool inq[maxn]; /// 是否在队列中
    int d[maxn];    /// s到各个点的距离  double 要改成double类型
    int p[maxn];    /// 最短路中的上一条弧
    int cnt[maxn];  /// 进队次数
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int dist)
    {
        edges.emplace_back(from, to, dist);
        m = edges.size();
        G[from].push_back(m - 1);
    }
    bool bellmanford(int s){
        queue<int>Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); } ///如果只判负环用这个
        //for(int i=0;i<n;i++)d[i]=inf;
        //d[s]=0;inq[s]=true;Q.push(s);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=false;
            for(auto& id:G[u]){
                Edge& e=edges[id];
                if(d[u]<inf && d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u] + e.dist;
                    p[e.to]=id;
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=true;
                        if(++cnt[e.to]>n)return true;
                    }
                }
            }
        }
        return false;
    }
};

Floyd 多源最短路 O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct{
    char vertex[maxn];        //顶点表
    int edges[maxn][maxn];    //邻接矩阵,可看做边表
    int n,e;                  //图中当前的顶点数和边数
}MGraph;

void Floyd(MGraph g){
    int A[maxn][maxn];
    int path[maxn][maxn];
    int i,j,k,n=g.n;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++){
        A[i][j]=g.edges[i][j];
        path[i][j]=-1;
    }
    for(k=0;k<n;k++)
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    if(A[i][j]>(A[i][k]+A[k][j])){
        A[i][j]=A[i][k]+A[k][j];
        path[i][j]=k;
    }
}

Floyd 判环(龟兔赛跑算法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
（1）求环

初始状态下，假设已知某个起点节点为节点S。现设两个指针t和h，将它们均指向S。

同时让t和h往前推进，h的速度为t的2倍），直到h无法前进，即到达某个没有后继的节点时，就可以确定从S出发不会遇到环。反之当t与h再次相遇时，就可以确定从S出发一定会进入某个环，设其为环C。（h和t推进的步数差是环长的倍数）

（2）求环的长度

上述算法刚判断出存在环C时，t和h位于同一节点，设其为节点M。仅需令h不动，而t不断推进，最终又会返回节点M，统计这一次t推进的步数，就是环C的长度。

（3）求环的起点

为了求出环C的起点，只要令h仍均位于节点M，而令t返回起点节点S。随后，同时让t和h往前推进，且速度相同。持续该过程直至t与h再一次相遇，此相遇点就是环C的一个起点。

why？

假设出发起点到环起点的距离为m，已经确定有环，环的周长为n，（第一次）相遇点距离环的起点的距离是k。那么当两者相遇时，慢指针（t）移动的总距离i = m + a * n + k，快指针（h）的移动距离为2i，2i = m + b * n + k。其中，a和b分别为t和h在第一次相遇时转过的圈数。让两者相减（快减慢），那么有i = (b - a) * n。即i是圈长度的倍数。

将一个指针移到出发起点S，另一个指针仍呆在相遇节点M处两者同时移动，每次移动一步。当第一个指针前进了m，即到达环起点时，另一个指针距离链表起点为i + m。考虑到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
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
/// 固定根的最小树型图，邻接矩阵写法
struct MDST{
    int n;
    int w[maxn][maxn];    ///边权
    int vis[maxn];        ///访问标记，仅用来判断无解
    int ans;              ///计算答案
    int removed[maxn];    ///每个点是否被删除
    int cid[maxn];        ///所在圈编号
    int pre[maxn];        ///最小入边的起点
    int iw[maxn];         ///最小入边的权值
    int max_cid;          ///最大圈编号

    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)w[i][j]=inf;
    }
    void AddEdge(int u,int v,int cost){
        w[u][v]=min(w[u][v],cost);  ///重边取权值最小的
    }

    ///从s出发能到达多少个结点
    int dfs(int s){
        int ans=1;
        vis[s]=1;
        for(int i=0;i<n;i++)if(!vis[i]&&w[s][i]<inf)ans+=dfs(i);
        return ans;
    }
    ///从u出发沿着pre指针找圈
    bool cycle(int u){
        max_cid++;
        int v=u;
        while(cid[v]!=max_cid){cid[v]=max_cid;v=pre[v];}
        return v==u;
    }
    /// 计算u的最小入弧，入弧起点不得在圈c中
    void update(int u){
        iw[u]=inf;
        for(int i=0;i<n;i++)
        if(!removed[i]&&w[i][u]<iw[u]){
            iw[u]=w[i][u];
            pre[u]=i;
        }
    }
    ///根节点为s,如果失败返回false
    bool solve(int s){
        memset(vis,0,sizeof(vis));
        if(dfs(s)!=n)return false;
        memset(removed,0,sizeof(removed));
        memset(cid,0,sizeof(cid));
        for(int u=0;u<n;u++)update(u);
        pre[s]=s;iw[s]=0;      /// 根结点特殊处理
        ans=max_cid=0;
        for(;;){
            bool have_cycle=false;
            for(int u=0;u<n;u++)if(u!=s&&!removed[u]&&cycle(u)){
                have_cycle=true;
                /// 以下代码缩圈，圈上除了u之外的结点均删除
                int v=u;
                do{
                    if(v!=u)removed[v]=1;
                    ans+=iw[v];
                    /// 对于圈外点i，把边i->v改成i->u（并调整权值）；v->i改为u->i
                    /// 注意圈上可能还有一个v'使得i->v'或者v'->i存在，因此只保留权值最小的i->u和u->i
                    for(int i=0;i<n;i++)if(cid[i]!=cid[u]&&!removed[i]){
                        if(w[i][v]<inf)w[i][u]=min(w[i][u],w[i][v]-iw[v]);
                        w[u][i]=min(w[u][i],w[v][i]);
                        if(pre[i]==v)pre[i]=u;
                    }
                    v=pre[v];
                }while(v!=u);
                update(u);
                break;
            }
            if(!have_cycle)break;
        }
        for(int i=0;i<n;i++)
            if(!removed[i])ans+=iw[i];
        return true;
    }
};

二分图

二分图判断

1
2
3
4
5
6
7
8
9
10
11
12
color[maxn];
bool bipartite(int u){
    for(int i = 0;i < G[u].size(); i++){
        int v =G[u][i];
        if(color[v] == color[u])return false;
        if(!color[v]){
            color[v] = 3 - color[u];
            if(!bipartite(v,b))return false;
        }
    }
    return true;
}

二分图最大基数匹配

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
/// 二分图最大基数匹配
struct BPM{
    int n,m;    /// 左右顶点个数
    vector<int>G[maxn]; /// 邻接表
    int left[maxn];    /// left[i]为右边第i个点的匹配点编号，-1表示不存在
    bool T[maxn];       /// T[i]为右边第i个点是否已标记

    int right[maxn];        /// 求最小覆盖用
    bool S[maxn];           /// 求最小覆盖用

    void init(int n,int m){
        this->n=n;
        this->m=m;
        for(int i=0;i<n;i++)G[i].clear();
    }

    void AddEdge(int u,int v){
        G[u].push_back(v);
    }

    bool match(int u){
        S[u]=true;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(!T[v]){
                T[v]=true;
                if(left[v]==-1||match(left[v])){
                    left[v]=u;
                    right[u]=v;
                    return true;
                }
            }
        }
        return false;
    }
    /// 求最大匹配
    int solve(){
        memset(left,-1,sizeof(left));
        memset(right,-1,sizeof(right));
        int ans=0;
        for(int u=0;u<n;u++){
            memset(S,0,sizeof(S));
            memset(T,0,sizeof(T));
            if(match(u))ans++;
        }
        return ans;
    }
    /// 求最小覆盖。X和Y为最小覆盖中的点集
    int mincover(vector<int>& X,vector<int>& Y){
        int ans=solve();
        memset(S,0,sizeof(S));
        memset(T,0,sizeof(T));
        for(int u=0;u<n;u++)
            if(right[u]==-1)match(u);
        for(int u=0;u<n;u++)
            if(!S[u])X.push_back(u);
        for(int v=0;v<n;v++)
            if(T[v])Y.push_back(v);
        return ans;
    }
};

二分图最大权匹配(KM算法)

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
int g[150][150];  ///存图
int nx,ny; /// 两边点数
bool visx[maxn],visy[maxn];
int slack[maxn];
int linker[maxn];   ///y中各点匹配状态
int lx[maxn],ly[maxn]; /// x,y中的点标号
bool dfs(int x){
    visx[x]=true;
    for(int y=0;y<ny;y++){
        if(visy[y])continue;
        int tmp=lx[x]+ly[y]-g[x][y];
        if(tmp==0){
            visy[y]=true;
            if(linker[y]==-1||dfs(linker[y])){
                linker[y]=x;return true;
            }
        }
        else if(slack[y]>tmp)slack[y]=tmp;
    }
    return false;
}
int KM(){
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    for(int i=0;i<nx;i++){
        lx[i]=-inf;
        for(int j=0;j<ny;j++){
            if(g[i][j]>lx[i])lx[i]=g[i][j];
        }
    }
    for(int x=0;x<nx;x++){
        for(int i=0;i<ny;i++)slack[i]=inf;
        while(true){
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(dfs(x))break;
            int d=inf;
            for(int i=0;i<ny;i++)
                if(!visy[i]&&d>slack[i])d=slack[i];
            for(int i=0;i<nx;i++)
                if(visx[i])lx[i]-=d;
            for(int i=0;i<ny;i++)
                if(visy[i])ly[i]+=d;
                else slack[i]-=d;
        }
    }
    int res=0;
    for(int i=0;i<ny;i++)
        if(linker[i]!=-1)res+=g[linker[i]][i];
    return res;
}

网络流

Edge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Edge
{
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f)
        : from(u), to(v), cap(c), flow(f) {}
};
// ---
// 费用流
// ---
struct Edge
{
    int from, to, cap, flow, cost;
    Edge(int u, int v, int c, int f, int w)
        : from(u), to(v), cap(c), flow(f), cost(w) {}
};

EdmondKarp

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
const int maxn = "Edit";
struct EdmonsKarp //时间复杂度O(v*E*E)
{
    int n, m;
    vector<Edge> edges;  //边数的两倍
    vector<int> G[maxn]; //邻接表，G[i][j]表示节点i的第j条边在e数组中的序号
    int a[maxn];         //起点到i的可改进量
    int p[maxn];         //最短路树上p的入弧编号
    void init(int n)
    {
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int cap)
    {
        edges.emplace_back(from, to, cap, 0);
        edges.emplace_back(to, from, 0, 0); //反向弧
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    int Maxflow(int s, int t)
    {
        int flow = 0;
        for (;;)
        {
            memset(a, 0, sizeof(a));
            queue<int> q;
            q.push(s);
            a[s] = INF;
            while (!q.empty())
            {
                int x = q.front();
                q.pop();
                for (int i = 0; i < G[x].size(); i++)
                {
                    Edge& e = edges[G[x][i]];
                    if (!a[e.to] && e.cap > e.flow)
                    {
                        p[e.to] = G[x][i];
                        a[e.to] = min(a[x], e.cap - e.flow);
                        q.push(e.to);
                    }
                }
                if (a[t]) break;
            }
            if (!a[t]) break;
            for (int u = t; u != s; u = edges[p[u]].from)
            {
                edges[p[u]].flow += a[t];
                edges[p[u] ^ 1].flow -= a[t];
            }
            flow += a[t];
        }
        return flow;
    }
};

Dinic

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
const int maxn = "Edit";
struct Dinic
{
    int n, m, s, t;      //结点数，边数（包括反向弧），源点编号和汇点编号
    vector<Edge> edges;  //边表。edge[e]和edge[e^1]互为反向弧
    vector<int> G[maxn]; //邻接表，G[i][j]表示节点i的第j条边在e数组中的序号
    bool vis[maxn];      //BFS使用
    int d[maxn];         //从起点到i的距离
    int cur[maxn];       //当前弧下标
    void init(int n)
    {
        this->n = n;
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int cap)
    {
        edges.emplace_back(from, to, cap, 0);
        edges.emplace_back(to, from, 0, 0);
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool BFS()
    {
        memset(vis, 0, sizeof(vis));
        memset(d, 0, sizeof(d));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = 0; i < G[x].size(); i++)
            {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x, int a)
    {
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++)
        { //从上次考虑的弧
            Edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0)
            {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
    int Maxflow(int s, int t)
    {
        this->s = s, this->t = t;
        int flow = 0;
        while (BFS())
        {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, INF);
        }
        return flow;
    }
    vector<int>Mincut(){ /// call this after maxflow
        vector<int>ans;
        for(int i=0;i<edges.size();i++){
            Edge& e=edges[i];
            if(vis[e.from]&&!vis[e.to]&&e.cap>0)ans.push_back(i);
        }
        return ans;
    }
};

ISAP

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
const int maxn = "Edit";
struct ISAP
{
    int n, m, s, t;      //结点数，边数（包括反向弧），源点编号和汇点编号
    vector<Edge> edges;  //边表。edges[e]和edges[e^1]互为反向弧
    vector<int> G[maxn]; //邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
    bool vis[maxn];      //BFS使用
    int d[maxn];         //起点到i的距离
    int cur[maxn];       //当前弧下标
    int p[maxn];         //可增广路上的一条弧
    int num[maxn];       //距离标号计数
    void init(int n)
    {
        this->n = n;
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int cap)
    {
        edges.emplace_back(from, to, cap, 0);
        edges.emplace_back(to, from, 0, 0);
        int m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    int Augumemt()
    {
        int x = t, a = INF;
        while (x != s)
        {
            Edge& e = edges[p[x]];
            a = min(a, e.cap - e.flow);
            x = edges[p[x]].from;
        }
        x = t;
        while (x != s)
        {
            edges[p[x]].flow += a;
            edges[p[x] ^ 1].flow -= a;
            x = edges[p[x]].from;
        }
        return a;
    }
    void BFS()
    {
        memset(vis, 0, sizeof(vis));
        memset(d, 0, sizeof(d));
        queue<int> q;
        q.push(t);
        d[t] = 0;
        vis[t] = 1;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            int len = G[x].size();
            for (int i = 0; i < len; i++)
            {
                Edge& e = edges[G[x][i] ^ 1];
                if (!vis[e.from] && e.cap > e.flow)
                {
                    vis[e.from] = 1;
                    d[e.from] = d[x] + 1;
                    q.push(e.from);
                }
            }
        }
    }
    int Maxflow(int s, int t)
    {
        this->s = s;
        this->t = t;
        int flow = 0;
        BFS();
        memset(num, 0, sizeof(num));
        for (int i = 0; i < n; i++)
            if (d[i] < INF) num[d[i]]++;
        int x = s;
        memset(cur, 0);
        while (d[s] < n)
        {
            if (x == t)
            {
                flow += Augumemt();
                x = s;
            }
            int ok = 0;
            for (int i = cur[x]; i < G[x].size(); i++)
            {
                Edge& e = edges[G[x][i]];
                if (e.cap > e.flow && d[x] == d[e.to] + 1)
                {
                    ok = 1;
                    p[e.to] = G[x][i];
                    cur[x] = i;
                    x = e.to;
                    break;
                }
            }
            if (!ok) //Retreat
            {
                int m = n - 1;
                for (int i = 0; i < G[x].size(); i++)
                {
                    Edge& e = edges[G[x][i]];
                    if (e.cap > e.flow) m = min(m, d[e.to]);
                }
                if (--num[d[x]] == 0) break; //gap优化
                num[d[x] = m + 1]++;
                cur[x] = 0;
                if (x != s) x = edges[p[x]].from;
            }
        }
        return flow;
    }
};

MinCost MaxFlow

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
const int maxn = "Edit";
struct MCMF
{
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn]; //是否在队列中
    int d[maxn];   //bellmanford
    int p[maxn];   //上一条弧
    int a[maxn];   //可改进量
    void init(int n)
    {
        this->n = n;
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int cap, int cost)
    {
        edges.emplace_back(from, to, cap, 0, cost);
        edges.emplace_back(to, from, 0, 0, -cost);
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool BellmanFord(int s, int t, int& flow, ll& cost)
    {
        for (int i = 0; i < n; i++) d[i] = INF;
        memset(inq, 0, sizeof(inq));
        d[s] = 0;
        inq[s] = 1;
        p[s] = 0;
        a[s] = INF;
        queue<int> q;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (int i = 0; i < G[u].size(); i++)
            {
                Edge& e = edges[G[u][i]];
                if (e.cap > e.flow && d[e.to] > d[u] + e.cost)
                {
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap - e.flow);
                    if (!inq[e.to])
                    {
                        q.push(e.to);
                        inq[e.to] = 1;
                    }
                }
            }
        }
        if (d[t] == INF) return false; // 当没有可增广的路时退出
        flow += a[t];
        cost += (ll)d[t] * (ll)a[t];
        for (int u = t; u != s; u = edges[p[u]].from)
        {
            edges[p[u]].flow += a[t];
            edges[p[u] ^ 1].flow -= a[t];
        }
        return true;
    }
    int MincostMaxflow(int s, int t, ll& cost)
    {
        int flow = 0;
        cost = 0;
        while (BellmanFord(s, t, flow, cost));
        return flow;
    }
};

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
40
41
struct LCA{
    int n;
    int fa[maxn];       ///父亲数组
    int cost[maxn];     ///和父亲的费用
    int L[maxn];        ///层次(根节点为0)
    int anc[maxn][logmaxn];     /// anc[p][i]是结点p的第2^i级父亲。anc[i][0] = fa[i]
    int maxcost[maxn][logmaxn]; /// maxcost[p][i]是i和anc[p][i]的路径上的最大费用
    void preprocess(){
        for(int i=0;i<n;i++){
            anc[i][0]=fa[i];maxcost[i][0]=cost[i];
            for(int j=1;(1<<j)<n;j++)anc[i][j]=-1;
        }
        for(int j=1;(1<<j)<n;j++)
            for(int i=0;i<n;i++)
        if(anc[i][j-1]!=-1){
            int a=anc[i][j-1];
            anc[i][j]=anc[a][j-1];
            maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
        }
    }
    /// 求p到q的路径上的最大权
    int query(int p,int q){
        int tmp,log,i;
        if(L[p]<L[q])swap(p,q);
        for(log=1;(1<<log)<=L[p];log++);log--;
        int ans=-inf;
        for(int i=log;i>=0;i--)
        if(L[p]-(1<<i)>=L[q]){ans=max(ans,maxcost[p][i]);p=anc[p][i];}

        if(p==q)return ans; ///LCA为p

        for(int i=log;i>=0;i--)
        if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
            ans=max(ans,maxcost[p][i]);p=anc[p][i];
            ans=max(ans,maxcost[q][i]);q=anc[q][i];
        }
        ans=max(ans,cost[p]);
        ans=max(ans,cost[q]);
        return ans; ///LCA为fa[p]（它也等于fa[q]）
    }
};

倍增简单写法

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
int mi[maxn][22],fa[maxn][22],dep[maxn];
void dfs(int now,int pre,int w,int deep){
    fa[now][0]=pre;
    mi[now][0]=w;
    if(pre==0)mi[now][0]=inf,fa[now][0]=now;
    dep[now]=deep;
    for(auto i:ve[now]){
        if(i.to==pre)continue;
        dfs(i.to,now,i.w,deep+1);
    }
}
void init(){
    for(int i=1;i<=20;i++)
    for(int j=1;j<=n;j++){
        int p=fa[j][i-1];
        fa[j][i]=fa[p][i-1];
        mi[j][i]=min(mi[j][i-1],mi[p][i-1]);
    }
}
int lca(int p,int q){
    if(dep[p]<dep[q])swap(p,q);
    int res=inf;
    for(int i=20;i>=0;i--)
        if(dep[fa[p][i]]>=dep[q])
        res=min(res,mi[p][i]),p=fa[p][i];
    if(p==q)return res;
    for(int i=20;i>=0;i--){
        if(fa[p][i]!=fa[q][i]){
            res=min(res,mi[p][i]);
            res=min(res,mi[q][i]);
            p=fa[p][i];q=fa[q][i];
        }
    }
    return min(res,min(mi[p][0],mi[q][0]));
}

数学

一些公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//平方和公式 sigm（i^2）=n*(n+1)*(2n+1)/6
//皮克定理 多边形面积S = 多边形内整数点的个数 n + 多边形边上整数点的个数 / 2 - 1 
//边界的点数用gcd(a.x-b.x,a.y-b.y)计算
//当O点为原点时，根据向量的叉积计算公式，各个三角形的面积计算如下：
//S_OAB = 0.5*(A_x*B_y - A_y*B_x)   【(A_x，A_y)为A点的坐标】
//S_OBC = 0.5*(B_x*C_y - B_y*C_x)
/*
斯特林公式
 int digit_stirling(int n)///求n！的位数
{
     double PI=acos(double(-1));// PI的值=反余弦函数 -1.0为Pi， 1为0。
     double e=exp(double(1));//e的值
     return floor(log10(sqrt(2*PI*n))+n*log10(n/e))+1;
}
*/
//G[X]表示：1-X的数字和的总和；

//根据G[10^X]=45*X*10^(X-1);所以G[10^18]=45*18*10^17;
//等差数列求和：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2
//等比数列求和：Sn=a1*(1-q^n)/(1-q)=(a1-an*q)/(1-q)

莫比乌斯反演

组合数计数

1
2
3
4
5
6
7
8
    inv[0]=p[0]=1;
    for(int i=1;i<=n;i++)
        p[i]=p[i-1]*i%mod,inv[i]=ksm(p[i],mod-2);
}
ll cal(int n,int m){
    if(n<m)return 0LL;
    return p[n]*inv[n-m]%mod*inv[m]%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
ll pow_mod(ll x, ll n, ll mod){
    ll res=1;
    while(n){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll a,ll p){return pow_mod(a,p-2,p);}
ll cal(ll a,ll b,ll p){
    if(a<b)return 0;
    if(b>a-b)b=a-b;
    ll fz=1,fm=1;
    for(ll i=0;i<b;i++){
        fz=fz*(a-i)%p;
        fm=fm*(i+1)%p;
    }
    return fz*inv(fm,p)%p;
}

ll lucas(ll a,ll b,ll p){
    if(b==0)return 1;
    return cal(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

逆元

如果mod不是素数 那么a关于mod的逆元是 a^(phi(mod)-1)

ExGcd求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
///返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(a==0&&b==0)return -1;
    if(b==0){x=1;y=0;return a;}
    ll d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
///ax=1(mod n)
ll mod_reverse(ll a,ll n){
    ll x,y;
    ll d=extend_gcd(a,n,x,y);
    if(d==1)return (x%n+n)%n;
    else return -1;
}

费马小定理

1
2
3
4
5
6
7
8
9
10
11
///a<mod 并且 p为素数
ll pow_mod(ll x, ll n, ll mod){
    ll res=1;
    while(n){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll a,ll p){return pow_mod(a,p-2,p);}

逆元线性筛

1
2
inv[1]=1;
for (int i = 2; i < maxn; i++) inv[i] = inv[p % i] * (p - p / i) % p;

杜教筛

设需要计算的式子为：$\sum_{i=1}^{n}f(i)（f(i)为积性函数）$

我们构造两个积性函数$h$和$g$。使得$h=f∗g$

现在我们开始求$\sum_{i=1}^{n}h(i)$

记$S(n)=\sum_{i=1}^{n}f(i)$

$\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}g(d)\cdot f(\frac{i}{d})\\\to =\sum_{d=1}^{n}g(d)\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f({i})$

$\to \sum_{i=1}^{n}h(i)=\sum_{d=1}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)$

接着，我们将右边式子的第一项给提出来，可以得到：

$\sum_{i=1}^{n}h(i)=g(1)\cdot S(n)+\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)$

$\to g(1)S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor) $

其中$h(i)=(f*g)(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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=6e6+50;
unordered_map<int,int>m;
unordered_map<ll,ll>p;
bool vis[maxn];
int mu[maxn],sum_mu[maxn],phi[maxn];
ll sum_phi[maxn];
int cnt,prime[maxn];

void init(int N){
    phi[1]=mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            mu[i]=-1;phi[i]=i-1;
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]>N)break;
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<=N;i++){
        sum_mu[i]=sum_mu[i-1]+mu[i];
        sum_phi[i]=sum_phi[i-1]+phi[i];
    }
}
int getmu(int x){
    if(x<=6e6)return sum_mu[x];
    if(m[x])return m[x];
    int ans=1;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1)*getmu(x/l);
    }
    return m[x]=ans;
}
ll getphi(ll x){
    if(x<=6e6)return sum_phi[x];
    if(p[x])return p[x];
    ll ans=x*(x+1)/2;
    for(ll l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        ans-=(r-l+1)*getphi(x/l);

    }
    return p[x]=ans;
}
int main(){
    int t,n;
    cin>>t;
    init(6e6);
    while(t--){
        cin>>n;
        cout<<getphi(n)<<" "<<getmu(n)<<endl;
    }
    return 0;
}

数论

合数分解

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 prime[maxn+1];
void getprime(){
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=maxn;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
ll factor[100][2];
int fatcnt;
int getfactors(ll x){
    fatcnt=0;
    ll tmp=x;
    for(int i=1;i<=prime[0]&&prime[i]<=tmp/prime[i];i++){
        factor[fatcnt][1]=0;
        if(tmp%prime[i]==0){
            factor[fatcnt][0]=prime[i];
            while(tmp%prime[i]==0){
                factor[fatcnt][1]++;
                tmp/=prime[i];
            }
            fatcnt++;
        }
    }
    if(tmp!=1){
        factor[fatcnt][0]=tmp;
        factor[fatcnt++][1]=1;
    }
    return fatcnt;
}

欧拉函数

欧拉降幂

A^Bmod C=A^(B mod phji(C)) %C gcd(a,c)==1

A^B mod C=A^B %C (B<phi(C))

A^B mod C=A^(B mod phi(C)+phi(C))%C (B>=phi(C))

得出单个数的欧拉函数 O(sqrt n)

1
2
3
4
5
6
7
8
9
10
11
12
ll euler(ll n)
{
    ll rt = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            rt -= rt / i;
            while (n % i == 0) n /= i;
        }
    if (n > 1) rt -= rt / n;
    return rt;
}

筛法欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
const int N = "Edit";
int phi[N] = {0, 1};
void caleuler()
{
    for (int i = 2; i < N; i++)
        if (!phi[i])
            for (int j = i; j < N; j += i)
            {
                if (!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i - 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
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
void phi_and_prime_table(int N){
    memset(check,false,sizeof(check));
    phi[1]=1;
    tot=0;
    for(int i=2;i<=N;i++){
        if(!check[i]){
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>N)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else{
                phi[i*prime[j]]=phi[i]*(prime[j]-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
int prime[maxn];
bool notprime[maxn];
int mu[maxn];
void getMobius(int N){
    mu[1]=1;    ///μ函数的1是特殊情况
    int tot=0;
    for(int i=2;i<=N;i++){
        if(!notprime[i]){
            prime[++tot]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=tot;j++){
            if(i*prime[j]>N)break;
            notprime[i*prime[j]]=true;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;   ///i中已经包括了prime[j]
                break;
            }
            else{
                mu[i*prime[j]]=-mu[i];
            }
        }
    }
}

模线性方程

中国剩余定理

1
2
3
4
5
6
7
8
9
10
11
///要求m 两两互质 X=ri(mod mi) 引用返回通解 X=re+k*mo
void crt(ll r[],ll m[],ll n,ll &re,ll &mo){
    mo=1,re=0;
    for(int i=0;i<n;i++)mo*=m[i];
    for(int i=0;i<n;i++){
        ll x,y,tm=mo/m[i];
        ll d=exgcd(tm,m[i],x,y);
        re=(re+tm*x*r[i])%mo;
    }
    re=(re+mo)%mo;
}

ExCRT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//mi可以不两两互质
bool excrt(ll r[], ll m[], ll n, ll &re, ll &mo)
{
    ll x, y;
    mo = m[0], re = r[0];
    for (int i = 1; i < n; i++)
    {
        ll d = exgcd(mo, m[i],  x, y);
        if ((r[i] - re) % d != 0) return 0;
        x = (r[i] - re) / d * x % (m[i] / d);
        re += x * mo;
        mo = mo / d * m[i];
        re %= mo;
    }
    re = (re + mo) % mo;
    return 1;
}

大步小步算法 a^x=b(mod n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 求解模方程a^x=b(mod n)。n 为素数。无解返回-1
int log_mod(int a, int b) {
  int m, v, e = 1, i;
  m = (int)sqrt(MOD);
  v = inv(pow_mod(a, m));
  map <int,int> x;
  x[1] = 0;
  for(i = 1; i < m; i++){ e = mul_mod(e, a); if (!x.count(e)) x[e] = i; }
  for(i = 0; i < m; i++){
    if(x.count(b)) return i*m + x[b];
    b = mul_mod(b, v);
  }
  return -1;
}

扩展大步小步(gcd!=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
int ex_BSGS(int A,int B,int C)
{
    if(B==1) return 0;
    int k=0,tmp=1,d;
    while(1)
    {
        d=__gcd(A,C);
        if(d==1) break;
        if(B%d) return -1;
        B/=d; C/=d;
        tmp=1LL*tmp*(A/d)%C;
        k++;
        if(tmp==B) return k;
    }
    map<int,int>mp;
    mp.clear();
    int mul=B;
    mp[B]=0;
    int m=ceil(sqrt(1.0*C));
    for(int j=1;j<=m;++j)
    {
        mul=1LL*mul*A%C;
        mp[mul]=j;
    }
    int am=fastpow(A,m,C);
    mul=tmp;
    for(int j=1;j<=m;++j)
    {
        mul=1LL*mul*am%C;
        if(mp.count(mul)) return j*m-mp[mul]+k;
    }
    return -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
struct Linear_Basis{
	long long d[65],p[65];
	int cnt;
	Linear_Basis(){
		memset(d,0,sizeof(d));
		memset(p,0,sizeof(p));
		cnt=0;
	}

	bool ins(long long val){
		for (int i=62;i>=0;i--) {
			if (val&(1LL<<i)){
				if (!d[i]){
					d[i]=val;
					break;
				}
				val^=d[i];
			}
		}
		return val>0;
	}

	long long query_max(long long D=0LL){
		long long ret=D;
		for (int i=62;i>=0;i--)
			if ((ret^d[i])>ret) ret^=d[i];
		return ret;
	}

    long long query_min(long long D=0LL){
        long long ret=D;
        for(int i=0;i<=62;i++){
            if(d[i]) ret^=d[i];
        }
        return ret;
    }

	void rebuild(){
		for (int i=1;i<=62;i++)
			for (int j=0;j<i;j++)
				if (d[i]&(1LL<<j)) d[i]^=d[j];
		cnt=0;
		for (int i=0;i<=62;i++)
			if (d[i]) p[cnt++]=d[i];
	}
    //第K大
	long long kthquery(long long k){
		long long ret=0;
		if (k>=(1LL<<cnt)) return -1;
		for (int i=0;i<=62;i++)
			if (k&(1LL<<i)) ret^=p[i];
		return ret;
	}
	Linear_Basis merge(const Linear_Basis &n1,const Linear_Basis &n2){
	    Linear_Basis ret=n1;
	    for(int i=62;i>=0;i--)
            if(n2.d[i])ret.ins(n2.d[i]);
        return ret;
	}
};

几何

弧度转换,点绕点旋转

其中顺时针旋转为负，逆时针旋转为正，角度angle是弧度值，如旋转30度转换为弧度为： $angle = pi/180 * 30$。

4、度与角度的转换
根据圆为$360 º$，弧度为$2π$，即 $360º = 2π$

4.1 角度转弧度：$2π / 360 = π / 180 ≈ 0.0174rad$, 即: $度数 (π / 180） = 弧度$
例如：将30º转为弧度rad
$ 30º (π / 180）= 0.523320 rad $

4.2 弧度转角度: $360 / 2π = 180 / π ≈ 57.3º$, 即: $ 弧度 (180 / π） = 度数$
例如：将$0.523320rad$转为度º
$0.523320rad (180 / π) = 29.9992352688º $

若o不是原点，则可先将a点坐标转换为相对坐标计算，计算结果再加上o点坐标。

参与计算的a点坐标实际应为 a - 0,最终计算公式如下：

$b.x = ( a.x - o.x)cos(angle) - (a.y - o.y)sin(angle) + o.x$

$b.y = (a.x - o.x)sin(angle) + (a.y - o.y)cos(angle) + o.y$

付队模板

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#define mp make_pair
typedef long long ll;
const double inf=1e200;
const double eps=1e-8;
const double pi=4*atan(1.0);
struct point{
    double x,y;
    point(double a=0,double b=0):x(a),y(b){}
};
int dcmp(double x){ return fabs(x)<eps?0:(x<0?-1:1);}
point operator +(point A,point B) { return point(A.x+B.x,A.y+B.y);}
point operator -(point A,point B) { return point(A.x-B.x,A.y-B.y);}
point operator *(point A,double p){ return point(A.x*p,A.y*p);}
point operator /(point A,double p){ return point(A.x/p,A.y/p);}
point rotate(point A,double rad){
    return point(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
bool operator ==(const point& a,const point& b) {
     return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(point A,point B){ return A.x*B.x+A.y*B.y;}
double det(point A,point B){ return A.x*B.y-A.y*B.x;}
double dot(point O,point A,point B){ return dot(A-O,B-O);}
double det(point O,point A,point B){ return det(A-O,B-O);}
double length(point A){ return sqrt(dot(A,A));}
double angle(point A,point B){ return acos(dot(A,B)/length(A)/length(B));}
double distoline(point P,point A,point B)
{
    //点到直线距离
    point v1=B-A,v2=P-A;
    return fabs(det(v1,v2)/length(v1));
}
double distoseg(point P,point A,point B)
{
    //点到线段距离
    if(A==B) return length(P-A);
    point v1=B-A,v2=P-A,v3=P-B;
    if(dcmp(dot(v1,v2))<0) return length(v2);
    else if(dcmp(dot(v1,v3))>0) return length(v3);
    return fabs(det(v1,v2)/length(v1));
}
double Ployarea(vector<point>p)
{
    //多边形面积
    double ans=0; int sz=p.size();
    for(int i=1;i<sz-1;i++) ans+=det(p[i]-p[0],p[i+1]-p[0]);
    return ans/2.0;
}
bool SegmentProperIntersection(point a1,point a2,point b1,point b2)   {
    //规范相交
    double c1=det(a2-a1,b1-a1),c2=det(a2-a1,b2-a1);
    double c3=det(b2-b1,a1-b1),c4=det(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool isPointOnSegment(point p,point a1,point a2)
{
    //点是否在线段上
    return dcmp(det(a1-p,a2-p)==0&&dcmp(dot(a1-p,a2-p))<0);
}
int isPointInPolygon(point p,vector<point>poly)
{
    //判断点与多边形的位置关系
    int wn=0,sz=poly.size();
    for(int i=0;i<sz;i++){
        //在边上
        if(isPointOnSegment(p,poly[i],poly[(i+1)%sz])) return -1;
        int k=dcmp(det(poly[(i+1)%sz]-poly[i],p-poly[i]));
        int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+1)%sz].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    if(wn!=0) return 1;//内部
    return 0;          //外部
}
double seg(point O,point A,point B){
    if(dcmp(B.x-A.x)==0) return (O.y-A.y)/(B.y-A.y);
    return (O.x-A.x)/(B.x-A.x);
}
pair<double,int>s[110*60];
double polyunion(vector<point>*p,int N){ //有多个才加*,单个不加，有改变的加&
    //求多边形面积并
    double res=0;
    for(int i=0;i<N;i++){
        int sz=p[i].size();
        for(int j=0;j<sz;j++){
            int m=0;
            s[++m]=mp(0,0);
            s[++m]=mp(1,0);
            point a=p[i][j],b=p[i][(j+1)%sz];
            for(int k=0;k<N;k++){
                if(i!=k){
                    int sz2=p[k].size();
                    for(int ii=0;ii<sz2;ii++){
                        point c=p[k][ii],d=p[k][(ii+1)%sz2];
                        int c1=dcmp(det(b-a,c-a));
                        int c2=dcmp(det(b-a,d-a));
                        if(c1==0&&c2==0){
                            if(dcmp(dot(b-a,d-c))){
                                s[++m]=mp(seg(c,a,b),1);
                                s[++m]=mp(seg(c,a,b),-1);
                            }
                        }
                        else{
                            double s1=det(d-c,a-c);
                            double s2=det(d-c,b-c);
                            if(c1>=0&&c2<0) s[++m]=mp(s1/(s1-s2),1);
                            else if(c1<0&&c2>=0) s[++m]=mp(s1/(s1-s2),-1);
                        }
                    }
                }
            }
            sort(s+1,s+m+1);
            double pre=min(max(s[1].first,0.0),1.0),now,sum=0;
            int cov=s[0].second;
            for(int j=2;j<=m;j++){
                now=min(max(s[j].first,0.0),1.0);
                if(!cov) sum+=now-pre;
                cov+=s[j].second;
                pre=now;
            }
            res+=det(a,b)*sum;
        }
    }
    return -(res/2);
}
point jiaopoint(point p,point v,point q,point w)
{   //p+tv q+tw，点加向量表示直线，求直线交点
    point u=p-q;
    double t=det(w,u)/det(v,w);
    return p+v*t;
}
point GetCirPoint(point a,point b,point c)
{
    point p=(a+b)/2;    //ad中点
    point q=(a+c)/2;    //ac中点
    point v=rotate(b-a,pi/2.0),w=rotate(c-a,pi/2.0);   //中垂线的方向向量
    if (dcmp(length(det(v,w)))==0)    //平行
    {
        if(dcmp(length(a-b)+length(b-c)-length(a-c))==0) return (a+c)/2;
        if(dcmp(length(b-a)+length(a-c)-length(b-c))==0) return (b+c)/2;
        if(dcmp(length(a-c)+length(c-b)-length(a-b))==0) return (a+b)/2;
    }
    return jiaopoint(p,v,q,w);
}
point MinCircular(point *P,int n)
{
    //最小圆覆盖 ,看起来是O(N^3)，期望复杂度为O(N)
    random_shuffle(P+1,P+n+1);    //随机化
    point c=P[1]; double r=0;   //c 圆心,,//r 半径
    for (int i=2;i<=n;i++)
        if (dcmp(length(c-P[i])-r)>0)    //不在圆内
        {
            c=P[i],r=0;
            for (int j=1;j<i;j++)
                if (dcmp(length(c-P[j])-r)>0)
                {
                    c=(P[i]+P[j])/2.0;
                    r=length(c-P[i]);
                    for (int k=1;k<j;k++)
                        if (dcmp(length(c-P[k])-r)>0)
                        {
                            c=GetCirPoint(P[i],P[j],P[k]);
                            r=length(c-P[i]);
                        }
                }
        }
    //cout<<r<<":"<<c.x<<" "<<c.y<<endl;
    return c;
}
const int maxn=400010;
bool cmp(point a,point b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
point f[maxn],c[maxn],ch[maxn];
void convexhull(point *a,int n,int &top)
{
    //水平序的Andrew算法求凸包。
    sort(a+1,a+n+1,cmp); top=0;
    for(int i=1;i<=n;i++){ //求下凸包
        while(top>=2&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
    int ttop=top;
    for(int i=n-1;i>=1;i--){ //求上凸包
        while(top>ttop&&det(ch[top-1],ch[top],a[i])<=0) top--;
        ch[++top]=a[i];
    }
}
void P(double x)
{
    //if(fabs(x)<0.000001) puts("0.00000000"); else
    printf("%.9lf",x);
}

球体积交

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
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e2 + 5;
const double pi = acos(-1.0);
const double eps = 1e-8;
 
int Sgn(double X) {
    if (fabs(X) < eps) {
        return 0;
    }
    return X < 0 ? -1 : 1;
}
 
struct Point {
    double X, Y, Z;
 
    void Input() {
        scanf("%lf%lf%lf", &X, &Y, &Z);
    }
};
 
typedef Point Vector;
 
Vector operator + (Vector Key1, Vector Key2) {
    return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y, Key1.Z + Key2.Z};
}
 
Vector operator - (Vector Key1, Vector Key2) {
    return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y, Key1.Z - Key2.Z};
}
 
double operator * (Vector Key1, Vector Key2) {
    return Key1.X * Key2.X + Key1.Y * Key2.Y + Key1.Z * Key2.Z;
}
 
double Length(Vector Key) {
    return sqrt(Key * Key);
}
 
double operator ^ (Vector Key1, Vector Key2) {
    return Length((Vector){Key1.Y * Key2.Z - Key1.Z * Key2.Y, Key1.Z * Key2.X - Key1.X * Key2.Z, Key1.X * Key2.Y - Key1.Y * Key2.X});
}
 
double DisPointToPoint(Point Key1, Point Key2) {
    return sqrt((Key1 - Key2) * (Key1 - Key2));
}
 
struct Sphere {
    double pi=acos(-1.0);
    Point Center;
    double Radius;
 
    void Input() {
        Center.Input();
        scanf("%lf", &Radius);
    }
    double get(){
        return (4.0/3.0)*pi*Radius*Radius*Radius;
    }
};
 
double CalVolume(Sphere Key) {
    return 4.0 / 3.0 * pi * Key.Radius * Key.Radius * Key.Radius;
}
 
double SphereIntersectVolume(Sphere Key1, Sphere Key2) {
    double Ans = 0.0;
    double Dis = DisPointToPoint(Key1.Center, Key2.Center);
    if (Sgn(Dis - Key1.Radius - Key2.Radius) >= 0) {
        return Ans;
    }
    if (Sgn(Key2.Radius - (Dis + Key1.Radius)) >= 0) {
        return CalVolume(Key1);
    }
    else if (Sgn(Key1.Radius - (Dis + Key2.Radius)) >= 0) {
        return CalVolume(Key2);
    }
    double Length1 = ((Key1.Radius * Key1.Radius - Key2.Radius * Key2.Radius) / Dis + Dis) / 2;
    double Length2 = Dis - Length1;
    double X1 = Key1.Radius - Length1, X2 = Key2.Radius - Length2;
    double V1 = pi * X1 * X1 * (Key1.Radius - X1 / 3.0);
    double V2 = pi * X2 * X2 * (Key2.Radius - X2 / 3.0);
    return V1 + V2;
}
 
int T;
int N;
Sphere a;
Sphere b;
double ans;
 
int main(int argc, char *argv[]) {
 
    a.Input();
    b.Input();
    ans=a.get()+b.get()-SphereIntersectVolume(a,b);
    cout<<fixed<<setprecision(15);
    cout<<ans<<endl;
    return 0;
}

其他

技巧

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
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
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

        Scanner cin=new Scanner(System.in);

        BigInteger num1=new BigInteger("12345");
        BigInteger num2=cin.nextBigInteger();

        BigDecimal num3=new BigDecimal("123.45");
        BigDecimal num4=cin.nextBigDecimal();
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger num1=new BigInteger("12345");
        BigInteger num2=new BigInteger("45");
        //加法
        System.out.println(num1.add(num2));
        //减法
        System.out.println(num1.subtract(num2));
        //乘法
        System.out.println(num1.multiply(num2));
        //除法(相除取整)
        System.out.println(num1.divide(num2));
        //取余
        System.out.println(num1.mod(num2));
        //最大公约数GCD
        System.out.println(num1.gcd(num2));
        //取绝对值
        System.out.println(num1.abs());
        //取反
        System.out.println(num1.negate());
        //取最大值
        System.out.println(num1.max(num2));
        //取最小值
        System.out.println(num1.min(num2));
        //是否相等
        System.out.println(num1.equals(num2));
    }
}
import java.math.BigDecimal;

public class Main {
    public static void main(String[] args) {
        BigDecimal num1=new BigDecimal("123.45");
        BigDecimal num2=new BigDecimal("4.5");
        //加法
        System.out.println(num1.add(num2));
        //减法
        System.out.println(num1.subtract(num2));
        //乘法
        System.out.println(num1.multiply(num2));
        //除法（在divide的时候就设置好要精确的小数位数和舍入模式）
        System.out.println(num1.divide(num2,10,BigDecimal.ROUND_HALF_DOWN));
        //取绝对值
        System.out.println(num1.abs());
        //取反
        System.out.println(num1.negate());
        //取最大值
        System.out.println(num1.max(num2));
        //取最小值
        System.out.println(num1.min(num2));
        //是否相等
        System.out.println(num1.equals(num2));
        //判断大小( > 返回1, < 返回-1)
        System.out.println(num2.compareTo(num1));
    }
}
while(cin.hasNext())//相当于EOF
二分求开根号
static BigInteger cal(BigInteger x){
        BigInteger l = BigInteger.ONE ;
        BigInteger r = x ;
        BigInteger temp = BigInteger.ZERO ;
        while(!l.equals(r)){
            BigInteger mid = (l.add(r)).divide(BigInteger.valueOf(2)) ;
            if(temp.compareTo(BigInteger.ZERO)!=0&&temp.compareTo(mid)==0){
                break ;
            }else{
                temp = mid ;
            }
            if(temp.compareTo(BigInteger.ZERO)==0){
                temp = mid ;
            }
            if(mid.multiply(mid).compareTo(x)==1){
                r=mid ;
            }else{
                l=mid ;
            }
        }
        if(l.multiply(l).compareTo(x)==1){
            l=l.subtract(BigInteger.ONE) ;
        }
        return l;
        
}
牛顿迭代求平方根
      static BigInteger cal(BigInteger x) {
          BigInteger ans=BigInteger.valueOf(0);
          if(x.equals(BigInteger.valueOf(0))==true)return ans;
          BigInteger r=BigInteger.valueOf(1);
          BigInteger l=BigInteger.valueOf(-1);
          while(true) {
              BigInteger nxt =r.add(x.divide(r)).shiftRight(1);
              if(nxt.equals(l)==true) {
                  if(l.compareTo(r)==-1)return r;
                  else return l;
              }
              l=r;r=nxt;
          }

      }

文件读入

1
2
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

扩栈

1
2
// 解决爆栈问题
#pragma comment(linker, "/STACK:1024000000,1024000000")

快速读入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 适用于正负整数
template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0; //EOF
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}
inline void out(int x)
{
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}

莫队算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ---
// 莫队算法,可以解决一类静态,离线区间查询问题。分成 $\sqrt{x}$ 块,分块排序。
// ---
struct query { int L, R, id; };
void solve(query node[], int m)
{
    memset(ans, 0, sizeof(ans));
    sort(node, node + m, [](query a, query b) {
        return a.l / unit < b.l / unit
               || a.l / unit == b.l / unit && a.r < b.r;
    });
    int L = 1, R = 0;
    for (int i = 0; i < m; i++)
    {
        while (node[i].L < L) add(a[--L]);
        while (node[i].L > L) del(a[L++]);
        while (node[i].R < R) del(a[R--]);
        while (node[i].R > R) add(a[++R]);
        ans[node[i].id] = tmp;
    }
}

高精度

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
// 加法 乘法 小于号 输出
struct bint
{
    int l;
    short int w[100000];
    bint(ll x = 0)
    {
        l = x == 0, memset(w, 0,sizeof(w));
        while (x) w[l++] = x % 10, x /= 10;
    }
    bool operator<(const bint& x) const
    {
        if (l != x.l) return l < x.l;
        int i = l - 1;
        while (i >= 0 && w[i] == x.w[i]) i--;
        return (i >= 0 && w[i] < x.w[i]);
    }
    bint operator+(const bint& x) const
    {
        bint ans;
        ans.l = l > x.l ? l : x.l;
        for (int i = 0; i < ans.l; i++)
        {
            ans.w[i] += w[i] + x.w[i];
            ans.w[i + 1] += ans.w[i] / 10;
            ans.w[i] = ans.w[i] % 10;
        }
        if (ans.w[ans.l] != 0) ans.l++;
        return ans;
    }
    bint operator*(const bint& x) const
    {
        bint res;
        int up, tmp;
        for (int i = 0; i < l; i++)
        {
            up = 0;
            for (int j = 0; j < x.l; j++)
            {
                tmp = w[i] * x.w[j] + res.w[i + j] + up;
                res.w[i + j] = tmp % 10;
                up = tmp / 10;
            }
            if (up != 0) res.w[i + x.l] = up;
        }
        res.l = l + x.l;
        while (res.w[res.l - 1] == 0 && res.l > 1) res.l--;
        return res;
    }
    void print()
    {
        for (int i = l - 1; ~i; i--) printf("%d", w[i]);
        puts("");
    }
};

矩阵

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat& A,mat &B){
    mat C(A.size(),vec(B[0].size()));
    for(int i=0;i<A.size();i++)
        for(int k=0;k<B.size();k++)
        if(A[i][k])
            for(int j=0;j<B[0].size();j++)
            C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
    return C;
}
mat Pow(mat A,ll n){
    mat B(A.size(),vec(A.size()));
    for(int i=0;i<A.size();i++)B[i][i]=1;
    for(;n;n>>=1,A=mul(A,A))
        if(n&1)B=mul(B,A);
    return B;
}

高斯消元

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
void gauss()
{
    int now = 1, to;
    double t;
    for (int i = 1; i <= n; i++, now++)
    {
        /*for (to = now; !a[to][i] && to <= n; to++);
        //做除法时减小误差，可不写
        if (to != now)
            for (int j = 1; j <= n + 1; j++)
                swap(a[to][j], a[now][j]);*/
        t = a[now][i];
        for (int j = 1; j <= n + 1; j++) a[now][j] /= t;
        for (int j = 1; j <= n; j++)
            if (j != now)
            {
                t = a[j][i];
                for (int k = 1; k <= n + 1; k++) a[j][k] -= t * a[now][k];
            }
    }
}
int gauss(int n,int m){
   int col, i, mxr, j, row;
   for (row = col = 1; row <= n && col <= m;row++,col++){
      mxr = row;
      for (i = row + 1; i <= n;i++)
      if(fabs(a[i][col])>fabs(a[mxr][col]))
         mxr = i;
      if(mxr!=row)
         swap(a[row], a[mxr]);
      if(fabs(a[row][col])<eps){
         row--;
         continue;
      }
      for (i = 1; i <= n;i++) /////消成上三角矩阵
         if(i!=row&&fabs(a[i][col])>eps)
            for (j = m; j >= col;j--)
               a[i][j] -= a[row][j] / a[row][col] * a[i][col];
         
   }
   row--;
   for (i = row; i >= 1;i--){//////回代成对角矩阵
      for (j = i + 1; j <= row;j++){
         a[i][m] -= a[j][m] * a[i][j];
      }
      a[i][m] /= a[i][i];
   }
   return row;
}

数位DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int num[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool first){
    if(pos==-1)return 1;
    if(!first&&dp[pos][sta]!=-1)return dp[pos][sta];
    int up=first?num[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++){
        if(pre==6&&i==2)continue;
        if(i==4)continue;
        ans+=dfs(pos-1,i,i==6,first&&i==num[pos]);
    }
    if(!first)dp[pos][sta]=ans;
    return ans;
}
int ac(int x){
    int pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true);
}