QBXT五一数学

Qinzh · 2023-04-29 18:39:45 · 个人记录

zhx好闪，拜谢zhx 本人LaTeX存在问题,下课修改(

Day 1

上午

电脑1s跑3e8()

mod

例1

读入n, p,输出n! % p
2 <= p <= 1e9, 1 <= n <= 1000;

ll n = read(), p = read();
ll ans = 1;
if(n >= p){
    cout << 0;
    return 0;
}
for(int i = 2; i <= n; ++i)ans = (ans * i) % p;
cout << ans % p;

gcd & lcm

设 g = \gcd(a, b), a = a'g, b = b'g

代码
ll gcd(ll a, ll b){return a ? gcd(b % a, a) : b;}

时间复杂度O(log n)

证明：

证明：

分类讨论

b <= a / 2时， a % b < b <= a / 2;

a >= b > a / 2时，a % b = a - b < a / 2;

所以每次 gcd 相当于将 a 除以 2

所以 O(\log n)

例1

求gcd(a1, a2, ..., an)

int n = read(), ans;
for(int i = 1; i <= n; ++i)a[i] = read();
ans = a[1];
for(int i = 2; i <= n; ++i)ans = gcd(ans, a[i]);
cout << ans << "\n";

时间复杂度：

所以最多除 \log{ans} 次

设 g = \gcd(a, b), l = lcm(a, b)

代码

ll lcm(int a, int b){return a / gcd(a, b) * b;}

快速幂

例: y = 37 时

时间复杂度O(\log y)

代码
通用版(循环)
ll qpow(ll a, ll b, ll p){
    if(b == 0)return 1;
    ll res = 1;
    while(b){
        if(b & 1)res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}
zhx版(递归)
ll ksm(ll x, ll y, ll p){
    if(y == 0)return 1;
    if(y == 1)return a;
    ll z = ksm(x, y >> 2, p);
    return z * z * (y & 1 ? x : 1) % p
}

例1

x, y, p <= 10 ^ 18
求x * y % p
直接求x * y达到10 ^ 36存不下
例 y = 37 用快速幂思想
x * y = x * 37 = x + x + .. = x
x * 37 = x * 18 + x * 18 + x
x * 18 = x * 9 + x * 9
x * 9 = x * 4 + x * 4 + x
x * 4 = x * 2 + x * 2
x * 2 = x + x

代码
ll ksc(ll x, ll y, ll p){
    if(y == 0)return 0;
    if(y == 1)return x;
    ll z = ksc(x, y >> 2, p);
    return (z + z + (y & 1 ? x : 0)) % p
}

矩阵

大抵可以看做一个二维数组 被迫使用 \LaTeX( 矩阵加法与减法

矩阵减法同理

矩阵乘法

只有第一个矩阵的列数等于第二个矩阵的行数才行

代码：

struct Matrix{
    ll a[105][105];//自行开空间 
    int n, m;
    Matrix() {memset(a, 0, sizeof a);}
    Matrix operator * (const Matrix &A, const Matrix &B){//& 直接调用A, B.const 防止 A, B 被修改 
        Matrix Ans;
        int n = A.n, m = B.m;
        Ans.n = n, Ans.m = m;
        for(int i =1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                for(int k = 1; k <= A.m; ++k)
                    Ans.a[i][j] += A.a[i][k] * B.a[k][j];
        return Ans;
    }
};

时间复杂度 O(n \cdot m ^ 2)

所以循环顺序改成 i, k, j ( j 放在最后一位即可) 利用缓存机制

下午

例1

给定 n, p， 求斐波那契数列第 n 项 \bmod p

数组 f 代表 fib 数列

手推可得

令

矩阵乘法套快速幂即可

#include<bits/stdc++.h>
#define ll long long
#define itn int
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
const ll M = 1e9 + 7;
ll n;
struct Matrix{
    ll a[105][105];//自行开空间 
    int n, m;
    Matrix() {memset(a, 0, sizeof a);}
}ans, base;
Matrix operator * (const Matrix &A, const Matrix &B){//& 直接调用A, B.const 防止 A, B 被修改 
        Matrix Ans;
        int n = A.n, m = B.m;
        Ans.n = n, Ans.m = m;
        for(int i =1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                for(int k = 1; k <= A.m; ++k)
                    Ans.a[i][j] = (Ans.a[i][j] + A.a[i][k] * B.a[k][j]) % M, Ans.a[i][j] %= M;
        return Ans;
    }
void init(){
    base.n = base.m = 2, ans.n = 2, ans.m = 2;
    base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
    ans.a[1][1] = ans.a[1][2] = 1;
}
void qpow(ll b){
    while(b){
        if(b & 1)ans = ans * base;
        base = base * base;
        b >>= 1;
    }
}
int main(){
    n = read();
    if(n <= 2)return puts("1"), 0;
    init();
    qpow(n - 2);
    cout << ans.a[1][1] % M << "\n";
    return 0;
}

例2

一个数列 f_{i} = f_{i - 1} \times f_{i - 3}

仍然手推可得

令

扩展

已知 f_i=k_{1}f_{i-1}+k_{2}f_{i-2}....+k_{m}f_{i-m+1}(m\le i)

求f_n \bmod p(1\le n\le 10^{18})

构造矩阵

即可得出答案

矩阵乘法中

例3

一个有向图， n 个点，走 k 步， 求从 1 走到 n 的方案数

考虑动态规划

令 bj_{i,j} 表示 i 与 j 之间是否连边, f_{i,j} 表示走到 j 走了 i 步的方案数

所以答案即为 f_{k,n}

初始状态为 f_{0,1} = 1

状态转移为 f_{i,j} += \sum_{k = 1}^nf_{i-1,k} \times bj_{k,i}

部分代码:

n = read(), k = read();
for(int i = 1; i <= n; ++i)bj[i][j] = read();
f[0][1] = 1;
for(int a = 1; a <= k; ++a)
    for(int b = 1; b <= n; ++b)
        for(int c = 1; c <= n; ++c){
        //走了a步,走到了b,第a - 1步在c
            f[a][b] += f[a - 1][c] * bj[c][b];
        }
cout << f[k][n];

强行加一维

n = read(), k = read();
for(int i = 1; i <= n; ++i)bj[i][j] = read();
f[0][1][1] = 1;
for(int a = 1; a <= k; ++a)
    for(int d = 1; d <= n; ++d)
        for(int b = 1; b <= n; ++b)
            for(int c = 1; c <= n; ++c){
            //走了a步,走到了b,第a - 1步在c
                f[a][d][b] += f[a - 1][d][c] * bj[c][b];
            }
cout << f[k][1][n];

提出 f_{a,d,b} += f_{a-1,d,c} \times bj_{c,b}

改为 f_{a_{d,b}} += f_{(a-1)_{d,c}} \times bj_{c,b}

然后将 f_a, f_{a - 1}, bj 当做 n 行 n 列矩阵

所以 f_a = f_{a - 1} \times bj

即得 f_k = f_0 \times bj ^ k

套矩阵快速幂

时间复杂度 O(\log {n ^ 3 \log k})

例4

LuoguP4159

比例 4 多了路径长度罢了

把每一条边拆成由几个长度为一的边组成的链

然后由同一个点引出来的链可以合并

代码晚上补(

#include<bits/stdc++.h>
#define ll long long
#define itn int
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
const ll M = 2009;
ll n, m;
struct Matrix{
    ll a[105][105];//自行开空间 
    int n, m;
    Matrix() {memset(a, 0, sizeof a);}
}ans, f;
Matrix operator * (const Matrix &A, const Matrix &B){//& 直接调用A, B.const 防止 A, B 被修改 
        Matrix Ans;
        Ans.m = Ans.n = m; 
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= m; ++j)
                for(int k = 1; k <= m; ++k)
                    Ans.a[i][j] = (Ans.a[i][j] + A.a[i][k] * B.a[k][j]) % M, Ans.a[i][j] %= M;
        return Ans;
    }
void qpow(ll b){
    while(b){
        if(b & 1)ans = (ans * f);
        f = f * f;
        b >>= 1;
    }
}
int main(){
    n = read();int t = read();
    m = 9 * n;
    ans.n = ans.m = f.n = f.m = 9 * n;
    for(int i = 1; i <= n; ++i){
        string s;
        cin >> s;
        for(int j = 1; j <= 8; ++j){
            f.a[i + j * n][i + j * n - n] = 1; 
            ans.a[i + j * n][i + j * n - n] = 1;
        }
        for(int j = 1; j <= n; ++j){
            int v = s[j - 1] - '0';
            if(v) f.a[i][j + v * n - n] = 1, ans.a[i][j + v * n - n] = 1;
        }
    }
    qpow(t - 1);
    cout << ans.a[1][n] % M;
    return 0;
}

质数判定

初等数论: 自然数范围

质数 : 只有自己和 1 为因子的数

合数 : 有大于 2 个因子的数

给定 x 分解质因数.(不能用筛)

void factorize(int x){
 int cnt = 0;
    for(int a = 2; a * a <= x; ++a){
        if(x % a == 0){
            ++cnt;
            prime[cnt] = a;
            while(x % a == 0){
                ++num[cnt];
                x /= a;
            }
        }
    }
    if(x != 1){
        ++cnt;
        prime[cnt] = x;
        num[cnt] = 1;
    }
}

对于 a 第一次合条件时显然一定是质数,然后 x 除掉 a 直到不能再除,以后的 a 符合条件时也一定为质数

而对于特判,意思是如果x本身是质数就需要只输出 x 而循环不会记录 x 只能特判

例1

现有 1\backsim n, 将它们分为几组,使得每组内之和都为质数,求最少分几组.

由哥德巴赫猜想知,大于等于 4 的偶数,可分为两个质数的和, 大于等于 3 的奇数,可分为 3 个质数的和

令 x = \sum_{i = 1}^n i = \frac{n \times (n + 1)}{2}

若 x 为偶数,输出 2 ,若 x 为奇数则分类讨论

若 x - 2 等于 0 则输出 2 ,否则输出 3

#include<bits/stdc++.h>
#define ll long long
#define itn int
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
bool check(int n){
    if(n <= 1)return 0;
    for(int i = 2; i * i <= n; ++i)if(n % i == 0)return 0;
    return 1;
}
int a[6005];
int main(){
    int n = read();
    int x = n * (n + 1) / 2;
    if(n == 1)return puts("-1"), 0;
    if(n == 2)return puts("1 1"), 0;
    if(n == 3)return puts("1 1 2"), 0;
    for(int i = 1; i <= n; ++i){
        a[i] = 1;
    }
    if(x & 1){
        if(check(x - 2)){
            a[2] = 2;
            for(int i = 1; i <= n; ++i)cout << a[i] << ' ';
        }
        else{
            a[3] = 3;
            for(int i = 1; i <= n; ++i)if(check(i) && check(x - 3 - i)){
                a[i] = 2;
                break;
            }
            for(int i = 1; i <= n; ++i)cout << a[i] << ' ';
        }
    }
    else{
        for(int i = 1; i <= n; ++i)if(check(i) && check(x - i)){
            a[i] = 2;
            break;
        }
        for(int i = 1; i <= n; ++i)cout << a[i] << ' ';
    }
    return 0;
}

Day 2

上午

逆元

逆元:对于 a \div b \bmod p 找到一个整数 c ,使得 a \div b \bmod p = a \times c \bmod p

费马小定理:

当 p 为质数,且 1 \le a < p, a ^ {p - 1} \equiv 1 (\bmod p)

即得: a ^ {p - 2} \equiv \frac{1}{a} (\bmod p)

此时 a ^ {p - 2} 即为 a 在 \bmod p 意义下的逆元

inline void inv(ll a, ll b, ll p){return 1ll * a * ksm(b, p - 2, p) % p}

这个方法只适合于 p 是质数 ,且 \gcd(a, p) = 1

欧拉定理:

当 p 为质数时, \phi(p) = p - 2 ,所以费马小定理是欧拉定理的特殊情况.

求 \phi (n):

若 n = p_1, \phi(n) = p_1 - 1

ll getphi(ll n){
    ll phi = n;
    for(int i = 2; i* i <= n; ++i){
        if(n % i == 0){
            phi = phi / i * (i - 1);
            while(n % i == 0)
                n = n / i;
        }
    }
    if(n != 1)phi = phi / n * (n - 1);
    return phi;
}

例1

LuoguP3811

给定 n, p ,求 1 \backsim n 中每个数 \bmod p 意义下的逆元

然后从 (n - 1) \backsim 1 推, \frac{1}{i!} = \frac{1}{(i + 1)!} \cdot (i + 1)

求出阶乘逆元 facinv[i]

然后逆元 \frac{1}{i} = (i - 1)! \cdot \frac{1}{i!}

cin >> n >> p;
fac[0] = 1;//阶乘
for(int i = 1; i <= n; ++i)
    fac[i] = 1ll * fac[i - 1] * i % p;
facinv[n] = ksm(fac[n], p -2, p);//阶乘逆元
for(int i = n - 1; i >= 1; --i)
    facinv[i]= 1ll * facinv[i + 1] * (i + 1) % p;
for(int i =1; i <= n; ++i)//逆元
    inv[i] = 1ll * fac[i - 1] * facinv[i] % p;

法二

假设 inv_1 \backsim inv_{i - 1} 都已经求出, inv_i = ?

所以 0 \equiv ki + r (\bmod p)

有一个 a ,1 \le a < n 使得

1. a ^ d \bmod n = 1

2. 存在 0 \le i < r, a^{d \times 2 ^ i} \bmod n = n - 1

int exgcd(int a, int b, int &x, int &y){
    //求g = gcd(a, b)以及 xa + yb = g
    if(!b){x = 1, y = 0; return 0;}
    int xp, yp;
    int g = exgcd(b, a % b, xp, yp);
    //xp * b + yp * (a % b) = g
    //xp * b + yp * (a - b * (a / b)) = g
    //xp * b + yp * a - yp * b * (a / b) = g
    //yp * a + (xp - yp *(a/b)) * b = g
    x = yp;y = xp - yp * (a / b);
    return g;
}

裴蜀定理

对于 xa + yb (x, y\in Z) 能表示的最小正整数为 \gcd(a, b)

例1

LuoguP1082

变为 ax + by = \gcd(a, b)

#include<bits/stdc++.h>
#define ll long long
#define itn int
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
ll n, p ,x, y;
void exgcd(ll a, ll b){
    if(!b)x = 1, y = 0;
    else exgcd(b, a % b), swap(x, y), y -= a / b * x;
}
int main(){
    n = read(), p = read();
    exgcd(n, p);
    cout << (x % p + p) % p << "\n";
    return 0;
}

下午

例2

中国剩余定理(CRT)/(ExCRT)

LuoguP1495

LuoguP4777

法一(大数翻倍):

首先，对于 x\equiv 1(\bmod 3), x\equiv 1( \bmod 5)

设 t = lcm(3,5)

发现 2 个同余方程可以合并:

如何合并成 x \equiv a( \bmod p):

令 x = a_1, 不断加上 p_1 , 次数加过 p_2 , 则无解

最后，p = lcm(p_1, p_2)，a=x ，合并完毕，时间复杂度 O(p_2)。

void solve(int p1, int a1, int p2, int a2, int &p, int &a){
    if(p1 < p2)swap(p1, p2),swap(a1, a2);//优化为O(min(p1, p2))
    int x = a1, g = gcd(p1, p2), l = p1 / g * p2;
    while(x <= l && x % p2 != a2)x += p1;
    if(x > l)p = a = -1;
    else p = l, a = x;
}

法二(ExGcd):

设 x = k_1 \times p_1 + a_1 = k_2 \times p_2 + a_2

void solve(int p1, int a1, int p2, int a2, int &p, int &a){
    int g, k1, k2;
    g = exgcd(p1, p2, k1, k2);
    k2 = -k2;
    if((a2 - a1) % g != 0)p = -1, a = -1;
    else{
    int k = (a2 - a1) / g;
        k1 = k1 * k, k2 = k2 * k;
        int x = k1 * p1 + a1;
        p = p1 / g * p2;
        a = (x % p + p) % p;
    }
}

大数翻倍完整代码:

#include<bits/stdc++.h>
#define ll __int128
#define itn int
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}

long long a[100005], p[100005];
int n;
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){x = 1, y = 0; return a;}
    ll d = exgcd(b, a % b, y, x); y -= (a / b) * x;
    return d;
}
ll gcd(ll a, ll b){return a ? gcd(b % a, a) : b;}
void solve(ll p1, ll a1, ll p2, ll a2, ll &p, ll &a){
    if(p1 < p2)swap(p1, p2),swap(a1, a2);//优化为O(min(p1, p2))
    ll x = a1, g = gcd(p1, p2), l = p1 / g * p2;
    while(x <= l && x % p2 != a2)x += p1;
    if(x > l)p = a = -1;
    else p = l, a = x;
}
int main(){
    n = read();
    for(int i = 1; i <= n; ++i)p[i] = read(), a[i] = read(), a[i] %= p[i];
    for(int i = 2; i <= n; ++i){
        ll ta, tp;
        solve(p[i - 1], a[i - 1], p[i], a[i], tp, ta);
        if(tp != -1 && ta != -1)p[i] = tp, a[i] = ta;
    }
    cout << a[n];
    return 0;
}

筛法

给定 n 个数,从小到大输出 1 \backsim n 中的质数

暴力,枚举每个数 O(n\sqrt n)

埃氏筛:

for(int a = 2; a <= n; ++a)
    for(int b = a + a; b <= n; b += a)
        nop[b] = 1;

for(int a = 2; a <= n; ++a)
    if(nop[a] == 0)p[++cnt] = a;

复杂度为 O(\frac{n}{1} + \frac{n}{2} + ... \frac{n}{n})

调和级数, \approx O(n \log {n})

优化:

for(int a = 2; a <= n; ++a)
    if(nop[a] == 0)
        for(int b = a + a; b <= n; b += a)
            nop[b] = 1;

复杂度 O(n\log{\log{n}})

线性筛&欧拉筛

void Ola(){
    for(int i = 2; i <= n; ++i){
        if(nop[i] == 0)p[++cnt] = i;
        for(int j = 1; j <= cnt; ++j){//筛掉第j个质数的i倍
            int x = p[j] * i;
            if(x > n)break;
            nop[x] = 1;
            if(i % p[j] == 0)break;//保证每个数只被最小质因子筛掉
        }
    }
}

时间复杂度 O(n)

积性函数

积性函数: 当 \gcd(a, b) = 1 时, f(a)f(b) = f(ab)

例子: \phi(x)

线性预处理 \phi(x)

void Ola(){
    for(int i = 2; i <= n; ++i){
        if(nop[i] == 0)p[++cnt] = i, phi[i] = i - 1;
        for(int j = 1; j <= cnt; ++j){
            int x = p[j] * i;
            if(x > n)break;
            nop[x] = 1;
            phi[x] = phi[p[j]] * phi[i];
            if(i % p[j] == 0){
                phi[x] = p[j] * phi[i];
                break;
            }
        }
    }
}

Day 3

上午

baby step giant step算法(北上广深算法)

给定 a, b, p 求解 a ^ x \bmod p = b

暴力容易写出 O(x)

//此文章第1145行(
int solve (int a, int b, int p){
    ll v = 1;
    for(int x = 0; ; ++x){
    if(v == b)return x;
        v = 1ll * v * a % p;
        f(v == 1)return -1;
    }
}

由费马小定理知:

所以

可得循环节只有 p - 1 的长度

修改为 O(p - 1)

int solve (int a, int b, int p){
    ll v = 1;
    for(int x = 0; x < p - 1; ++x){
    if(v == b)return x;
        v = 1ll * v * a % p;
        f(v == 1)return -1;
    }
}

查看第一组是否有解,若有,则跳出循环,否则查看第二组......

和暴力复杂度其实一样

我们可以发现如果 b 在第二组中出现,则一定在第一组中有 b \cdot a^{-s} 出现,

如果 b 在第二组中出现,则一定在第一组中有 b \cdot a^{-2s} 出现

...

所以可以检查第一组得到解, 有分块的思想

代码

int solve (int a, int b, int p){
    int s = sqrt(p);
    int v = 1;
    set<int> se;//集合STL
    for(int i = 0; i < s; ++i){
        se.insert(v);
        v = 1ll * v * a % p;
    }
    //O(p/s)
    for(int i = 0; i * s <= p; ++i){//检查答案是否在第i行 
    //看b * a ^ (-i* s) 是否在第0行出现
        int c = 1ll * b * ksm(ksm(a, i * s, p), p - 2, p) % p;
        if(se.count(c) != 0){
            int v = ksm(a, i * s, p);//第i行第一个数
            for(int j = i * s; ; ++j){//最坏O(s)
                if(v == b)return j;
                v = 1ll * v * a % p;
            } 
        }
    } 
    //总 : O(max(s, p/s)); 即得s = sqrt(p)最合适 
    //所以时间复杂度 O(sqrt(p)) 
    return -1;
}
//1234行(

时间复杂度 O(\sqrt p) (分块复杂度

例1

LuoguP3846 模板,见代码:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
ll ksm(ll a, ll b, ll p){
    if(b == 0)return 1; 
    ll ans = 1;
    while(b){
        if(b&1)ans = ans * a % p;
        b >>= 1;
        a = a * a % p; 
    }
    return ans;
}
ll solve(ll a, ll b, ll p){
    int s = sqrt(p);
    int v = 1;
    set<int> se;
    for(int i = 0; i < s; ++i){
        se.insert(v);
        v = 1ll * v * a % p;
    }
    for(int i = 0; i * s <= p; ++i){
        int c = 1ll * b * ksm(ksm(a, i * s, p), p - 2, p) % p;
        if(se.count(c) != 0){
            int v = ksm(a, i * s, p);
            for(int j = i * s; ; ++j){
                if(v == b)return j;
                v = 1ll * v * a % p;
            }
        }
    }
    return -1;
}
int main(){
    int p, b, n;
    cin >> p >> b >> n;
    ll ans = solve(b, n, p);
    if(ans == -1)cout << "no solution";
    else cout << ans;
    return 0;
}

组合数学

组合睡学(

核心: 计数, 方案数

加法原理 : 从 A 到 B 上面 3 条路,下面 2 条路,总共 5 种方案 (同一阶段内加)

乘法原理 ; 从 A 到 B 有 3 条路, B 到 C 有 2 条路, A 到 C 有 6 种方案 (不同阶段内乘)

排列: n 个人选 m 个人, 考虑 m 个人的顺序

第 1 个人有 n 种选法

第 2 个人有 n - 1 种选法

第 m 个人有 n - m + 1 种选法,

组合: n 个人选 m 个人, 不考虑 m 个人的顺序

组合数一些式子:

1. 一个都不选或者全选,只有一种做法:

   \binom{n}{0} = 1 = \binom{n}{n}

2. 选 m 个或者选 n - m 个丢掉实质一样:

   \binom{n}{m} = \binom {n}{n - m}

3. 选 m 个, 考虑分情况讨论:: 1) 选第 1 个物品, 还需要从剩下的 n - 1 中选 m - 1个

   2) 不选第 1 个物品, 还需要从剩下的 n - 1 中选 m个

   \binom{n}{m} = \binom{n - 1}{m - 1} + \binom {n - 1}{m}

   预处理求所有的组合数

for(int i = 0; i <= n; ++i){
    c[i][0] = 1;
    for(int j = 1; j <= i; ++j)
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}

此时的 C 数组是个杨辉三角形

4. 选任意多个物品:

   \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + ... +\binom{n}{n} = 2 ^ n
5. n \ge 1 \binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\binom{n}{3}+... \pm \binom{n}{n} = 0

   由第 3 个式子可得,所有奇数位置的和等于杨辉三角中上一行的和,所有偶数位置的和也等于杨辉三角上一行的和都等于 2^{n - 1}

   所以奇数位置之和与偶数位置之和之差为 0

观察系数,发现是杨辉三角

即为

例1

就可以看做

的解的个数 = \binom{n + m-1}{m}

例2

求 \binom{n}{m} \bmod p

1.n,m \le 10^{18}, p = 1

2.n, m \le 1000, p 随意

用杨辉三角递推O(nm)

for(int i = 0; i <= n; ++i){
    c[i][0] = 1;
    for(int j = 1; j <= i; ++j)
        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
}
cout << c[n][m];

LuoguP2822

代码下课补(

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
ll t, k;
ll c[2005][2005], qzh[2005][2005];
int main(){
    t = read(), k = read();
    memset(c, -1, sizeof c);
    for(int i = 0; i <= 2000; ++i){
        c[i][0] = 1;
        for(int j = 1; j <= i; ++j){
            c[i][j] = (max(c[i - 1][j - 1], (ll)0) + max(c[i - 1][j],(ll)0)) % k;
        }
    }
    for(int i = 1; i <= 2000; ++i){
        for(int j = 1; j <= 2000; ++j){
            qzh[i][j] = qzh[i - 1][j] + qzh[i][j - 1] - qzh[i - 1][j - 1];
            if(c[i][j] == 0)qzh[i][j]++;
        }
    }
    for(int i = 1; i <= t; ++i){
        int n = read(), m = read();
        cout << qzh[n][m] << "\n";
    }
    return 0;
}

3.n,m \le 10^6, p 为质数

逆元 O(n\log p)

fac[0] = 1;
for(int i = 1; i <= 1000000; ++i)fac[i] = 1ll * fac[i - 1] * i % p;
cout << fac[n] * ksm(fac[m], p - 2, p) % p * ksm(fac[n - m], p - 2, p) % p;

下午

4.n \le 10^9, m \le 10^3

然后把分母约为 1, 分子乘起来即可 O(m^2\log m)

for(int i = 1; i <= m; ++i){
    fenzi[i] - i;
    fenmu[i] - n - i + 1; 
}
for(int i = 1; i <= m; ++i){
    for(int j = 1; j <= m; ++j){
        int g = gcd(fenzi[i], fenmu[j]);
        fenzi[i] /= g;
        fenmu[j] /= g;
    }
} 
int ans =1;
for(int i = 1; i <= m; ++i)ans = 1ll * fenzi[i] % p;

5.n, m \le 10 ^ 9, p \le 100 为指数

int lucas(int n, int m, int p){
    while(n){
        ++x[0];
        x[x[0]] = n % p;
        n = n / p;
    }//n的p进制表示 
    while(m){
        ++y[0];
        y[y[0]] = m % p;
        m = m / p;
    }
    int ans = 1;
    for(int i = 1; i <= x[0]; ++i)
        ans = 1ll * ans * c[x[i]][y[i]] % p;
    return ans; 
}
int main(){
    cin >> n >> m >> p;
    for(int i = 0; i <= p; ++i){
        c[i][0] = 1;
        for(int j = 1; j <= i; ++j){
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
        }
    }
    return 0;
}

LuoguP3807

卢卡斯定理只适用于 p 为质数, 当 p 不为质数时, 将其质因数分解

然后中国剩余定理合并, 计算可得

例3

将 x 拆为 k 个不同组合数之和

酱汁构造(

例4

比较 \binom{n1}{m1} 与 \binom{n2}{m2} 大小

fac[0] = 0;
for(int i  =1; i <= 1000000; ++i){
    fac[i] = fac[i - 1] + log(i); 
}
double logcnm(int n, int m){
    return fac[n] - fac[m] - fac[n - m];
}

例5

找到 k 个不同的组合数,使得这 k 个组合数之和最大

对于每个组合数 \binom{a}{b}, a, b \le n

观察杨辉三角

最底层中间的数最大, 往外扩散逐渐减小

单调队列, 结构体重载运算符

代码晚上补(

例6

LuoguP3746

展开 k 次

令

矩阵快速幂

代码晚上能补出来?(

#include<bitsdc++.h>
#define ll long long
#define itn int
#define ull unsigned long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
ll n, p, k, r;
struct Matrix{
    ll a[55][55];//自行开空间 
    int n, m;
    Matrix() {memset(a, 0, sizeof a);}
}ans, base;
Matrix operator * (const Matrix &A, const Matrix &B){//& 直接调用A, B.const 防止 A, B 被修改 
        Matrix Ans;
        Ans.n = A.n, Ans.m = B.m;
        for(int i = 0; i < A.n; ++i)
            for(int j = 0; j < B.m; ++j)
                for(int k = 0; k < A.m; ++k)
                    Ans.a[i][j] = (Ans.a[i][j] + A.a[i][k] % p * B.a[k][j] % p) % p, Ans.a[i][j] %= p;
        return Ans;
    }
void ksm(ll b){
    while(b){
        if(b & 1)ans = ans * base;
        base = base * base;
        b >>= 1;
    }
}
void init(){    
    ans.a[0][0] = 1;
    ans.n = base.n = base.m = k, ans.m = k;
    for(int i = 0; i < k; ++i){
        base.a[i][i] = 1;
        base.a[i][(i + 1) % k]++;
    }
}
int main(){
    n = read(), p = read(), k = read(), r = read();
    init();
    ksm(n * k);
    cout << ans.a[0][r];
    return 0;
}

抽屉原理

用前缀和做:

将每个元素 \bmod c 后的结果分类 0, 1, 2, ..., c - 1

据抽屉原理知一定有同类的结果, 即得答案

代码等补(

例2

平面上 n 个点 (x_i, y_i)

用三个大小为 L \times L 的正方形覆盖住所有点

求最小的 L

显然二分答案, 如何写 check 函数

得到这些点 x, y 的最大最小值,用最小的矩形框住所有点

先用一个正方形盖住一角, 将剩下的点继续用最小矩形框住,再用一个正方形盖住一角,最后检查剩下的点能否盖住即可.

check中循环 4 \times 4.

代码晚上补啊啊啊啊啊啊啊啊啊啊

容斥

设 A_1 为学语文的人的集合, A_2 为学数学的人的集合, A_3 为学英语的人

同时学语文和数学的人: A_1 \bigcap A_2

学语文或数学的人: A_1 \bigcup A_2

例1

Day 4

上午

坐成一圈, 答案 \frac{(2n)!}{2n - 1} = {(2n - 1)}!

这样,所有不合法方案一定被减掉,但是, 有可能减多次

所以要减去 \sqrt[6]{n} 保证不重

#include<cmath>

cin >> n;
for(int a = 2; a <= 64; ++a){
    num[a] = 0;//代表x^a 这种形式的数算了几次 
}
for(int a = 2; a <= 64; ++a){
    //pow(x, y) = x ^ y;
    //pow(x, 0.5) = sqrt(x);
    ll v = floor(powl(n, 1.0 / a)) - 1;
    int d = 1 - num[a];
    ans += v * d;
    num[a] += d;
    for(int b = a; b <= 64; b += a){
        num[b] += d;
    } 
} 
cout << ans + 1;//补上1 

LuoguP9118

矩阵

解方程:

消元即可

如何求 n 元一次方程

高斯消元

......

消掉 x_1

剩下 n - 1 个方程和未知数.....

再不断消掉其他的位置数,只剩一个未知数和方程,然后回带

变成

变成

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
double a[105][105];
int n;
double x[105];
void Gauss(){
    for(int i = 1; i <= n; ++i){
        //把xi从第i+1到第n个方程中消掉
        for(int j = i; j <= n; ++j){
            if(fabs(a[j][i]) > fabs(a[i][i])){//主元消元法
                swap(a[i],a[j]);
                break;
            }
        }
        for(int j = i + 1; j <= n; ++j){//把xi从第j个方程中消掉 
            double ratio = a[j][i] / a[i][i];
            for(int k = 1; k <= n + 1; ++k){
                a[j][k] -= a[i][k] * ratio;
            } 
        } 
    }
    for(int i = n; i >= 1; --i){
        for(int j = i + 1; j <= n; ++j)
            a[i][n + 1] -= a[i][j] * x[j]; 
        x[i] = a[i][n + 1] / a[i][i];
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j)
            cin >> a[i][j];
        cin >> a[i][n + 1];
    }
    Gauss();
    //a[1][1] * x[1] + a[1][2] * x[2] + ... + a[1][n] * x[n] = a[1][n + 1];
    //a[2][1] * x[1] + a[2][2] * x[2] + ... + a[2][n] * x[n] = a[2][n + 1];
    // ............................................................
    //a[n][1] * x[1] + a[n][2] * x[2] + ... + a[n][n] * x[n] = b[n][n + 1];
    for(int i = 1; i <= n; ++i){
        printf("%.2lf\n", x[i]);
    }
    return 0;
}

可以用最小公倍数做, 避免精度问题

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[105][105];
int n;
double x[105];
void Gauss(){
    for(int i = 1; i <= n; ++i){
        //把xi从第i+1到第n个方程中消掉
        for(int j = i; j <= n; ++j){
            if(fabs(a[i][j] != 0)){//实数判断是否为0 
                swap(a[i],a[j]);
                break;
            }
        }
        for(int j = i + 1; j <= n; ++j){//把xi从第j个方程中消掉 
            if(a[j][i] == 0)continue;
            int l = a[i][i] / gcd(abs(a[i][i]),abs(a[j][i])) * a[j][i];
            int ratioi = l / a[i][i];
            int ratioj = l / a[j][i];
            for(int k = 1; k <= n + 1; ++k)
                a[j][k] = a[j][k] * ratioj - a[i][k] * ratioi;
        } 
    }
    for(int i = n; i >= 1; --i){
        for(int j = i + 1; j <= n; ++j)
            a[i][n + 1] -= a[i][j] * x[j]; 
        x[i] = (double)a[i][n + 1] / a[i][i];
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j)
            cin >> a[i][j];
        cin >> a[i][n + 1];
    }
    Gauss();
    //a[1][1] * x[1] + a[1][2] * x[2] + ... + a[1][n] * x[n] = a[1][n + 1];
    //a[2][1] * x[1] + a[2][2] * x[2] + ... + a[2][n] * x[n] = a[2][n + 1];
    // ............................................................
    //a[n][1] * x[1] + a[n][2] * x[2] + ... + a[n][n] * x[n] = b[n][n + 1];
    for(int i = 1; i <= n; ++i){
        printf("%.2lf\n", x[i]);
    }
    return 0;
}

单位矩阵 I :

若

则 B 为 A 的倒数

若 A \cdot B = C 则 C_{i,j} = \sum_{k = 1}^{n}A_{i,k} \cdot B_{k, j}

就有 n ^ 2 个未知数和方程, 高斯消元求解 B, 时间复杂度 O(n^6)

所以矩阵可以高斯消元消成单位矩阵,在消元过程中相当于矩阵乘 B

下午

概率和期望

事件

扔一个骰子

样本空间: 1,2,3,4,5,6

样本点组合成事件

则 P(A)= \frac{1}{2}

减法: 把 A 中出现在 B 中的元素删掉

概率

概率定义：为样本空间的每一个事件定义一个实数，这个实数称为概率

事件的概率等于它所包含的样本点的概率之和

公式1: P(A|B) = \frac{P(AB)}{P(B)}

公式2: P(A|B)P(B) = P(AB)

独立事件 : 两个事件 A, B,A 的发生不影响 B 的发生, B 也不影响 A

即: P(A)P(B) = P(AB), P(A) = P(A|B)

扔两次骰子,第一次与第二次互相不影响,互为独立事件

期望

扔骰子: 1,2,3,4,5,6

数的期望: 1,2,3,4,5,6

概率:\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6}

期望值: 1 \times \frac{1}{6} + 2\times \frac{1}{6} + 3\times \frac{1}{6} + 4\times \frac{1}{6} + 5\times \frac{1}{6} + 6\times \frac{1}{6} = \frac{7}{2}

数的平方的期望 1,4,9,16,25,36

此时的期望值 \frac{91}{6}

期望的和 等于和 的期望

例1

三张一样的卡, 其中一张两面黑,一张两面红,一张一面红一面黑

随机抽取一张放在桌子上,红色面朝上,另一面为黑色的概率是多少是多少

因为有三张牌,而又分正反面,所以朝上的情况有 6 种

例2

第二个人的概率是: \frac{n - 1}{n} \cdot \frac{1}{n - 1} = \frac{1}{n}

第三个人的概率是: \frac{n - 1}{n}\frac{n - 2}{n - 1} \cdot \frac{1}{n - 2} = \frac{1}{n}

以此类推

例3

设男女人口比例为 51:49, 男性色盲率为 2\%, 女性色盲率为 0.25\%

例4

一个人左右口袋各一盒火柴,每盒 n 支,每次抽烟时随机选一盒点火,由于习惯, 选右口袋的概率大于二分之一 (P > \frac{1}{2}) ,, 问下面两种情形概率是否相等,试求概率值

1. 某次发现取的这一盒已经空了, 这是另一盒恰好有 m 支火柴

2. 某次用完一盒时另一盒恰好有 m 盒火柴 1)		概率		取
   左	1-p	n	n + 1
   右	p	n	n - m

当右边先取完，p^{(n+1)}(1-p)^{(n-m)}

当左边先取完，(1-p)^{(n+1)}p^{(n-m)}\cdot C(2n-m,n)

例5

在小葱和小泽面前有三瓶药，其中有两瓶是毒药，每个人必须喝 一瓶。小葱和小泽各自选了一瓶药，小泽手速比较快将药喝了下去，然 后就挂掉了.。小葱想活下去，他是应该喝掉手上的这瓶，还是另外剩下的一瓶 呢？

其实是三门问题.

有三扇门, 两个门后面是羊,一个门后面是车,你选定了一个门,主持人打开了一个门显示为羊

假设你选第一个门 (p = \frac{1}{3}), 主持人不论打开剩下的那扇门都应该不换,选第二个门 (p = \frac{1}{3}), 主持人打开第 3 个门, 应该换, 选第三个门 (p = \frac{1}{3}), 主持人打开第 2 个门,应该换.

所以 P(\text{换}) = \frac{2}{3}

小泽喝药死了是随机行为,不一定是因为毒药

所以换不换都一样

例6

过河有两个路

问选哪个.

首先,选 1 活的概率是 (\frac{99}{100}) ^ {100} 选 2 活的概率是 (\frac{999}{1000}) ^ {1000}

即 \dfrac{999}{1000} > \dfrac{998}{999}

又 \because \dfrac{99}{100} =\dfrac{990}{1000}= \dfrac{999}{1000} \cdot \dfrac{998}{999} \cdot ... \cdot \dfrac{990}{991}

例7

小胡站在原点，手里拿着两枚硬币。抛第一枚硬币正面向上的概 率为 q，第二枚正面向上的概率为 r。

小胡开始抛第一枚硬币，每次抛到反面小胡就向 y 轴正方向走一 步，直到抛到正面。

接下来小胡继续抛第一枚硬币，每次抛到反面小胡就向 x 轴正方 向走一步，直到抛到正面。

现在小胡想回来了，于是他开始抛第二枚硬币，如果小胡抛到正 面小胡就向 y 轴的负方向走一步，否则小胡就向 x 轴的负方向走一 步。

现在小胡想知道他在往回走的时候经过原点的概率是多少呢？

令 t = x+ y

据二项式定理:

得原式

发现此时的西格玛为等比数列, 运用等比数列求和公式

原式

而分子 1-(1 - p)^{\inf + 1} 无限趋近于 1

例8

检验矩阵 A \times B= C 是否成立

竟然是MILLER_RABIN!

随机一个 n \times 1 的矩阵 D

若 A\times (B \times D) = C \times D

只要随机足够多的矩阵 D, 则一定正确.

完结撒花！！！！！！