欧拉函数

欧拉函数是小于x的整数中与x互质的数的个数,一般用φ(x)表示。特殊的,φ(1)=1。
当n>1时，小于n的数中，与n互质的数的总和为：(φ(n)∗n)/2
若n互质的数有一个是m，那么还存在另一个数n−m也与n互质。
所以与n互质的数的平均数是n/2，而个数又是φ(n)，可以得到这些数的和就是(φ(n)∗n)/2
​

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N =1e5+10;
const ll mod = 1e9+7;

void deer()
{
    ll n,ans=2;
    cin>>n;

//[欧拉函数] 算出'比i小的'与i互素的'数的个数e[i]
    vector<ll> e(n+1);
    if(n==1)
    {
        cout<<0<<endl;
        return;
    }
    for(int i=1;i<=n;i++)   e[i]=i;
    for(int i=2;i<=n;i++)
    {
        if(e[i]==i)
        {
            for(int j=i;j<=n;j+=i)
            {
                e[j]=e[j]/i*(i-1);
            }
        }
    }

    for(int i=2;i<n;i++)    ans+=e[i]*2;
    cout<<ans+1<<endl;
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;
    while(t--)
    {
        deer();
    }

    return 0;
}

组合数

qqqqq1

求C(n,m)mod(1e9+7)
1<=m<=n<=2000

C(n,m)=C(n-1,m-1)+C(n-1,m)
O(n^2)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N =2e3+10;
const ll mod = 1e9+7;

int n,m;
int f[N][N];

void init()     //初始化C(n,m)
{
    for(int i=0;i<=2000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j)  f[i][j]=1;
            else    f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
        }
    }
}

void deer()
{
    cin>>n>>m;
    cout<<f[n][m]<<"\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;
    while(t--)
    {
        init();
        deer();
    }

    return 0;
}

qqqqq2

求C(n,m)mod(1e9+7)
1<=q<=1e5 1<=m<=n<=1e5

a/b mod p = a mod p * (b^-1) mod p
O(n log (p))

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

int f[N], inf[N];   //f[i]为 i的阶乘, inf[i]为 1/(i的阶乘)
int n, m;

int qmi(int x, int k, int p)    //快速幂，求 x^k
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * x % p;
        x = (ll)x * x % p;
        k >>= 1;
    }
    return res;
}

void init()
{
    f[0] = inf[0] = 1;
    for (int i = 1;i < N;i++)
    {
        f[i] = (ll)f[i - 1] * i % mod;
        inf[i] = (ll)inf[i - 1] * qmi(i, mod - 2, mod) % mod;       //费马小定理求逆元
    }
}

void deer()
{
    cin >> n >> m;
    cout << (ll)f[n] * inf[m] % mod * inf[n - m] % mod << "\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    int t = 1;
    cin >> t;
    while (t--)
    {
        deer();
    }

    return 0;
}

qqqqq3

求C(n,m)mod p
1<=q<=20 1<=m<=n<=1e18 1<=p<=1e5

–> 数论/Lucas定理
【模板】卢卡斯定理/Lucas定理

qqqqq4

求C(n,m)
1<=m<=n<=5000

没有取模操作，结果较大，需要高精度
分解质因数,高精度乘法
• 大于 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

int n, m;
vector<int> pri;    //小于n的素数
bool st[N];

void init(int x)
{
    for (int i = 2;i <= x;i++)
    {
        if (!st[i])
        {
            pri.push_back(i);
        }
        for (auto temp : pri)
        {
            if (temp * i > x)    break;
            st[temp * i] = true;
            if (i % temp == 0)   break;
        }
    }
}

int get(int x, int y)   //x!里面包含的y的次方 
{
    int res = 0;
    while (x)
    {
        res += x / y;
        x /= y;
    }
    return res;
}

/*
eg：5！ = 1 * 2 * 3 * 4 * 5
2*4=2^3
return res=3
*/

vector<int> mul(vector<int>ans, int x)  //高精度乘(ans*x)
{
    vector<int> tans;
    int res = 0;
    for (auto temp : ans)
    {
        res += temp * x;
        tans.push_back(res % 10);   //推进个位数
        res /= 10;
    }
    while (res)
    {
        tans.push_back(res % 10);   //将剩余的推进
        res /= 10;
    }
    return tans;
}

