QBXT五一数学营

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

Day 1

上午

电脑1s跑3e8()

mod

$a/b=c...d,a=b\cdot c+d$

$b>d\ge 0$

$c=a/b,d=a\mathrm{mod}b$

$(a+b)\mathrm{mod}c=(a\mathrm{mod}c+b\mathrm{mod}c)\mathrm{mod}c$

$(a-b)\mathrm{mod}c=(a\mathrm{mod}c-b\mathrm{mod}c)\mathrm{mod}c$

$(a\cdot b)\mathrm{mod}c=(a\mathrm{mod}c)\cdot (b\mathrm{mod}c)\mathrm{mod}c$

例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 g = \gcd(a, b), a = a'g, b = b'g g=gcd(a,b),a=a′g,b=b′g

∴ gcd ⁡ ( a ′ , b ′ ) = 1 \therefore \gcd(a', b') = 1 ∴gcd(a′,b′)=1

∴ gcd ⁡ ( a − b , b ) = gcd ⁡ ( ( a ′ − b ′ ) g , b ′ g ) = gcd ⁡ ( a ′ − b ′ , b ′ ) ⋅ g = 1 ⋅ g = g \therefore \gcd(a - b, b) = \gcd((a' - b')g, b'g) = \gcd(a' - b', b') \cdot g = 1 \cdot g = g ∴gcd(a−b,b)=gcd((a′−b′)g,b′g)=gcd(a′−b′,b′)⋅g=1⋅g=g

$\gcd (a,b)=\gcd (a-b,b)=\gcd (a-2b,b)=.....=\gcd (a\mathrm{mod}b,b)$

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

时间复杂度$O(logn)$

证明：
$a \ge b, \gcd(a, b) = \gcd(b, a \bmod $ $b)$

$a\mathrm{mod}b<a/2$

证明：分类讨论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";

时间复杂度：

$ans$ 每次都在变小， 而每次 $gcd$ 都可看做除 $2$
所以最多除 $ \log{ans}$ 次

$ans=a1$ , 所以 O ( n + log ⁡ a 1 ) O(n + \log a_1) O(n+loga1​)

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

$ g \cdot l = a \cdot b$

代码

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

快速幂

x , y , p ≤ 1 0 9 x, y, p \le 10 ^ 9 x,y,p≤109

例: $y=37$ 时

x 37 = ( x 18 ) 2 ⋅ x x ^ {37} = (x ^ {18}) ^ 2 \cdot x x37=(x18)2⋅x

x 18 = ( x 9 ) 2 x ^ {18} = (x ^ 9) ^ 2 x18=(x9)2

x 9 = ( x 4 ) 2 ⋅ x x ^ 9 = (x ^ 4) ^ 2 \cdot x x9=(x4)2⋅x

x 4 = ( x 2 ) 2 x ^ 4 = (x ^ 2) ^ 2 x4=(x2)2

x 2 = x ⋅ x x ^ 2 = x \cdot x x2=x⋅x

时间复杂度$O(\log y)$

