[TOC]

树状数组求逆序对

[https://vjudge.net/contest/515986#problem/C]: 

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
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 2e5 + 10;
int a[N];
int t[N];
typedef long long ll;
int lowbit(int x)
{
    return x & -x;
}
void add(int x)
{
    while (x <= n)
    {
        t[x]++;
        x += lowbit(x);
    }
}
int ask(int x)
{
    int sum = 0;
    while (x >= 1)
    {
        sum += t[x];
        x -= lowbit(x);
    }
    return sum;
}
int main()
{
    scanf("%d", &n);
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        add(a[i]);
        sum += (i - ask(a[i]));
    }
    printf("%lld\n", sum);
    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
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
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e6 + 10;
int tr[N];
int num[N];
int last[N];
int ans[N];
struct node
{
    int l, r, pos;
} ask[N];
bool cmp(node a, node b)
{
    return a.r < b.r;
}
int lowbit(int x)
{
    return x & (-x);
}
void add(int x, int ans)
{
    while (x <= n)
    {
        tr[x] += ans;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
    }
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &ask[i].l, &ask[i].r);
        ask[i].pos = i;
    }
    sort(ask + 1, ask + 1 + m, cmp);
    int fuck = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = fuck; j <= ask[i].r; j++)
        {
            if (last[num[j]])
            {
                add(last[num[j]], -1);
            }
            add(j, 1);
            last[num[j]] = j;
        }
        fuck = ask[i].r + 1;
        ans[ask[i].pos] = sum(ask[i].r) - sum(ask[i].l - 1);
    }
    for (int i = 1; i <= m; i++)
    {
        printf("%d\n", ans[i]);
    }
    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
#include <bits/stdc++.h>
using namespace std;
int sum[1001][1001];
int main()
{
    int m, n, x1, y1, x2, y2, value;
    scanf("%d %d", &n, &m); //从一开始避免了分类讨论
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &value);
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + value;
        }
    }
    int q;
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);
    }
    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
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
#include<bits/stdc++.h>
using namespace std;

/*
 * 给出一个序列，查询区间内有多少个不相同的数
 */
const int MAXN = 30010;
const int M = MAXN * 100;
int n, q, tot;
int a[MAXN];
int T[M], lson[M], rson[M], c[M];
int build(int l, int r)
{
    int root = tot++;
    c[root] = 0;
    if (l != r)
    {
        int mid = (l + r) >> 1;
        lson[root] = build(l, mid);
        rson[root] = build(mid + 1, r);
    }
    return root;
}
int update(int root, int pos, int val)
{
    int newroot = tot++, tmp = newroot;
    c[newroot] = c[root] + val;
    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (pos <= mid)
        {
            lson[newroot] = tot++;
            rson[newroot] = rson[root];
            newroot = lson[newroot];
            root = lson[root];
            r = mid;
        }
        else
        {
            rson[newroot] = tot++;
            lson[newroot] = lson[root];
            newroot = rson[newroot];
            root = rson[root];
            l = mid + 1;
        }
        c[newroot] = c[root] + val;
    }
    return tmp;
}
int query(int root, int pos)
{
    int ret = 0;
    int l = 1, r = n;
    while (pos < r)
    {
        int mid = (l + r) >> 1;
        if (pos <= mid)
        {
            r = mid;
            root = lson[root];
        }
        else
        {
            ret += c[lson[root]];
            root = rson[root];
            l = mid + 1;
        }
    }
    return ret + c[root];
}

int main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    while (scanf("%d", &n) == 1)
    {
        tot = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        T[n + 1] = build(1, n); //建立一颗空树
        map<int, int> mp;
        for (int i = n; i >= 1; i--)
        {
            if (mp.find(a[i]) == mp.end())
            {
                T[i] = update(T[i + 1], i, 1);
            }
            else
            {
                int tmp = update(T[i + 1], mp[a[i]], -1);
                T[i] = update(tmp, i, 1);
            }
            mp[a[i]] = i;
        }
        scanf("%d", &q);
        while (q--)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", query(T[l], r));
        }
    }
    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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 10;