void deer()
{
    cin >> n >> m;
    init(n);
    vector<int> ans;
    ans.push_back(1);
    for (auto temp : pri)   //取素数
    {
        int sum = get(n, temp) - get(m, temp) - get(n - m, temp);   //temp的个数为sum
        for (int i = 0;i < sum;i++)
        {
            ans = mul(ans, temp);
        }
    }
    for (int i = ans.size() - 1;i >= 0;i--)
        cout << ans[i];

    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //    cin>>t;
    while (t--)
    {
        deer();
    }

    return 0;
}

卡特兰数

考点：
括号化
出栈次序P1044 [NOIP2003 普及组] 栈
凸多边形三角划分
给定节点组成二叉搜索树
n对括号正确匹配数目

卡特兰数（Catalan number）是 组合数学 中一个常出现在各种 计数问题 中的 数列。
​数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862，…
知乎

设h(n)为Catalan数的第n+1项，令h(0)=1,h(1)=1，Catalan数满足递推式：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2)

递推式：
h(1)=1,
h(n)=h(n-1)(4n-2)/(n+1)
h(n+1)=h(n)(4n+2)/(n+2)

递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=0,1,2,…)
h(n)=C(2n,n) - C(2n,n-1) (n=0,1,2,…)

P1375 小猫
属于凸多边形三角划分

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

ll n, ans = 1, x = 1, y = 1, z = 1;

ll pow(ll a, ll b)  //快速幂
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll mul(ll a, ll b)
{
    a %= mod;
    b %= mod;
    ll c = a * b / mod;
    ll ans = a * b - c * mod;
    if (ans < 0)   ans += mod;
    else if (ans >= mod)   ans -= mod;
    return ans;
}

void deer()
{
    cin >> n;
    for (ll i = 1;i <= 2 * n;i++)
    {
        if (i <= n)    y = mul(y, i);       //y*i    n!
        if (i <= n + 1)  z = mul(z, i);     //z*i    (n+1)!
        x = mul(x, i);      //x*i  (2n)!
    }
    y = mul(y, z);  //n!(n+1)!
    ans = mul(x, pow(y, mod - 2));   // x ^ (-y)       (2n)!/(n!(n+1)!)
    cout << ans << "\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin>>t;
    while (t--)
    {
        deer();
    }

    return 0;
}

容斥原理

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
oi-wiki

U381835 能被整除的数

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 20;
const ll mod = 1e9 + 7;

int n, m;
int pri[N];
int ans;

void deer()
{
    cin >> n >> m;
    for (int i = 0;i < m;i++)
    {
        cin >> pri[i];
    }
    for (int i = 1;i < 1 << m;i++)  //i<(2^m)
    {
        ll tmp = 1;
        int cnt = 0;
        for (int j = 0;j <= m;j++)
        {
            if ((i >> j) & 1)   // i/(2^j)
            {
                tmp *= pri[j];  //选中数字的乘积
                if (tmp > n)
                {
                    tmp = -1;
                    break;
                }
                cnt++;
            }
        }
        if (tmp == -1)
            continue;
        if (cnt % 2)
            ans += n / tmp;     //被tmp(选中数字乘积)整除的数字的交集
        else
            ans -= n / tmp;     //被tmp(选中数字乘积)整除的数字的交集
    }
    cout << ans << "\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //    cin>>t;
    while (t--)
    {
        deer();
    }

    return 0;
}

Nim游戏

公平组合游戏(ICG): 包括取数游戏，31 点，以及 Nim 游戏等
oi-wiki

【模板】Nim 游戏
n堆物品，每堆有a[i]个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。
取走最后一个物品的人获胜。

定理 1：没有后继状态的状态是必败状态。
定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

当所有堆石子数量的异或和为0时为先手必败状态，而所有堆石子数量的异或和不为0时为先手必胜状态

SG定理

Sprague–Grundy 定理(Sprague–Grundy Theorem), 简称 SG 定理
博弈论 | 详解搞定组合博弈问题的SG函数