代码
通用版(循环)
ll qpow(ll a, ll b, ll p){if(y == 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;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(
矩阵加法与减法

$$
\begin{vmatrix}{}
1 & 2 & 3 \
3 & 2 & 1
\end{vmatrix}

\begin{vmatrix}{}
1 & 2 & 3 \
3 & 2 & 1
\end{vmatrix}

=
\begin{vmatrix}{}
4 & 4 & 4 \
4 & 4 & 4
\end{vmatrix}
$$

矩阵减法同理

矩阵乘法

$A(n\cdot m)\cdot B(m\cdot k)$
只有第一个矩阵的列数等于第二个矩阵的行数才行

$$
\begin{vmatrix}{}
1 & 2 & 3 \
3 & 2 & 1
\end{vmatrix}

\times

\begin{vmatrix}{}
1 & 2 \
1 & 2 \
1 & 2
\end{vmatrix}

=

\begin{vmatrix}{}
1 * 1 + 2 * 1 + 3 * 1 & 1 * 2 + 2 * 2 + 3 * 2 \
3 * 1 + 2 * 1 + 1 * 1 & 3 * 2 + 2 * 2 + 1 * 2
\end{vmatrix}

=

\begin{vmatrix}{}
6 & 12 \
6 & 12
\end{vmatrix}
$$

代码：

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 ⋅ m 2 ) O(n \cdot m ^ 2) O(n⋅m2)

$i,j,k$ 枚举顺序修改对结果无影响，但对速度有影响

$i,j,k$ 顺序枚举跑 $n=1024$ ,耗时 $9.454s$

$j,k,i$ 顺序枚举 $14.19s$

$k,j,i$ : $12.46s$

$i,k,j$ : $5.212s$

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

下午

例1

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

数组 $ f $代表 $fib$ 数列

手推可得

$$

\begin{vmatrix}{}
f_{i - 1} & f_{i - 2}
\end{vmatrix}

\times

\begin{vmatrix}{}
1 & 1\
1 & 0
\end{vmatrix}

=
\begin{vmatrix}{}
f_{i} & f_{i - 1}
\end{vmatrix}
$$

令
B = ∣ 1 1 1 0 ∣ B = \begin{vmatrix}{} 1 & 1\\ 1 & 0 \end{vmatrix} B= ​11​10​ ​
$$
\therefore

\begin{vmatrix}{}
f_{n} & f_{n - 1}
\end{vmatrix}

=

\begin{vmatrix}{}
f_{1} & f_{0}
\end{vmatrix}

\times

B ^ n
$$
矩阵乘法套快速幂即可

#include
#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 × f i − 3 f_{i} = f_{i - 1} \times f_{i - 3} fi​=fi−1​×fi−3​

仍然手推可得

$$

\begin{vmatrix}{}
f_{i - 1} & f_{i - 2} & f_{i - 3}
\end{vmatrix}

\times

\begin{vmatrix}{}
1 & 1 & 0\
0 & 0 & 1\
1 & 0 & 0
\end{vmatrix}

=
\begin{vmatrix}{}
f_{i} & f_{i - 1} & f_{i - 2}
\end{vmatrix}
$$

令
B = ∣ 1 1 0 0 0 1 1 0 0 ∣ B = \begin{vmatrix}{} 1 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{vmatrix} B= ​101​100​010​ ​
$$
\therefore

\begin{vmatrix}{}
f_{n} & f_{n - 1} & f_{n - 2}
\end{vmatrix}

=

\begin{vmatrix}{}
f_{2} & f_{1} & f_{0}
\end{vmatrix}

\times

B ^ n
$$

扩展

已知 f i = k 1 f i − 1 + k 2 f i − 2 . . . . + k m f i − m + 1 ( m ≤ i ) f_i=k_{1}f_{i-1}+k_{2}f_{i-2}....+k_{m}f_{i-m+1}(m\le i) fi​=k1​fi−1​+k2​fi−2​....+km​fi−m+1​(m≤i)

求 f n m o d p ( 1 ≤ n ≤ 1 0 18 ) f_n \bmod p(1\le n\le 10^{18}) fn​modp(1≤n≤1018)

构造矩阵
$$
\overbrace{
\begin{vmatrix}{}
k_1 &1&0&0&…\
k_{2}&0&1&0&…\
k_{3}&0&0&1&…\
k_{4}&0&0&0&…\
…&…&…&…&…\
k_{m}&0&0&0&…\
\end{vmatrix}}^{\text{m}}

\times

\begin{vmatrix}{}
f_1 &f_2&&f_3&…&f_m\
\end{vmatrix} ^ n
$$

即可得出答案

矩阵乘法中
$$A\times B\ne B\times A$$

例3

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

$ n \le 100, k \le 100$

考虑动态规划

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

所以答案即为 f k , n f_{k,n} fk,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步在cf[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步在cf[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 × b j c , b f_{a,d,b} += f_{a-1,d,c} \times bj_{c,b} fa,d,b​+=fa−1,d,c​×bjc,b​

改为 f a d , b + = f ( a − 1 ) d , c × b j c , b f_{a_{d,b}} += f_{(a-1)_{d,c}} \times bj_{c,b} fad,b​​+=f(a−1)d,c​​×bjc,b​

然后将 f a , f a − 1 , b j f_a, f_{a - 1}, bj fa​,fa−1​,bj当做 $n$ 行 $n$ 列矩阵

所以 f a = f a − 1 × b j f_a = f_{a - 1} \times bj fa​=fa−1​×bj

即得 f k = f 0 × b j k f_k = f_0 \times bj ^ k fk​=f0​×bjk

套矩阵快速幂

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

例4

LuoguP4159

比例 $4$ 多了路径长度罢了

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

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

代码晚上补(

#include
#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;
}

质数判定

初等数论: 自然数范围

质数 & 素数 & prime : 只有自己和 $1$ 为因子的数

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

1既不是素数也不是合数

给定 $x$ 判断 $x$ 是否为质数

bool is_prime(int x){if(x < 2)return 0;for(int i = 2; i * i <= x; ++i)if(x % i == 0)return 0;return 1;
}

O ( x ) O(\sqrt x) O(x ​)只能处理 x ≤ 1 0 16 x \le 10 ^ {16} x≤1016

给定 $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,2,3,...,n$ n 个数, 将它们分为几组,使得每组内之和都为质数,求最少分几组.

$ n \le 2000$

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

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

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

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

#include
#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

上午

逆元

$ (3 + 4) \bmod 5 = 2 $

$ (3 - 4) \bmod 5 = 4 $

$ [(1 + 7) \div 4] \bmod 5 = 2 $

$ (3 \div 4) \bmod 5 = ??? $

逆元:对于 $a÷b\mathrm{mod}p$ 找到一个整数 $c$ ,使得 $ a \div b \bmod p = a \times c \bmod p$

费马小定理:

当 $p$ 为质数,且 $1\le a<p$, a p − 1 ≡ 1 ( m o d p ) a ^ {p - 1} \equiv 1 (\bmod p) ap−1≡1(modp)

即得: a p − 2 ≡ 1 a ( m o d p ) a ^ {p - 2} \equiv \frac{1}{a} (\bmod p) ap−2≡a1​(modp)

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

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

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

欧拉定理:

$\gcd (a,b)=1$ 即可

$ a ^ {\phi§} \equiv 1 (\bmod p)$

$ \phi§ $ : 欧拉函数,求 $1\backsim p$ 中与 $p$ 互质的个数

由欧拉定理可得: $ a ^ {\phi§ - 1} \equiv \frac{1}{a}(\bmod p)$

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

求 $\varphi (n)$:

若 n = p 1 , ϕ ( n ) = p 1 − 1 n = p_1, \phi(n) = p_1 - 1 n=p1​,ϕ(n)=p1​−1

n = p 1 2 , ϕ ( n ) = p 1 2 − p 1 = p 1 ( p 1 − 1 ) n = {p_1} ^ 2, \phi(n) = {p_1} ^ 2 - p_1 = p_1(p_1 - 1) n=p1​2,ϕ(n)=p1​2−p1​=p1​(p1​−1)

n = p 1 k , ϕ ( n ) = p 1 k − 1 ⋅ ( p 1 − 1 ) = p i − 1 p i ⋅ n n = {p_1} ^ k, \phi(n) = {p_1} ^ {k - 1} \cdot (p_1 - 1) = \frac{p_{i - 1}}{p_i} \cdot n n=p1​k,ϕ(n)=p1​k−1⋅(p1​−1)=pi​pi−1​​⋅n

n = p 1 p 2 , ϕ ( n ) = n − n p 1 − n p 2 + n p 1 p 2 = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) n = p_1p_2, \phi(n) = n - \frac{n}{p_1} - \frac{n}{p_2} + \frac{n}{p_1p_2} = n(1 - \frac{1}{p_1})(1 - \frac{1}{p2}) n=p1​p2​,ϕ(n)=n−p1​n​−p2​n​+p1​p2​n​=n(1−p1​1​)(1−p21​)

n = p 1 k 1 ⋅ p 2 k 2 ⋅ p 3 k 3 ⋅ . . . . . . ⋅ p t k t n = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdot {p_3}^{k_3} \cdot ...... \cdot {p_t}^{k_t} n=p1​k1​⋅p2​k2​⋅p3​k3​⋅......⋅pt​kt​

$ \phi(n) = n \cdot (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})…(1 - \frac{1}{p_t})$

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;
}

O ( n ) O(\sqrt n) O(n ​)

例1

LuoguP3811

给定 $n,p$ ,求 $1\backsim n$ 中每个数 $\mathrm{mod}p$ 一一下的逆元

$ n \le 10 ^ 6, p$ 为在 1 0 9 10 ^ 9 109 附近的质数

法一

先递推 $1\backsim n$ 阶乘 $fac[i]$

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

求出阶乘逆元 $facinv[i]$

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

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;

法二

假设 i n v 1 ∽ i n v i − 1 inv_1 \backsim inv_{i - 1} inv1​∽invi−1​ 都已经求出, i n v i = ? inv_i = ? invi​=?

$p>i$ 设 $p=ki+r$

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

$ -r \equiv ki(\bmod $ $p)$

$ \frac{r}{i} \equiv -k (\bmod $ $p)$

$ \frac{1}{i} \equiv -\frac{k}{r}(\bmod $ $p)$ 即可得出.

cin >> n >> p;
inv[1] = 1;
for(int i = 2; i <= n; ++i){int k = p / i, r = p % i;//p = k * i + r//0 = k * i + r(mod p)//-r = k * i(mod p)//1 / i = -k / r(mod p)inv[i] = 1ll * (p - k) * inv[r] % p;
}

质数

若 $n$ 为质数, $ n - 1 = d \times 2 ^ r$

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

1. a d m o d n = 1 a ^ d \bmod n = 1 admodn=1

2. 存在 $0\le i<r$, a d × 2 i m o d n = n − 1 a^{d \times 2 ^ i} \bmod n = n - 1 ad×2imodn=n−1

$n$ 若为质数, 则两个性质中至少满足一个,若都不满足,则一定不为质数

随机代入 $a$ 检验, 满足的次数越多,则是质数的概率越大,有一个 $a$ 不满足条件,则一定不是质数

法一

//n - 1 = d * 2 ^ r
//找一个 1 <= a <= n
//1. a ^ d % n = 1
//2. 存在0 <= i < r使得a ^ (d * 2 ^ i) % n = n - 1
//当n是质数时,至少一条成立
bool miller_rabin(int n, int a){int d = n - 1, r = 0;while(d % 2 == 0)d /= 2, ++r;int x = ksm(a, d, r);if(x == 1)return 1;for(int i = 0; i < r; ++i){if(x == n - 1)return 1;x = 1ll * x * x * % n;}return 0;
}//O(logn)
bool check(int n){if(n < 2)return 0;for(int i = 1; i <= 23; ++i){int a = rand()%(n - 1) + 1;if(!miller_rabin(n, a)) return 0;}return 1;
}

法二

bool miller_rabin(int n, int a){int d = n - 1, r = 0;while(d % 2 == 0)d /= 2, ++r;int x = ksm(a, d, r);if(x == 1)return 1;for(int i = 0; i < r; ++i){if(x == n - 1)return 1;x = 1ll * x * x * % n;}return 0;
}//O(logn)
int p[] = {2, 3, 5, 7, 11, 13, 23, 37, 73};
bool check(int n){if(n < 2)return 0;for(int i = 0; i < 8; ++i){if(n == p[i])return 1;if(n % p[i] == 0) return 0;if(!miller_rabin(n, p[i] % n))reutrn 0;}return 1;
}

exgcd

方程 $xa+yb=g\to (\gcd (a,b)=g)$

$ \gcd(b, a \bmod b) = g \rightarrow x’b + y’(a \bmod b) = g$

x ′ b + y ′ a − y ′ b ⌊ a b ⌋ = g x'b + y'a - y'b \lfloor\frac{a}{b}\rfloor = g x′b+y′a−y′b⌊ba​⌋=g

y ′ a + ( x ′ − y ′ ⌊ a b ⌋ ) ⋅ b = g y'a + (x' - y' \lfloor\frac{a}{b}\rfloor) \cdot b = g y′a+(x′−y′⌊ba​⌋)⋅b=g

int exgcd(int a, int b, int &x, int &y){//求g = gcd(a, b)以及 xa + yb = gif(!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 = gx = yp;y = xp - yp * (a / b);return g;
}

裴蜀定理

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

例1

LuoguP1082

$ax\equiv 1(\mathrm{mod}b)\to ax=yb+1$

$\therefore ax-yb=1$

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

#include
#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)$

$(1 + t) \equiv 1( \bmod $ $3),(1+t)\equiv 1(\mathrm{mod}$ $5)$

$t\equiv 0(\mathrm{mod}$ $15)$

发现 $2$ 个同余方程可以合并:
x ≡ { a 1 ( m o d p 1 ) a 2 ( m o d p 2 ) x\equiv\begin{cases} a_1&(\bmod p_1)\\ a_2&(\bmod p_2) \end{cases} x≡{a1​a2​​(modp1​)(modp2​)​

如何合并成 $x\equiv a(\mathrm{mod}p)$:

令 x = a 1 x = a_1 x=a1​, 不断加上 p 1 p_1 p1​ , 次数加过 p 2 p_2 p2​ , 则无解

最后， p = l c m ( p 1 , p 2 ) p = lcm(p_1, p_2) p=lcm(p1​,p2​)，$a=x$ ，合并完毕，时间复杂度 O ( p 2 ) O(p_2) O(p2​)。

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 m o d p 1 = a 1 , x m o d p 2 = a 2 , x m o d p = a x \bmod p_1 = a_1, x \bmod p_2 = a_2, x \bmod p = a xmodp1​=a1​,xmodp2​=a2​,xmodp=a

设 x = k 1 × p 1 + a 1 = k 2 × p 2 + a 2 x = k_1 \times p_1 + a_1 = k_2 \times p_2 + a_2 x=k1​×p1​+a1​=k2​×p2​+a2​

∴ k 1 × p 1 − k 2 × p 2 = a 2 − a 1 \therefore k_1 \times p_1 - k_2 \times p_2 = a_2 - a_1 ∴k1​×p1​−k2​×p2​=a2​−a1​

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
#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 n ) O(n\sqrt n) O(nn ​)

$miller$_$rabin$ ,枚举每个数 $O(n\log 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 ( n 1 + n 2 + . . . n n ) O(\frac{n}{1} + \frac{n}{2} + ... \frac{n}{n}) O(1n​+2n​+...nn​)

$ = n (\frac{1}{1} + \frac{1}{2} + … \frac{1}{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)$

例子: $\varphi (x)$

ϕ ( n ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p t ) \phi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_t}) ϕ(n)=n(1−p1​1​)(1−p2​1​)...(1−pt​1​)

n = p 1 k 1 p 2 k 2 . . . p t k t n = {p_1}^{k_1}{p_2}^{k_2}...{p_t}^{k_t} n=p1​k1​p2​k2​...pt​kt​

ϕ ( m ) = m ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p w ) \phi(m) = m(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_w}) ϕ(m)=m(1−p1​1​)(1−p2​1​)...(1−pw​1​)

m = p 1 r 1 p 2 r 2 . . . p w r w m = {p_1}^{r_1}{p_2}^{r_2}...{p_w}^{r_w} m=p1​r1​p2​r2​...pw​rw​

n m = p 1 k 1 p 2 k 2 . . . p t k t ⋅ p 1 r 1 p 2 r 2 . . . p w r w nm = {p_1}^{k_1}{p_2}^{k_2}...{p_t}^{k_t} \cdot {p_1}^{r_1}{p_2}^{r_2}...{p_w}^{r_w} nm=p1​k1​p2​k2​...pt​kt​⋅p1​r1​p2​r2​...pw​rw​

ϕ ( n m ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p t ) ⋅ m ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p w ) \phi(nm) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_t}) \cdot m(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_w}) ϕ(nm)=n(1−p1​1​)(1−p2​1​)...(1−pt​1​)⋅m(1−p1​1​)(1−p2​1​)...(1−pw​1​)