int w[N];
int n, q;
int _max, _min;
const int INF = 0x3f3f3f3f;
struct node
{
    int l, r, minn, maxn;
} tr[N * 4];
void pushup(int u)
{
    tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);
    tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void build(int u, int l, int r)
{
    tr[u].l = l;
    tr[u].r = r;
    if (l == r)
    {
        tr[u].maxn = tr[u].minn = w[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        _max = max(_max, tr[u].maxn);
        _min = min(_min, tr[u].minn);
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
    {
        query(u << 1, l, r);
    }
    if (r > mid)
    {
        query(u << 1 | 1, l, r);
    }
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
    }
    build(1, 1, n);
    int l, r;
    while (q--)
    {
        scanf("%d%d", &l, &r);
        _max = -INF;
        _min = INF;
        query(1, l, r);
        printf("%d\n", _max - _min);
    }
    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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int w[N];
struct node
{
    int l, r, sum, lazy;
} tr[N * 4];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
    if (tr[u].lazy != 0)
    {
        tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].lazy;
        tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].lazy;
        tr[u << 1].lazy += tr[u].lazy;
        tr[u << 1 | 1].lazy += tr[u].lazy;
        tr[u].lazy = 0;
    }
}
void build(int u, int l, int r)
{
    tr[u] = {l, r, w[l], 0};
    if (l == r)
    {
        return;
    }
    int mid = (l + r) / 2;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
        tr[u].lazy += k;
        return;
    }
    int mid = (tr[u].l + tr[u].r) / 2;
    pushdown(u);
    if (l <= mid)
    {
        update(u << 1, l, r, k);
    }
    if (r > mid)
    {
        update(u << 1 | 1, l, r, k);
    }
    pushup(u);
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    int sum = 0;
    if (l <= mid)
    {
        sum += query(u << 1, l, r);
    }
    if (r > mid)
    {
        sum += query(u << 1 | 1, l, r);
    }
    return sum;
}
signed main()
{
    int n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &w[i]);
    }
    build(1, 1, n);
    int op;
    int x, y, k;
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld", &op);
        if (op == 1)
        {
            scanf("%lld%lld%lld", &x, &y, &k);
            update(1, x, y, k);
        }
        else
        {
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", query(1, x, y));
        }
    }
    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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int w[N];
struct node
{
    int l, r, sum;
} tr[N * 4];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
    tr[u] = {l, r, w[l]};
    if (l == r)
    {
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update(int u, int x, int k)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        tr[u].sum += k;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid)
    {
        update(u << 1, x, k);
    }
    else if (x > mid)
    {
        update(u << 1 | 1, x, k);
    }
    pushup(u);
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid)
    {
        sum += query(u << 1, l, r);
    }
    if (r > mid)
    {
        sum += query(u << 1 | 1, l, r);
    }
    return sum;
}
signed main()
{
    int n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &w[i]);
    }
    build(1, 1, n);
    int op;
    int x, y, k;
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld", &op);
        if (op == 1)
        {
            scanf("%lld%lld", &x, &k);
            update(1, x, k);
        }
        else
        {
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", query(1, x, y));
        }
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int ne[N];
int ch[N][26], cnt[N], idx;
void insert(string s)
{
    int p = 0;
    for (int i = 0; s[i]; i++)
    {
        int j = s[i] - 'a';
        if (!ch[p][j])
        {
            ch[p][j] = ++idx;
        }
        p = ch[p][j];
    }
    cnt[p]++;
}
void build()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
    {
        if (ch[0][i])
        {
            q.push(ch[0][i]);
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {
            int v = ch[u][i];
            if (v)
            {
                ne[v] = ch[ne[u]][i];
                q.push(v);
            }
            else
            {
                ch[u][i] = ch[ne[u]][i];
            }
        }
    }
}
int query(string s)
{
    int ans = 0;
    for (int k = 0, i = 0; s[k]; k++)
    {
        i = ch[i][s[k] - 'a'];
        for (int j = i; j && ~cnt[j]; j = ne[j])
        {
            ans += cnt[j];
            cnt[j] = -1;
        }
    }
    return ans;
}
int main()
{
    int t;
    string a;
    scanf("%d", &t);
    while (t--)
    {
        cin >> a;
        insert(a);
    }
    build();
    cin >> a;
    int ans = query(a);
    printf("%d\n", ans);
    return 0;
}

