怎样做音乐网站,wordpress主题怎么改,网店推广方法,石家庄职业技术学院质数筛
用于快速处理 1#xff5e;n 中所有素数的算法
因为依次遍历判断每一个数是否质数太慢#xff0c;所以把一些明显不能质数的筛出来 普通筛法#xff0c;对于每个整数#xff0c;删除掉其倍数。
bool vis[N];//0表示是质数
int pri[N],o; //质数表
void get(int n…质数筛
用于快速处理 1n 中所有素数的算法
因为依次遍历判断每一个数是否质数太慢所以把一些明显不能质数的筛出来 普通筛法对于每个整数删除掉其倍数。
bool vis[N];//0表示是质数
int pri[N],o; //质数表
void get(int n) {vis[1] true; //1不是素数for(int i 2; i n; i) {//从2开始if(!vis[i])pri[o] i; //加入质数表for(int j 2 * i; j n; j i)vis[j] 1;//删除到n的整数倍}
}
线性筛和埃氏筛-CSDN博客
埃氏筛
在普通筛法的过程中发现筛 4 的倍数毫无意义因为 4 的倍数肯定已被 2 的倍数筛过了所以优化方法是只用质数去筛。 对于每一个整数只有他是质数时才去筛
if(!vis[i]){ primes[ tot] i; for(int j 2 * i; j n; j i) vis[j] 1;//进入if里了 }
线性筛欧拉
让每个数都被其最小的质因数筛掉故一个数只被筛一次复杂度为O(n)
实现就是对于每个数我们都将他对整个现在已有的质数表筛一遍比如3是质数那么把已有的2相乘筛掉6但是并不往下进行因为比如12最小质数因数是3在遍历到4时自然而然就筛掉了这样每个数就只会被他最小质因数筛掉一次达到了线性
for(int i 2; i n; i) {if(!vis[i]) //是素数pri[ o] i;for(int j1;jo;j)if(i*pri[j]n)vis[i*pri[j]]1;else break;//}
} 快速幂
1. 基本概念
一个在O(logn)的时间内计算an的魔术技巧小技巧而暴力的计算需要O(n)的时间基本思想就是将指数按照二进制表示来分割。例如
ll ksm(ll a,ll b,ll p){ll ans1;while(b){if(b1) ansans*a%p;//b 1用按位与运算判断 b 的二进制最低位是否为 1比如 b5 是 101b1 结果为 1b4 是 100b1 结果为 0 。
如果最低位是 1说明当前这一位对应的幂次需要乘到结果里。
ans ans * a % p把当前的 a对应某一 “二进制位权” 的幂乘到结果 ans 中再对 p 取模保证数值不会溢出且符合题目对结果取模的要求。aa*a%p;//每次循环底数 a 自乘一次即 a a² % p 对应指数二进制位的位权翻倍。
比如初始 a3对应 3 1第一次自乘后 a3²9对应 3 2 第二次自乘后 a9²81对应 3 4第三次自乘后 a81²6561对应 3 8 …… 以此类推刚好匹配指数二进制各位的权值b1;//后移}return ans;
}a底数即要做幂运算的基数。b指数即幂次。p模数计算结果要对 p 取模避免数值过大溢出或满足题目对结果范围的要求。 2. 矩阵快速幂
矩阵快速幂 矩阵乘法 快速幂。 单位矩阵是对角线全为 1其他位置均为 0 的矩阵记为 I性质A×IA。
include iostream
#include cstring
using namespace std;typedef long long LL; // 使用LL作为long long的别名简化代码
const int MOD 1e9 7; // 定义模数防止整数溢出
const int N 105; // 定义矩阵的最大尺寸int n; // 矩阵的实际大小
LL k; // 矩阵需要乘方的次数// 矩阵结构体封装矩阵乘法和单位矩阵设置操作
struct Matrix {LL a[N][N]; // 存储矩阵元素// 默认构造函数初始化矩阵为全0Matrix() {memset(a, 0, sizeof a);}// 重载乘法运算符实现矩阵乘法Matrix operator*(const Matrix b) const {Matrix c;// 三层循环实现矩阵乘法注意取模防止溢出for (int i 1; i n; i)for (int k 1; k n; k)for (int j 1; j n; j)c.a[i][j] (c.a[i][j] a[i][k] * b.a[k][j]) % MOD;return c;}// 设置当前矩阵为单位矩阵对角线为1其余为0void setIdentity() {for (int i 1; i n; i) a[i][i] 1;}
};int main() {cin n k; // 输入矩阵大小n和幂次k// 读取原始矩阵Matrix base;for (int i 1; i n; i)for (int j 1; j n; j)cin base.a[i][j];// 初始化结果矩阵为单位矩阵相当于数值计算中的1Matrix res;res.setIdentity();// 快速幂算法计算矩阵的k次幂// 原理与数值快速幂相同但使用矩阵乘法代替数值乘法while (k) {if (k 1) res res * base; // 如果当前位为1则乘上当前的basebase base * base; // base平方k 1; // k右移一位相当于除以2}// 输出结果矩阵for (int i 1; i n; i) {for (int j 1; j n; j)cout res.a[i][j] ;cout endl;}return 0;
} 扩展欧几里得算法 一、核心目标求解 ax by gcd(a, b) 的整数解
扩展欧几里得算法本质是 在求最大公约数gcd的同时找到满足 ax by gcd(a, b) 的整数 x 和 y 。 比如a5, b3gcd 是 1同时能找到 x2, y-3因为 5×2 3×(-3) 10-91 gcd(5,3) 。 二、递归推导从 gcd(b, a%b) 反推 gcd(a, b) 的解
欧几里得算法的核心是 gcd(a, b) gcd(b, a%b)比如 gcd(5,3)gcd(3,2)gcd(2,1)gcd(1,0)1 。 扩展欧几里得在此基础上递归地从 gcd(b, a%b) 的解反推 gcd(a, b) 的解
ll exgcd(ll a, ll b, ll x, ll y){ // 传引用修改 x、yif(b 0){ // 递归出口b0时gcd是a解为x1, y0x 1; y 0; return a; }// 递归求解 gcd(b, a%b)同时得到子问题的解 (x, y)ll d exgcd(b, a % b, y, x); // 注意这里交换了 y、x 的位置// 子问题的解是 (x, y)但因为交换了参数实际拿到的是 yx, xy // 根据推导公式当前层的 y x - (a/b)*y y - (a / b) * x; return d; // 返回 gcd(a,b)
}
以 a5, b3 为例逐步看递归和求解过程 第一层调用exgcd(5, 3, x, y) b≠0递归调用 exgcd(3, 5%32, y, x) 第二层调用exgcd(3, 2, y, x) b≠0递归调用 exgcd(2, 3%21, y, x) 第三层调用exgcd(2, 1, y, x) b≠0递归调用 exgcd(1, 2%10, y, x) 第四层调用exgcd(1, 0, y, x) b0触发递归出口x1, y0返回 d1即 gcd1 返回第三层 此时 d1且因为参数交换当前层的 y 是子问题的 x1x 是子问题的 y0执行 y - (2/1)*x → y 0 - 2*1 -2返回 d1当前层的解是 x0, y-2 不对别急继续看… 其实这里的 x,y 是相对于当前层 a2, b1 的 哦因为参数交换后逻辑需要再仔细看 实际第三层的调用是 exgcd(2, 1, y, x)所以子问题第四层的 x1, y0 会被赋值给 当 前层的 y 和 x 即 当前层第三层的 y 子问题的 x1当前层第三层的 x 子问题的 y0 然后执行 y - (2/1)*x → y 1 - 2*0 1 所以第三层的解是 x0, y1对应等式 2*0 1*1 1 gcd(2,1)正确 返回第二层 第二层调用是 exgcd(3, 2, y, x)子问题第三层返回 d1且当前层的 y 第三层的 x0x 第三层的 y1执行 y - (3/2)*x → 3//21所以 y 0 - 1*1 -1此时第二层的解是 x1, y-1对应等式 3*1 2*(-1) 3-21 gcd(3,2)正确 返回第一层 第一层调用是 exgcd(5, 3, x, y)子问题第二层返回 d1且当前层的 y 第二层的 x1x 第二层的 y-1执行 y - (5/3)*x → 5//31所以 y 1 - 1*(-1) 2此时第一层的解是 x-1, y2对应等式 5*(-1) 3*2 -561 gcd(5,3)正确
最终exgcd(5,3,x,y) 执行后x-1, y2满足 5*(-1) 3*2 1 。 乘法逆元
1. 基本概念
更准确的来说是模意义下的乘法逆元。单位元在一个集合中对于某种运算∗如果对于任何的集合元素 a和元素 e 运算得到还是集合元素 a 本身则称 e 为这个运算下的单位元。例如加法运算的单位元是 0乘法的单位元是 1。逆元在一个集合中对于某种运算∗如果任意两个元素的运算结果等于单位元则称这两个元素互为逆元。加法中 a 的逆元是 - a乘法中 a 的逆元是a1即a−1。所以数学上的乘法逆元就是直观上的倒数即ax1x 即为 a 的逆元。对于模意义下的乘法逆元即满足ax≡1(modb)时则称 x 为 a 关于模 b 的逆元。
很容易看出来这是扩展欧几里得的一种运用
扩展欧几里得法 ax≡1(modb)⇒axby1 但是利用以上的欧几里得我们只能求出最近的一个乘法逆元比如3m10得到-3
此时应该进行魔术技巧
x (x % n n) % n
操作把不论正负求取最小正数逆元
费马小定理法
定义若 p 为质数gcd(a,p)1则ap−1≡1 (mod p)。
证明
因为ax≡1(modb)所以ax≡ab−1(modb)故x≡ab−2(modb)
然后就可以用快速幂求解时间复杂度为O(logb)。
ll inv(ll a,ll p){return ksm(a,p-2,p);//ksm上面呢
}
线性求逆元
求出 1-n 中每个数的逆元。
void getinv(ll n){inv[1] 1;for(int i 2; i n; i){inv[i] (p - (p / i)) * inv[p % i] % p;}
} 线性求逆元的递推公式
对于任意一个数 i它的逆元 inv[i] 可以通过如下递推公式计算得出
inv[i](p−⌊p/i⌋)×inv[p%i]%p
推导 我们令 k⌊p/i⌋ 以及 rp%i那么显然有 pk×ir也就是 k×ir≡0(modp)。 对这个同余式进行变形在等式两边同时乘以 i−1×r−1就可以得到 k×r−1i−1≡0(modp)。 进一步移项就能得到 i−1≡−k×r−1(modp)。 为了保证逆元是正数我们把公式调整为 i−1≡(p−k)×r−1(modp)这里的 r 其实就是 p%i。 递推的起始条件 当 i 等于 1 时它的逆元毫无疑问是 1即 inv[1]1这是整个递推过程的起点。 组合数学 基本求法 ll res[N][N];//记忆化避免重复计算
ll C(ll n,ll m){if(m 0 || n m) return 1;if(res[n][m])return res[n][m];//调用记忆return res[n][m] C(n - 1, m) C(n - 1, m - 1);
}
也可以将记忆化演变成动态规划
#includebits/stdc.h
#define ll long long
using namespace std;
int main(){ll n, m, p;cinnmp;ll total n m;vectorvectorll C(total 1, vectorll(total 1, 0)); // 预处理组合数for(int i 0; i total; i){C[i][0] 1 % p;C[i][i] 1 % p;for(int j 1; j i; j){C[i][j] (C[i-1][j] C[i-1][j-1]) % p;}coutC[total][n]endl;return 0;
}
ps:面对过大数据空间会炸 Lucas 定理 ll Lucas(ll n, ll m){if(m 0) return 1;return Lucas(n / p, m / p) * C(n % p, m % p) % p;
} 逆元法求组合利用费马
由于公式
我们想能不能直接利用阶乘自己取模后相除
但是当需要计算 C(n,m)modp 时不能直接对分子和分母分别取模后相除因为模运算的除法不满足分配律
逆元的作用是将模意义下的除法转换为乘法
ps-1不是次方是逆元的意思 ll comb(ll n, ll m, ll p) {//这里n上m下if (m 0 || m n) return 0;// 预处理阶乘数组vectorll fact(n 1, 1);for (ll i 1; i n; i) {fact[i] fact[i - 1] * i % p;}// 计算逆元fact[m]^(-1) 和 fact[n-m]^(-1)ll inv_m mod_pow(fact[m], p - 2, p);ll inv_nm mod_pow(fact[n - m], p - 2, p);//费马// 计算组合数return fact[n] * inv_m % p * inv_nm % p;
} 卢卡斯与逆元结合
include bits/stdc.h
using namespace std;typedef long long ll;// 快速幂计算 a^b % p
ll quick_pow(ll a, ll b, ll p) {ll res 1;while (b 0) {if (b 1) res res * a % p;a a * a % p;b 1;}return res;
}// 计算组合数 C(a, b) % p其中 a pb p
ll comb(ll a, ll b, ll p) {if (b 0 || b a) return 0;if (b 0 || b a) return 1;// 预处理阶乘和逆元vectorll fact(p), inv_fact(p);fact[0] 1;for (int i 1; i p; i) {fact[i] fact[i - 1] * i % p;}inv_fact[p - 1] quick_pow(fact[p - 1], p - 2, p);for (int i p - 2; i 0; --i) {inv_fact[i] inv_fact[i 1] * (i 1) % p;}return fact[a] * inv_fact[b] % p * inv_fact[a - b] % p;
}// 卢卡斯定理计算 C(n, m) % p
ll lucas(ll n, ll m, ll p) {if (m 0) return 1;return comb(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int T;cin T;while (T--) {ll n, m, p;cin n m p;// 计算 C(nm, n) % pcout lucas(n m, n, p) \n;}return 0;
}
卡特兰数 catalan数-CSDN博客 排列组合与容斥原理
1. 排列数公式
从 n 个元素中选 m 个排列Anmn×(n−1)×⋯×(n−m1)n!/(n−m)!。
2. 容斥原理基础
两个集合∣A∪B∣∣A∣∣B∣−∣A∩B∣。三个集合∣A∪B∪C∣∣A∣∣B∣∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣∣A∩B∩C∣。应用场景计算不满足某些条件的元素个数如求 1~n 中不被 2、3、5 整除的数的个数。 快速傅里叶变换FFT
1. 核心作用
加速多项式乘法将暴力O(n2)的复杂度优化到O(nlogn)。原理利用复数单位根的性质将多项式从系数表示转为点值表示相乘后再逆变换回系数表示。
2. 基本步骤
预处理单位根计算复数域上的 n 次单位根。FFT 正变换DFT将多项式转换为点值形式。点值相乘对应点值相乘得到结果多项式的点值表示。逆变换IDFT转换回系数形式 框架搞不懂看不懂不明白所以就贴了个码
const double PI acos(-1);
struct Complex {double x, y;Complex(double x0, double y0) : x(x), y(y) {}
};
Complex operator(Complex a, Complex b) { return Complex(a.xb.x, a.yb.y); }
Complex operator-(Complex a, Complex b) { return Complex(a.x-b.x, a.y-b.y); }
Complex operator*(Complex a, Complex b) { return Complex(a.x*b.x-a.y*b.y, a.x*b.ya.y*b.x); }void fft(Complex *a, int n, int inv) {if (n 1) return;Complex a1[n/2], a2[n/2];for (int i 0; i n; i) {if (i % 2 0) a1[i/2] a[i];else a2[i/2] a[i];}fft(a1, n/2, inv); fft(a2, n/2, inv);Complex w(1, 0), wn(cos(2*PI/n), inv*sin(2*PI/n));for (int i 0; i n/2; i) {a[i] a1[i] w * a2[i];a[in/2] a1[i] - w * a2[i];w w * wn;}if (inv -1) {for (int i 0; i n; i) a[i].x / n;}
}// 计算多项式乘法c a * ba和b的次数分别为n和m
void multiply(ll *a, ll *b, ll *c, int n, int m) {int len 1;while (len n m) len 1;Complex *fa new Complex[len], *fb new Complex[len];for (int i 0; i n; i) fa[i] Complex(a[i], 0);for (int i n; i len; i) fa[i] Complex(0, 0);for (int i 0; i m; i) fb[i] Complex(b[i], 0);for (int i m; i len; i) fb[i] Complex(0, 0);fft(fa, len, 1); fft(fb, len, 1);for (int i 0; i len; i) fa[i] fa[i] * fb[i];fft(fa, len, -1);for (int i 0; i n m; i) c[i] (ll)(fa[i].x 0.5);delete[] fa; delete[] fb;
}