$\therefore \varphi (n)\varphi (m)=\varphi (nm)$

线性预处理 $\varphi (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

上午

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

给定 $a,b,p$ 求解 a x m o d p = b a ^ x \bmod p = b axmodp=b

a , b , p ≤ 1 0 9 a, b, p \le 10^9 a,b,p≤109

暴力容易写出 $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;}
}

由费马小定理知:

a p − 1 ≡ 1 ( m o d p ) a ^ {p - 1} \equiv 1(\bmod p) ap−1≡1(modp)

所以

a p − 1 + k = a p − 1 × a k ≡ a k ( m o d p ) a^{p - 1 + k} = a^{p - 1} \times a ^ k \equiv a ^ k (\bmod p) ap−1+k=ap−1×ak≡ak(modp)

可得循环节只有 $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;}
}

$bsgs$ 解法:

先将 a 0 ∽ a p − 1 a^0 \backsim a^{p - 1} a0∽ap−1 分为几组, 每组为

a 0 , a 1 , . . . a s − 1 a^0, a^1,... a^{s - 1} a0,a1,...as−1

a s , a s − 1 , . . . , a 2 s − 1 a^s, a^{s - 1}, ..., a ^ {2s - 1} as,as−1,...,a2s−1

a 2 s . . . . . . a^{2s}...... a2s......