欧拉函数求小于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
//试除法求单个欧拉函数
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int phi(int n)
{
    int ans = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ans = ans * (i - 1) / i; //这里实际上是ans*(i分之i减一)
            while (n % i == 0)
            {
                n /= i;
            }
        }
    }
    if (n > 1)
    {
        ans = ans * (n - 1) / n;
    }
    return ans;
}
signed main()
{
    int n;
    while (scanf("%lld", &n) != EOF)
    {
        if (n == 0)
        {
            break;
        }
        printf("%lld\n", phi(n));
    }
    return 0;
}
//-------------------------------
//筛法求1~n的欧拉函数
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int p[N], vis[N], cnt;
int phi[N];
void get_phi(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; i * p[j] <= n; j++)
        {
            int m = i * p[j];
            vis[m] = 1;
            if (i % p[j] == 0)
            {
                phi[m] = p[j] * phi[i];
                break;
            }
            else
            {
                phi[m] = (p[j] - 1) * phi[i];
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    get_phi(n);
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", phi[i]);
    }
    return 0;
}

java中的BigInteger类

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
import java.lang.*;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger a = sc.nextBigInteger();
        BigInteger b = sc.nextBigInteger();
        System.out.println(a.add(b));//相加
        System.out.println(a.subtract(b));//相减
        System.out.println(a.multiply(b));//相乘
        System.out.println(a.divide(b));//相除取整
        System.out.println(a.gcd(b));//最大公约数
        System.out.println(a.abs());//绝对值
        System.out.println(a.negate());//数字取反
        int ans=10;
        System.out.println(a.pow(ans));//幂次方
        BigInteger mod=new BigInteger("1000000007");
        System.out.println(a.remainder(mod));//取模
        System.out.println(a.compareTo(b));//比较大小，大于返回1，小于返回-1，等于返回0
        int x=2;
        System.out.println(a.toString(x));//返回大整数x进制的字符串表示
    }
}

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
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
//vector存储边
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int dep[N];    // dep[u]存u点在树上的深度
int fa[N][20]; // fa[u][i]存从u点向上跳2的i次方层的祖先结点
vector<int> v[N];
int n, m, s;
void dfs(int u, int father)
{
    dep[u] = dep[father] + 1;
    fa[u][0] = father;
    for (int i = 1; i <= 19; i++) //跳2的0次方情况已经弄过了，所以从1开始
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; //先向上跳2的i-1层，再向上跳2^i-1层
    }
    for (auto t : v[u]) // dfs深搜就行
    {
        if (t == father)
            continue;
        dfs(t, u);
    }
}
int lca(int u, int v)
{
    if (dep[u] < dep[v]) //从深度大的开始跳
    {
        swap(u, v);
    }
    for (int i = 19; i >= 0; i--) //先跳到同一层
    {
        if (dep[fa[u][i]] >= dep[v])
        {
            u = fa[u][i];
        }
    }
    if (u == v) //看看他俩在不在一条路径上
    {
        return v;
    }
    //否则就两个结点一起往上跳，找到第一个相同的结点
    for (int i = 19; i >= 0; i--)
    {
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i], v = fa[v][i];
        }
    }
    //跳到最后一定是再跳1层就行，但判断之后不符合条件就直接退出了，所以最后u和v并没有赋值，得到的实际上是最近公共祖先的子节点
    return fa[u][0]; //返回再跳一层的值即可
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    int x, y;
    for (int i = 1; i <= n - 1; i++)
    {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(s, 0);
    int u, v;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}