$...$

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

和暴力复杂度其实一样

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

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

…

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

代码

int solve (int a, int b, int p){int s = sqrt(p);int v = 1;set<int> se;//集合STLfor(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 ( p ) O(\sqrt p) O(p ​) (分块复杂度

例1

LuoguP3846
模板,见代码:

#include
#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$ 种选法,

P ( n m ) = n ⋅ ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) = n ! ( n − m ) ! P \binom{n}{m} = n \cdot (n - 1)(n - 2)...(n - m + 1) = \dfrac{n!}{(n - m)!} P(mn​)=n⋅(n−1)(n−2)...(n−m+1)=(n−m)!n!​

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

C ( n m ) = n ⋅ ( n − 1 ) . . . ( n − m + 1 ) m ! = n ! ( n − m ) ! m ! = P ( n m ) m ! C \binom {n}{m} = \dfrac{n \cdot (n - 1)...(n - m + 1)}{m!} = \dfrac{n!}{(n - m)! m!} = \dfrac{P \binom{n}{m}}{m!} C(mn​)=m!n⋅(n−1)...(n−m+1)​=(n−m)!m!n!​=m!P(mn​)​

C ( n m ) = n ! ( n − m ) ! m ! C \binom{n}{m} = \dfrac{n!}{(n - m)!m!} C(mn​)=(n−m)!m!n!​