//-----------------------------------------
//链式前向星存储边
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
struct node
{
    int to, nex;
} a[N * 2];
int dep[N];    // dep[u]存u点在树上的深度
int fa[N][20]; // fa[u][i]存从u点向上跳2的i次方层的祖先结点
// vector<int> v[N];
int n, m, s;
int head[N];
int idx;
void add(int u, int v)
{
    a[++idx].to = v;
    a[idx].nex = head[u];
    head[u] = idx;
}
void dfs(int u, int father)
{
    dep[u] = dep[father] + 1;
    fa[u][0] = father;
    for (int i = 1; i <= 19; i++) //跳2的0次方情况已经弄过了，所以从1开始
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; //先向上跳2的i-1层，再向上跳2^i-1层
    }
    for (int i = head[u]; i != -1; i = a[i].nex)
    {
        if (a[i].to == father)
        {
            continue;
        }
        dfs(a[i].to, u);
    }
}
int lca(int u, int v)
{
    if (dep[u] < dep[v]) //从深度大的开始跳
    {
        swap(u, v);
    }
    for (int i = 19; i >= 0; i--) //先跳到同一层
    {
        if (dep[fa[u][i]] >= dep[v])
        {
            u = fa[u][i];
        }
    }
    if (u == v) //看看他俩在不在一条路径上
    {
        return v;
    }
    //否则就两个结点一起往上跳，找到第一个相同的结点
    for (int i = 19; i >= 0; i--)
    {
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i], v = fa[v][i];
        }
    }
    //跳到最后一定是再跳1层就行，但判断之后不符合条件就直接退出了，所以最后u和v并没有赋值，得到的实际上是最近公共祖先的子节点
    return fa[u][0]; //返回再跳一层的值即可
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    memset(head, -1, sizeof(head));
    int x, y;
    for (int i = 1; i <= n - 1; i++)
    {
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(s, 0);
    int u, v;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

LCATraJan写法

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;
const int N = 5e5 + 10;
int n, m, s, a, b;
vector<int> e[N];
vector<pair<int, int>> query[N];
int fa[N], vis[N], ans[N];
int find(int x)
{
    if (x == fa[x])
    {
        return x;
    }
    else
    {
        return fa[x] = find(fa[x]);
    }
}
void tarjan(int x)
{
    vis[x] = 1; //标记x已访问
    for (auto t : e[x])
    {
        if (vis[t] == 0)
        {
            tarjan(t);
            fa[t] = x; //回到x时指向x
        }
    }
    //离开x时找LCA
    for (auto q : query[x])
    {
        int y = q.first, i = q.second;
        if (vis[y] == 1)
        {
            ans[i] = find(y);
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n - 1; i++)
    {
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &a, &b);
        query[a].push_back({b, i});
        query[b].push_back({a, i});
    }
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    tarjan(s);
    for (int i = 1; i <= m; i++)
    {
        printf("%d\n", ans[i]);
    }
    return 0;
}

拓扑排序（Kahn算法)

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
//https://vjudge.net/problem/UVA-10305
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 10;
int n, m;
int din[N];
vector<int> e[N], ans;
void toposort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (din[i] == 0)
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        ans.push_back(x);
        for (auto y : e[x])
        {
            --din[y];
            if (din[y] == 0)
            {
                q.push(y);
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (1)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
        {
            break;
        }
        for (int i = 1; i <= N; i++)
        {
            e[i].clear();
        }
        memset(din, 0, sizeof(din));
        ans.clear();
        int a, b;
        for (int i = 1; i <= m; i++)
        {
            cin >> a >> b;
            e[a].push_back(b);
            din[b]++;
        }
        toposort();
        for (auto x : ans)
        {
            cout << x << " ";
        }
        cout << '\n';
    }
    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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int ch[N * 31][2];//ch[p][j]表示p号结点沿着j这条边到达的子节点
int idx;
void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i--)
    {
        int j = x >> i & 1;
        if (!ch[p][j])
        {
            ch[p][j] = ++idx;
        }
        p = ch[p][j];
        // printf("%d\n", idx);
    }
}
int query(int x)
{
    int p = 0, sum = 0;
    for (int i = 30; i >= 0; i--)
    {
        int j = x >> i & 1;
        if (ch[p][!j])
        {
            sum += 1 << i;
            p = ch[p][!j];
        }
        else
        {
            p = ch[p][j];
        }
    }
    return sum;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    int maxn = 0;
    for (int i = 1; i <= n; i++)
    {
        maxn = max(maxn, query(a[i]));
    }
    printf("%d\n", maxn);
    return 0;
}

优先队列 priority_queue

empty() 如果队列为空返回真

pop() 删除对顶元素

push() 加入一个元素

size() 返回优先队列中拥有的元素个数

top() 返回优先队列队顶元素

在默认的优先队列中，优先级高的先出队。在默认的 int 型中先出队的为较大的数

1
2
1 priority_queue<int>q1;//大的先出对
2 priority_queue<int,vector<int>,greater<int> >q2; //小的先出队

自定义比较函数：

1
2
3
4
5
6
7
8
9
10
1 struct cmp
2 {
3 bool operator ()(int x, int y)
4 {
5 return x > y; // x 小的优先级高
6 //也可以写成其他方式，如：return p[x] > p[y]; 表示 p[i] 小的优先级高
7 }
8 };
9 priority_queue<int, vector<int>, cmp>q;//定义方法
10 //其中，第二个参数为容器类型。第三个参数为比较函数。
1
2
3
4
5
6
7
8
9
10
11
12
struct node
2 {
3 int x, y;
4 friend bool operator < (node a, node b)
5 {
6 return a.x > b.x; //结构体中，x 小的优先级高
7 }
8 };
9 priority_queue<node>q;//定义方法
10 //在该结构中，y 为值, x 为优先级。
11 //通过自定义 operator< 操作符来比较元素中的优先级。
12 //在重载”<”时，最好不要重载”>”，可能会发生编译错误