组合数一些式子:

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$个

   ( n m ) = ( n − 1 m − 1 ) + ( n − 1 m ) \binom{n}{m} = \binom{n - 1}{m - 1} + \binom {n - 1}{m} (mn​)=(m−1n−1​)+(mn−1​)

   预处理求所有的组合数

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$ 数组是个杨辉三角形

$1$

$1,1$

$1,2,1$

$1,3,3,1$

$1,4,6,4,1$

4. 选任意多个物品:

   ( n 0 ) + ( n 1 ) + ( n 2 ) + . . . + ( n n ) = 2 n \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + ... +\binom{n}{n} = 2 ^ n (0n​)+(1n​)+(2n​)+...+(nn​)=2n

5. $n\ge 1$

   ( n 0 ) − ( n 1 ) + ( n 2 ) − ( n 3 ) + . . . ± ( n n ) = 0 \binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\binom{n}{3}+... \pm \binom{n}{n} = 0 (0n​)−(1n​)+(2n​)−(3n​)+...±(nn​)=0

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

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

6. ( x + y ) n (x + y)^n (x+y)n:

( x + y ) 0 = 1 (x + y)^0 = 1 (x+y)0=1
( x + y ) 1 = x + y (x + y)^1 = x + y (x+y)1=x+y
( x + y ) 2 = x 2 + 2 x y + y 2 (x + y)^2 = x ^ 2 + 2xy + y ^ 2 (x+y)2=x2+2xy+y2
( x + y ) 3 = x 3 + 3 x 2 y + 3 x y 2 + y 3 (x + y)^3 = x ^ 3 + 3x^2y + 3xy^2 +y^3 (x+y)3=x3+3x2y+3xy2+y3
( x + y ) 4 = x 4 + 4 x 3 y + 6 x 2 y 2 + 4 x y 3 + x 4 (x + y)^4 = x ^ 4 + 4x^3y + 6x^2y^2 + 4xy^3 + x^4 (x+y)4=x4+4x3y+6x2y2+4xy3+x4

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

∴ ( x + y ) n = ( n 0 ) x n y 0 + ( n 1 ) x n − 1 y 1 + . . . + ( n n ) x 0 y n \therefore (x + y)^n = \binom{n}{0}x^ny^0 + \binom{n}{1}x^{n - 1}y^1 + ...+\binom{n}{n}x^0y^n ∴(x+y)n=(0n​)xny0+(1n​)xn−1y1+...+(nn​)x0yn

即为
( x + y ) n = ∑ i = 0 n ( n i ) x n − i y i (x + y) ^n = \sum_{i = 0}^{n}\binom{n}{i}x^{n - i}y^i (x+y)n=i=0∑n​(in​)xn−iyi

7. $3$ 式的不断展开

( n m ) \binom{n}{m} (mn​)
= ( n − 1 m − 1 ) + ( n − 1 m ) =\binom{n-1}{m - 1}+\binom{n - 1}{m} =(m−1n−1​)+(mn−1​)
= ( n − 2 m − 2 ) + 2 ( n − 2 m − 1 ) + ( n − 2 m ) =\binom{n - 2}{m - 2}+2\binom{n - 2}{m - 1}+\binom{n - 2}{m} =(m−2n−2​)+2(m−1n−2​)+(mn−2​)
= ( n − 3 m − 3 ) + 3 ( n − 3 m − 1 ) + 3 ( n − 3 m − 2 ) + ( n − 3 m ) =\binom{n - 3}{m - 3}+3\binom{n - 3}{m - 1}+3\binom{n - 3}{m - 2}+\binom{n - 3}{m} =(m−3n−3​)+3(m−1n−3​)+3(m−2n−3​)+(mn−3​)
$$......$$
= ∑ i = 0 k ( k i ) ⋅ ( n − k m − i ) = \sum_{i = 0}^{k}\binom{k}{i} \cdot \binom{n - k}{m - i} =i=0∑k​(ik​)⋅(m−in−k​)