求逆元的四种方法

  • 扩展欧几里得求逆元

这种方法常数最小

1
2
3
4
5
6
7
8
9
10
typedef  long long ll;
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll inverse(ll a,ll n){
    ll d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

  • 费马小定理求逆元（%m为素数）

如果一个数m为素数，那么a^(m-1)≡1 (mod m)，那么a的逆元就是a^(m-2)，这是根据费马小定理推出来的。

1
2
3
4
5
6
7
8
9
10
11
typedef  long long ll;
ll pow_mod(ll x, ll n, ll mod){
    ll res=1;
    while(n>0){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll ans = pow_mod(a,m-2,m);

  • 欧拉函数求逆元（%p不为素数）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long eular(long long n)
{
    long long ans = n;
    for(int i = 2; i*i <= n; i++)
    {
        if(n % i == 0)
        {
            ans -= ans/i; //等价于通项，把n乘进去
            while(n % i == 0) //确保下一个i是n的素因数
                n /= i;
        }
    }
    if(n > 1)ans -= ans/n; //最后可能还剩下一个素因数没有除
    return ans;
}

注意，求出φ(n)以后依旧是mod n。

然后根据a^(φ(n))≡1 (mod n)，再拉个快速幂就行了。

  • 逆元打表

    ​ 最喜欢的就是这个了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    typedef  long long ll;
    const int N = 1e5 + 5;
    int inv[N];
     
    void inverse(int n, int p) {
        inv[1] = 1;
        for (int i=2; i<=n; ++i) {
            inv[i] = (ll) (p - p / i) * inv[p%i] % p;
        }
    }

  • n!的逆元

    1
    2
    3
    4
    5
    // 先利用费马小定理求出 n! 的逆元，再倒推求(n-1)!... 的逆元
    inv[N] = power(fac[N], MOD - 2); // fac[n]为 N 的阶乘

    for (i = N - 1; i >= 0; i--)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % 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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20;
int n, m, prim[N];
/*给定一个整数n和m个不同的质数p1,p2,...,pm ,
求1～n中能被p1,p2,…,pm中的至少一个数整除的数有多少个?
其中m≤16, n, pi ≤ 10*/
// 2 3
// 2 3 5
// 10
int calc()
{
    int res = 0;
    for (int i = 1; i < 1 << m; i++)
    {
        int t = 1, sign = -1;
        for (int j = 0; j < m; j++)
        {
            if (i & 1 << j)
            {
                if (t * prim[j] > n)
                {
                    t = 0;
                    break;
                }
                t *= prim[j];
                sign = -sign;
            }
        }
        if (t)
        {
            res += n / t * sign;
        }
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> prim[i];
    }
    cout << calc() << '\n';
    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
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
// 洛谷P1450，它的本质是全集减补集的并集
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int c[10], d[10];
int dp[N];
int n;
int s;
void init()
{
    dp[0] = 1;
    for (int i = 1; i <= 4; i++)
    {
        for (int j = c[i]; j <= N; j++)
        {
            dp[j] += dp[j - c[i]];
        }
    }
}
int calc()
{
    int ans = 0;
    for (int i = 1; i < 1 << 4; i++)
    {
        int t = 0, sign = -1;
        for (int j = 1; j <= 4; j++)
        {
            if (i & 1 << (j - 1))
            {
                t += c[j] * (d[j] + 1);
                sign = -sign;
            }
        }
        if (s >= t)
        {
            ans += dp[s - t] * sign;
        }
    }
    return dp[s] - ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 1; i <= 4; i++)
    {
        cin >> c[i];
    }
    init();
    cin >> n;
    while (n--)
    {
        for (int i = 1; i <= 4; i++)
        {
            cin >> d[i];
        }
        cin >> s;
        cout << calc() << '\n';
    }
    return 0;
}

筛法求莫比乌斯函数

image-20230317212228262

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int p[N], vis[N], cnt;
int mu[N];
void get_mu(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; i * p[j] <= n; j++)
        {
            int m = i * p[j];
            vis[m] = 1;
            if (i % p[j] == 0)
            {
                mu[m] = 0;
                break;
            }
            else
            {
                mu[m] = -mu[i];
            }
        }
    }
}
signed main()
{
    int n;
    cin >> n;
    get_mu(n);
    for (int i = 1; i <= n; i++)
    {
        cout << mu[i] << '\n';
    }
    return 0;
}

BSGS算法

image-20230321153331033

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
int bsgs(int a, int b, int p)
{
    a %= p, b %= p;
    if (b == 1)
    {
        return 0;
    }
    int m = ceil(sqrt(p));
    int t = b;
    unordered_map<int, int> hash;
    hash[b] = 0;
    for (int j = 1; j < m; j++)
    {
        t = t * a % p;
        hash[t] = j;
    }
    int mi = 1;
    for (int i = 1; i <= m; i++)
    {
        mi = mi * a % p;
    }
    t = 1;
    for (int i = 1; i <= m; i++)
    {
        t = t * mi % p;
        if (hash.count(t))
        {
            return i * m - hash[t];
        }
    }
    return -1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int p, b, n;
    cin >> p >> b >> n;
    int ans = bsgs(b, n, p);
    if (ans == -1)
    {
        cout << "no solution" << '\n';
    }
    else
    {
        cout << ans << '\n';
    }
    return 0;
}

扩展BSGS算法

image-20230321165933077

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
// 洛谷 4195
// 用于a和p不互质的情况
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}
LL exbsgs(LL a, LL b, LL p)
{
    a %= p;
    b %= p;
    if (b == 1 || p == 1)
        return 0; // x=0

    LL d, k = 0, A = 1;
    while (true)
    {
        d = gcd(a, p);
        if (d == 1)
            break;
        if (b % d)
            return -1; // 无解
        k++;
        b /= d;
        p /= d;
        A = A * (a / d) % p; // 求a^k/D
        if (A == b)
            return k;
    }

    LL m = ceil(sqrt(p));
    LL t = b;
    unordered_map<int, int> hash;
    hash[b] = 0;
    for (int j = 1; j < m; j++)
    {
        t = t * a % p; // 求b*a^j
        hash[t] = j;
    }
    LL mi = 1;
    for (int i = 1; i <= m; i++)
        mi = mi * a % p; // 求a^m
    t = A;
    for (int i = 1; i <= m; i++)
    {
        t = t * mi % p; // 求(a^m)^i
        if (hash.count(t))
            return i * m - hash[t] + k;
    }
    return -1; // 无解
}
int main()
{
    LL a, p, b;
    while ((scanf("%lld%lld%lld", &a, &p, &b) != EOF) && a)
    {
        LL res = exbsgs(a, b, p);
        if (res == -1)
            puts("No Solution");
        else
            printf("%lld\n", res);
    }
    return 0;
}

威尔逊定理

image-20230321161853459

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
//HDU 2973
#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
const int mx = 3000008;
int s[N], p[N], vis[mx], t, n;
void get_prim()
{
    for (long long i = 2; i < mx; ++i)
    {
        if (!vis[i])
        {
            if ((i - 7) % 3 == 0)
            {
                p[(i - 7) / 3] = 1;
            }
            for (long long j = i * i; j < mx; j += i)
            {
                vis[j] = 1;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    get_prim();
    for (int i = 2; i < N; ++i)
    {
        s[i] = s[i - 1] + p[i];
    }
    cin >> t;
    while (t--)
    {
        cin >> n;
        cout << s[n] << '\n';
    }
    return 0;
}

裴蜀定理

image-20230321163914077

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// luogu 4549
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int s = a[1];
    for (int i = 1; i <= n; i++)
    {
        s = __gcd(abs(a[i]), s);
    }
    cout << s << '\n';
    return 0;
}

卡特兰数(Catalan数)

image-20230321211646630

image-20230321211959934

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//luogu P1044
#include <bits/stdc++.h>
using namespace std;
#define int long long
int f[200];
signed main()
{
    ios::sync_with_stdio(false); // 关闭同步流，提升cin、cout读入输出效率
    cin.tie(0);                  // 解除 cin 与 cout 的绑定，提升输入速度
    cout.tie(0);
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] * (i * 4 - 2) / (i + 1);
    }
    cout << f[n] << '\n';
    return 0;
}

普通生成函数