例1

$n$ 个数, 选 $m$ 个, 不计顺序, 但是一个数可以选任意多次,求方案数

考虑原版,每个数只能选一次其实就是求不等式
1 ≤ a 1 < a 2 < . . . < a m ≤ n 1 \le a_1 < a_2 < ... < a_m \le n 1≤a1​<a2​<...<am​≤n
的解的个数

这道题可以看做
1 ≤ b 1 ≤ b 2 ≤ . . . ≤ b m ≤ n 1 \le b_1 \le b_2 \le ... \le b_m \le n 1≤b1​≤b2​≤...≤bm​≤n
的解的个数

设 c 1 = b 1 , c 2 = b 2 + 1... , c m = b m + m − 1 c_1 = b_1, c_2=b_2+1...,c_m = b_m + m - 1 c1​=b1​,c2​=b2​+1...,cm​=bm​+m−1

就可以看做
1 ≤ c 1 < c 2 < . . . < c m ≤ n + m + 1 1 \le c_1 < c_2 < ... < c_m \le n + m + 1 1≤c1​<c2​<...<cm​≤n+m+1
的解的个数 $ = \binom{n + m-1}{m}$

a n s = ( n + m − 1 m ) ans = \binom{n + m -1}{m} ans=(mn+m−1​)

例2

求 ( n m ) m o d p \binom{n}{m} \bmod p (mn​)modp

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

$ans=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
#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 ≤ 1 0 6 , p n,m \le 10^6, p n,m≤106,p 为质数

逆元 $O(n\log p)$

( n m ) = n ! ( n − m ) ! m ! = n ! [ ( n − m ) ! ] p − 2 ( m ! ) p − 2 m o d p \binom{n}{m} = \dfrac{n!}{(n - m)!m!} = n! [(n - m)!]^{p - 2}(m!)^{p - 2} \bmod p (mn​)=(n−m)!m!n!​=n![(n−m)!]p−2(m!)p−2modp

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 ≤ 1 0 9 , m ≤ 1 0 3 n \le 10^9, m \le 10^3 n≤109,m≤103

( n m ) = n ! ( n − m ) ! m ! \binom{n}{m} = \dfrac{n!}{(n - m)!m!} (mn​)=(n−m)!m!n!​
= n ( n − 1 ) ( n − 2 ) . . ( n − m + 1 ) 1 × 2 × 3 × . . . × m = \dfrac{n(n - 1)(n - 2)..(n - m + 1)}{1 \times 2 \times 3 \times...\times m} =1×2×3×...×mn(n−1)(n−2)..(n−m+1)​

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

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 ≤ 1 0 9 , p ≤ 100 n, m \le 10 ^ 9, p \le 100 n,m≤109,p≤100 为指数

$Lucas$ 定理:

先将 $n,m$ 转换为 $p$ 进制.

短除法转换进制

如 $n=25,m=12,p=3$ ,

n ( 3 ) = 221 , m ( 3 ) = 110 n_{(3)} = 221, m_{(3)} = 110 n(3)​=221,m(3)​=110

( 25 12 ) m o d p = ( n 1 m 1 ) ( n 2 m 2 ) ( n 3 m 3 ) m o d p \binom{25}{12} \bmod p = \binom{n_1}{m_1}\binom{n_2}{m_2}\binom{n_3}{m_3} \bmod p (1225​)modp=(m1​n1​​)(m2​n2​​)(m3​n3​​)modp

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;
}

$O(\log n)$

LuoguP3807

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

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

例3

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

x ≤ 1 0 9 , k ≤ 1 0 3 x \le 10 ^ 9, k \le 10^3 x≤109,k≤103