image-20230322214258600

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
//HDU 2152
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
const int N = 1e2 + 10;
int a[N], b[N], c[N], d[N];
int clac()
{
    for (int i = 0; i <= m; i++)
    {
        c[i] = d[i] = 0;
    }
    for (int i = a[1]; i <= b[1]; i++)
    {
        c[i] = 1;
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            for (int k = a[i]; k <= b[i]; k++)
            {
                d[j + k] += c[j];
            }
        }
        for (int j = 0; j <= m; j++)
        {
            c[j] = d[j];
            d[j] = 0;
        }
    }
    return c[m];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i] >> b[i];
        }
        cout << clac() << '\n';
    }
    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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// HDU 1085
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], b[N], c[N], d[N];
void clac(int m)
{
    for (int i = 0; i <= m; i++)
    {
        c[i] = d[i] = 0;
    }
    for (int i = 0; i <= a[1]; i++)
    {
        c[i] = 1;
    }
    for (int i = 2; i <= 3; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            for (int k = 0; k <= b[i] * a[i] && (j + k) <= m; k += b[i])
            {
                d[j + k] += c[j];
            }
        }
        for (int j = 0; j <= m; j++)
        {
            c[j] = d[j];
            d[j] = 0;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (1)
    {
        cin >> a[1] >> a[2] >> a[3];
        if (a[1] == 0 && a[2] == 0 && a[3] == 0)
        {
            break;
        }
        b[1] = 1, b[2] = 2, b[3] = 5;
        int m = a[1] * 1 + a[2] * 2 + a[3] * 5;
        clac(m);
        int x = 1;
        while (x <= m && c[x])
        {
            x++;
        }
        cout << x << '\n';
    }
    return 0;
}

指数生成函数

image-20230328155848886

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
// HDU 1521
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 10;
int n, m;
int a[N];
double c[N], d[N];
double fac[N];
void init()
{
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= 10; i++)
    {
        fac[i] = fac[i - 1] * i;
    }
}
double calc()
{
    for (int i = 0; i <= m; i++)
    {
        c[i] = d[i] = 0;
    }
    for (int i = 0; i <= a[1]; i++)
    {
        c[i] = 1.0 / fac[i];
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            for (int k = 0; k <= a[i]; k++)
            {
                d[j + k] += c[j] / fac[k];
            }
        }
        for (int j = 0; j <= m; j++)
        {
            c[j] = d[j];
            d[j] = 0;
        }
    }
    return c[m] * fac[m];
}
signed main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    init();
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        printf("%.0lf\n", calc());
    }
    return 0;
}

生成函数的应用

image-20230328160008438

image-20230328160023580

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
// https://darkbzoj.cc/problem/3028
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 10007;
int qpow(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string a;
    cin >> a;
    int n = 0;
    for (int i = 0; i < a.size(); i++)
    {
        n = (n * 10 % mod + a[i] - '0') % mod;
    }
    cout << n * (n + 1) % mod * (n + 2) % mod * qpow(6, mod - 2) % mod << '\n';
    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
// POJ 3734
#include <iostream>
using namespace std;
#define int long long
const int mod = 10007;
int ksm(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        cout << (ksm(4, n - 1) + ksm(2, n - 1)) % mod << '\n';
    }
}

狄利克雷卷积

image-20230329161526083

和式的变换

image-20230329161644649

image-20230329162008037

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
// luogu 3455
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 10;
int mu[N];
int p[N], vis[N];
int cnt;
void get_mu(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; i * p[j] <= n; j++)
        {
            int m = i * p[j];
            vis[m] = 1;
            if (i % p[j] == 0)
            {
                mu[m] = 0;
                break;
            }
            else
            {
                mu[m] = -mu[i];
            }
        }
    }
}
void init()
{
    get_mu(N);
    for (int i = 1; i <= N; i++)
    {
        mu[i] += mu[i - 1];
    }
}
int cal(int n, int m, int k)
{
    if (n > m)
    {
        swap(n, m);
    }
    n /= k, m /= k;
    int ans = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ans += (mu[r] - mu[l - 1]) * (n / l) * (m / l);
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int n;
    cin >> n;
    int a, b, d;
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b >> d;
        cout << cal(a, b, d) << '\n';
    }
    return 0;
}

image-20230329162214379

image-20230329162315906

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
// luogu 2257
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 10;
int mu[N];
int p[N], vis[N];
int cnt;
int F[N];
void init()
{
    mu[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; i * p[j] < N; j++)
        {
            int m = i * p[j];
            vis[m] = 1;
            if (i % p[j] == 0)
            {
                mu[m] = 0;
                break;
            }
            else
            {
                mu[m] = -mu[i];
            }
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = p[i]; j < N; j += p[i])
        {
            F[j] += mu[j / p[i]];
        }
    }
    for (int i = 1; i < N; i++)
    {
        F[i] += F[i - 1];
    }
}
int cal(int n, int m)
{
    if (n > m)
    {
        swap(n, m);
    }
    int ans = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ans += (F[r] - F[l - 1]) * (n / l) * (m / l);
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t;
    cin >> t;
    int a, b;
    while (t--)
    {
        cin >> a >> b;
        cout << cal(a, b) << '\n';
    }
    return 0;
}