酱汁构造(

x = 1 + 1 + 1 + . . . + 1 ⏞ k − 1 + ( n − k + 1 ) x = \overbrace{1 + 1 + 1 + ...+1}^{k - 1} +(n - k + 1) x=1+1+1+...+1 ​k−1​+(n−k+1)

= ( 1 0 ) + ( 2 0 ) + . . . . + ( k − 1 0 ) + ( n − k + 1 1 ) = \binom{1}{0}+\binom{2}{0} + .... +\binom{k - 1}{0}+\binom{n - k + 1}{1} =(01​)+(02​)+....+(0k−1​)+(1n−k+1​)

例4

比较 ( n 1 m 1 ) \binom{n1}{m1} (m1n1​) 与 ( n 2 m 2 ) \binom{n2}{m2} (m2n2​) 大小

log ⁡ ( n m ) = log ⁡ n ! ( n − m ) ! m ! = log ⁡ n ! − log ⁡ ( n − m ) ! − log ⁡ m ! \log \binom{n}{m} = \log\dfrac{n!}{(n - m)! m!} = \log {n!} - \log {(n - m)!} - \log{m!} log(mn​)=log(n−m)!m!n!​=logn!−log(n−m)!−logm!

$$\log n!=\log 1+\log 2+...+\log n$$

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$ 个组合数之和最大

对于每个组合数 ( a b ) , a , b ≤ n \binom{a}{b}, a, b \le n (ba​),a,b≤n

观察杨辉三角

$$1$$
$$1,1$$
$$1,2,1$$
$$1,3,3,1$$
$$1,4,6,4,1$$

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

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

代码晚上补(

例6

LuoguP3746

f ( n , r ) = ∑ i = 0 inf ⁡ C ( n k , i k + r ) f(n, r) = \sum_{i = 0}^{\inf}C(nk, ik + r) f(n,r)=i=0∑inf​C(nk,ik+r)
展开 $k$ 次
= ∑ i = 0 inf ⁡ ∑ j = 0 k C ( k , j ) ⋅ C ( n k − k , i k + r − j ) = \sum_{i = 0}^{\inf}\sum_{j = 0}^{k}C(k, j) \cdot C(nk - k, ik + r - j) =i=0∑inf​j=0∑k​C(k,j)⋅C(nk−k,ik+r−j)
= ∑ j = 0 k ∑ i = 0 inf ⁡ C ( k , j ) ⋅ C ( n k − k , i k + r − j ) = \sum_{j = 0}^{k}\sum_{i = 0}^{\inf}C(k, j) \cdot C(nk - k, ik + r - j) =j=0∑k​i=0∑inf​C(k,j)⋅C(nk−k,ik+r−j)
= ∑ j = 0 k ∑ i = 0 inf ⁡ C ( k , j ) ⋅ C ( n k − k , i k + r − j ) = \sum_{j = 0}^{k}\sum_{i = 0}^{\inf}C(k, j) \cdot C(nk - k, ik + r - j) =j=0∑k​i=0∑inf​C(k,j)⋅C(nk−k,ik+r−j)
= ∑ j = 0 k C ( k , j ) ∑ i = 0 inf ⁡ ⋅ C ( ( n − 1 ) k , i k + r − j ) = \sum_{j = 0}^{k}C(k, j)\sum_{i = 0}^{\inf} \cdot C((n - 1) k, ik + r - j) =j=0∑k​C(k,j)i=0∑inf​⋅C((n−1)k,ik+r−j)
= ∑ j = 0 k C ( k , j ) ⋅ f ( n − 1 , r − j ) = \sum_{j = 0}^{k}C(k, j) \cdot f(n - 1, r - j) =j=0∑k​C(k,j)⋅f(n−1,r−j)
令
$$D(r-j,r)=C(k,j)$$

f n ( 1 , r ) = ∑ j = 0 k f n − 1 ( 1 , r − j ) ⋅ D ( r − j , r ) f_n(1, r) = \sum_{j = 0}^{k}f_{n - 1}(1, r - j) \cdot D(r - j, r) fn​(1,r)=j=0∑k​fn−1​(1,r−j)⋅D(r−j,r)

矩阵快速幂

代码晚上能补出来?(

#include
#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;
}

抽屉原理

$n+1$ 个东西放入 $n$ 个抽屉里,至少有 $1$ 个抽屉有至少 $2$ 个东西

$kn+1$ 个东西,放入 $n$ 个抽屉里, 至少有一个抽屉有至少 $k+1$个东西

例1

给定 $n$ 个数, 要求从中选出任意多个数, 使得它们的和为 $c$ 的倍数

c ≤ n ≤ 1 0 5 c \le n \le 10^5 c≤n≤105

用前缀和做:

$qzh$ 数组中存放 $1+n$ 个数: q z h 0 , q z h 1 , . . . , q z h n qzh_0, qzh_1, ... ,qzh_n qzh0​,qzh1​,...,qzhn​

将每个元素 $\mathrm{mod}$ $c$ 后的结果分类 $0,1,2,...,c-1$

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

代码等补(

例2

平面上 $n$ 个点 ( x i , y i ) (x_i, y_i) (xi​,yi​)

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

求最小的 $L$

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

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

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

check中循环 $4\times 4$.

$O(4\times 4\times n)$

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

容斥

设 A 1 A_1 A1​ 为学语文的人的集合, A 2 A_2 A2​ 为学数学的人的集合, A 3 A_3 A3​ 为学英语的人

同时学语文和数学的人: A 1 ⋂ A 2 A_1 \bigcap A_2 A1​⋂A2​

学语文或数学的人: A 1 ⋃ A 2 A_1 \bigcup A_2 A1​⋃A2​

∣ A 1 ⋃ A 2 ∣ = ∣ A 1 ∣ + ∣ A 2 ∣ − ∣ A 1 ⋂ A 2 ∣ |A_1 \bigcup A_2| = |A_1| + |A_2| - |A_1 \bigcap A_2| ∣A1​⋃A2​∣=∣A1​∣+∣A2​∣−∣A1​⋂A2​∣

∣ A 1 ⋃ A 2 ⋃ A 3 ∣ = ∣ A 1 ∣ + ∣ A 2 ∣ + ∣ A 3 ∣ − ∣ A 1 ⋂ A 2 ∣ − ∣ A 2 ⋂ A 3 ∣ − ∣ A 1 ⋂ A 3 ∣ + ∣ A 1 ⋂ A 2 ⋂ A 3 ∣ |A_1 \bigcup A_2 \bigcup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \bigcap A_2| - |A_2 \bigcap A_3| - |A_1 \bigcap A_3| + |A_1 \bigcap A_2 \bigcap A_3| ∣A1​⋃A2​⋃A3​∣=∣A1​∣+∣A2​∣+∣A3​∣−∣A1​⋂A2​∣−∣A2​⋂A3​∣−∣A1​⋂A3​∣+∣A1​⋂A2​⋂A3​∣

∣ A 1 ⋃ A 2 ⋃ A 3 ⋃ A 4 ∣ |A_1 \bigcup A_2 \bigcup A_3 \bigcup A_4| ∣A1​⋃A2​⋃A3​⋃A4​∣

= ∣ A 1 ∣ + ∣ A 2 ∣ + ∣ A 3 ∣ + ∣ A 4 ∣ =|A_1| + |A_2| + |A_3| + |A_4| =∣A1​∣+∣A2​∣+∣A3​∣+∣A4​∣

− ∣ A 1 ⋂ A 2 ∣ − ∣ A 1 ⋂ A 3 ∣ − ∣ A 1 ⋂ A 4 ∣ − ∣ A 2 ⋂ A 3 ∣ − ∣ A 2 ⋂ A 4 ∣ − ∣ A 3 ⋂ A 4 ∣ -|A_1 \bigcap A_2|-|A_1 \bigcap A_3|-|A_1 \bigcap A_4|-|A_2 \bigcap A_3|-|A_2 \bigcap A_4|-|A_3 \bigcap A_4| −∣A1​⋂A2​∣−∣A1​⋂A3​∣−∣A1​⋂A4​∣−∣A2​⋂A3​∣−∣A2​⋂A4​∣−∣A3​⋂A4​∣

+ ∣ A 1 ⋂ A 2 ⋂ A 3 ∣ + ∣ A 1 ⋂ A 2 ⋂ A 4 ∣ + ∣ A 1 ⋂ A 3 ⋂ A 4 ∣ + ∣ A 2 ⋂ A 3 ⋂ A 4 ∣ + |A_1 \bigcap A_2 \bigcap A_3|+ |A_1 \bigcap A_2 \bigcap A_4|+ |A_1 \bigcap A_3 \bigcap A_4|+ |A_2 \bigcap A_3 \bigcap A_4| +∣A1​⋂A2​⋂A3​∣+∣A1​⋂A2​⋂A4​∣+∣A1​⋂A3​⋂A4​∣+∣A2​⋂A3​⋂A4​∣

− ∣ A 1 ⋂ A 2 ⋂ A 3 ⋂ A 4 ∣ -|A_1 \bigcap A_2 \bigcap A_3 \bigcap A_4| −∣A1​⋂A2​⋂A3​⋂A4​∣

例1

$n$ 对夫妻, $2n$ 个人,围成一个环,求方案数.

1. 夫妻不能相邻

2. 旋转算同一种方案

先不考虑要求1,并且坐成一排,答案 $(2n)!$

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

− ( n 1 ) ⋅ ( 2 n − 2 ) ! ⋅ 2 -\binom{n} {1} \cdot (2n - 2)! \cdot 2 −(1n​)⋅(2n−2)!⋅2 :减去使一对夫妻强制相邻的方案数

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

+ ( n 2 ) ⋅ ( 2 n − 3 ) ! ⋅ 2 2 +\binom{n} {2} \cdot (2n - 3)! \cdot 2 ^ 2 +(2n​)⋅(2n−3)!⋅22:加上两对夫妻强制相邻的方案数

− ( n 3 ) ⋅ ( 2 n − 4 ) ! ⋅ 2 3 -\binom{n} {3} \cdot (2n - 4)! \cdot 2 ^ 3 −(3n​)⋅(2n−4)!⋅23:加上三对夫妻强制相邻的方案数

剩下同上

总式:
a n s = ∑ i = 0 n ( n i ) ⋅ ( 2 n − i − 1 ) ! ⋅ 2 i ⋅ ( − 1 ) i ans = \sum_{i = 0}^{n}\binom{n}{i} \cdot (2n - i - 1)! \cdot 2 ^ i \cdot (-1)^i ans=i=0∑n​(in​)⋅(2n−i−1)!⋅2i⋅(−1)i

容斥通用做法:

要满足 $n$ 个条件, 先减满足前 $1$ 个条件的方案数, 再加满足前 $2$ 个条件的方案数…

例2

询问 $1\backsim n$ 中有多少数能表示成 x y , y > 1 x^ y, y > 1 xy,y>1 的形式

n ≤ 1 0 18 n \le 10 ^{18} n≤1018

$1\backsim n$ 中能表示成 x 2 x ^ 2 x2 的 $x$ 有 n \sqrt n n ​ 个

$1\backsim n$ 中能表示成 x 3 x ^ 3 x3 的 $x$ 有 n 3 \sqrt[3]{n} 3n ​ 个

$1\backsim n$ 中能表示成 x y x ^ y xy 的 $x$ 有 n y \sqrt[y]{n} yn ​ 个

y 6 = ( y 2 ) 3 = ( y 3 ) 2 y ^ 6 = (y ^ 2) ^ 3 = (y ^ 3) ^ 2 y6=(y2)3=(y3)2

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

#includecin >> 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

矩阵

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！