image-20230329162407082

image-20230329162455494

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
// luogu 3327
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 10;
int mu[N];
int p[N], vis[N];
int cnt;
int F[N];
void init()
{
    mu[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; i * p[j] < N; j++)
        {
            int m = i * p[j];
            vis[m] = 1;
            if (i % p[j] == 0)
            {
                mu[m] = 0;
                break;
            }
            else
            {
                mu[m] = -mu[i];
            }
        }
    }
    for (int i = 1; i < N; i++)
    {
        mu[i] += mu[i - 1];
    }
    for (int i = 1; i < N; i++)
    {
        for (int l = 1, r; l <= i; l = r + 1)
        {
            r = i / (i / l);
            F[i] += (r - l + 1) * (i / l);
        }
    }
}
int cal(int n, int m)
{
    if (n > m)
    {
        swap(n, m);
    }
    int ans = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ans += (mu[r] - mu[l - 1]) * F[n / l] * F[m / l];
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t;
    cin >> t;
    int a, b;
    while (t--)
    {
        cin >> a >> b;
        cout << cal(a, b) << '\n';
    }
    return 0;
}

莫比乌斯反演

image-20230420181457681

image-20230420181725324

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
// luogu 1829
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 10;
const int mod = 20101009;
int vis[N], p[N], mu[N], S[N], cnt;
void init()
{
    mu[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; i * p[j] < N; j++)
        {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
    for (int i = 1; i < N; i++)
    {
        S[i] = (S[i - 1] + mu[i] * i * i % mod + mod) % mod;
    }
}
int G(int n, int m)
{
    return (n * (n + 1) / 2 % mod) * (m * (m + 1) / 2 % mod) % mod;
}
int F(int n, int m)
{
    int ans = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ans = (ans + (S[r] - S[l - 1]) * G(n / l, m / l) % mod + mod) % mod;
    }
    return ans;
}
int cal(int n, int m)
{
    if (n > m)
    {
        swap(n, m);
    }
    int ans = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ans = (ans + (r - l + 1) * (l + r) / 2 % mod * F(n / l, m / l) % mod) % mod;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    int n, m;
    cin >> n >> m;
    cout << cal(n, m) << '\n';
    return 0;
}

image-20230420181753495

image-20230420181907970

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
// https://www.luogu.com.cn/problem/P3704
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int prime[N], vis[N], mu[N];
int f[N], F[N];
int g[N];
int cnt;
int ksm(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void init()
{
    mu[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!vis[i])
        {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; i * prime[j] < N; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    f[1] = g[1] = 1;
    F[0] = F[1] = 1;
    for (int i = 2; i < N; i++)
    {
        f[i] = (f[i - 1] + f[i - 2]) % mod;
        g[i] = ksm(f[i], mod - 2);
        F[i] = 1;
    }
    for (int i = 1; i < N; i++)
    {
        for (int j = i; j < N; j += i)
        {
            if (mu[j / i])
            {
                F[j] = F[j] * (mu[j / i] == 1 ? f[i] : g[i]) % mod;
            }
        }
    }
    for (int i = 2; i < N; i++)
    {
        F[i] = F[i - 1] * F[i] % mod;
    }
}
int calc(int n, int m)
{
    if (n > m)
    {
        swap(n, m);
    }
    int ans = 1;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        int s = F[r] * ksm(F[l - 1], mod - 2) % mod;
        ans = ans * ksm(s, (n / l) * (m / l)) % mod;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        cout << calc(n, m) << '\n';
    }
    return 0;
}

欧拉定理幂级数取模

img

矩阵快速幂

image-20230504204621558

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, k;
struct matrix
{
    int c[101][101];
    matrix() { memset(c, 0, sizeof(c)); }
} A, ans;
matrix operator*(matrix &x, matrix &y)
{
    matrix t;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                t.c[i][j] = (t.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;
            }
        }
    }
    return t;
}
void quickpow(int k)
{
    // 初始化单位矩阵
    for (int i = 1; i <= n; i++)
    {
        ans.c[i][i] = 1;
    }
    while (k)
    {
        if (k & 1)
        {
            ans = ans * A;
        }
        A = A * A;
        k >>= 1;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> A.c[i][j];
        }
    }
    quickpow(k);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << ans.c[i][j] << " ";
        }
        cout << '\n';
    }
    return 0;
}