Noip数学整理
目录
- Noip数学整理
- 序
- 1 取模相关
- 2 质数相关
- 3.基本操作
- 4.方程相关
- 5.数列相关
- 6.函数相关
Noip数学整理
序
- 因为某些原因， Noip对于数学方面的考纲仅停留在比较小的一部分，而这一部分
在平常的做题中接触较少我做的题目太少， 为了防止NOIP爆炸， 整理一些Noip的数学知识还是有用的。
1 取模相关
n%p所得结果的正负由n决定，与p无关。如：7%4=3，-7%4=-3，-7%-4=-3---xun学姐- 欧拉定理 \(\alpha^{\phi(p)} \equiv 1 mod(p)\)
- 当p为质数的特殊情况 $\alpha^{p - 1} \equiv 1 $
- Noip2014式取模， 如果f(x) = 0, 那么f(x) % p = 0, 在式子中带入数字看脸计算。
- 常数较小的取模方式
void upd(int &x, int y)
{x += y, x -= x >= mod ? mod : x;
}2 质数相关
质数判定
- 根号判断比较稳
bool check(int x)
{for(int i = 2; i * i <= x; i++)if(x % i == 0)return false;return true;
}- Miller robin比较骚\(-------\)chentongfei
bool check(int x)
{for(int i = 1; i <= 20; i++){int op = read() % x + 1;while(op == x) op = rand() % x + 1;if(poww(op, x - 1, x) != 1) return false;}return true;
}- 线性筛比较经典
void shai()
{isnt[1] = true;for(int i = 2; i <= n; i++){if(!isnt[i]) sta[++tp] = i;for(int j = 1; j <= tp && i * sta[j] <= n; j++){isnt[i * sta[j]] = true;if(i % sta[j] == 0) break;}}
}
- 区间筛比较没用
void shai(ll l, ll r)
{for(int i = 2; i * i <= r; i++){if(!isnt[i]){for(int j = 2 * i; j * j<= r; j += i) isnt[j] = true;for(ll j = max(2ll, (l + i - 1) / i ) * i; j <= r; j += i) vis[j - l] = true;}}for(ll i = 0; i <= b - a; i++) if(!vis[i]) sta[++tp] = i + a;
}质数应用
- 用来取模
3.基本操作
快速幂 or 慢速乘
- ？？？
- O1快速乘吼啊
inline long long multi(long long x,long long y,long long mod) {long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);return tmp<0 ? tmp+mod : tmp;
}
逆元
费马小定理
- 一定要检查一下模数是不是质数啊啊啊啊
exgcd求逆元
\(a * b \equiv 1\; mod\; m\Rightarrow a * b - m * y = 1\) 如果解出\(gcd(a, m) = 1\)， 那么就存在逆元了
int inv(int a, int p)
{int x, y;int tmp = gcd(a, p, x, y);if(tmp != 1) return false;return (x + p) % p;
}质因数分解
根号算法
- 枚举到根号大小就能找出所有质因子了
pollard-Robin
- 基于随机化， 鸽笼定理， floyd判环的算法
- 写起来挺舒适的
bool robin_miller(ll n) { //判断是否素数if(n < 2) return false;if(n == 2) return true;if(!(n & 1)) return false;ll u = n - 1, t = 0;while(!(u & 1)) u >>= 1, t++;if(t >= 1 && (u & 1) == 1) {for(int i = 0; i < s; i++) {ll a = rand() % (n-1) + 1;if(witness(a, n, u, t)) return false; //不是素数}}return true; //是素数
}ll gcd(ll a, ll b) {if(a == 0) return 1;if(a < 0) return gcd(-a, b);while(b) {ll t = a % b;a = b;b = t;}return a;
}ll pollard_rho(ll x, ll c) {ll i = 1, x0 = rand() % x;ll y = x0;ll k = 2;for(;;) {i++;x0 = (multi_mod(x0, x0, x) + c) % x;ll d = gcd(y - x0, x);if(d != 1 && d != x) return d; if(y == x0) return x;if(i == k) {y = x0;k += k;}}
}void find_fac(ll n) {if(n == 1) return;if(robin_miller(n)) {prime_factor.push_back(n);return;}ll p = n;while(p >= n) p = pollard_rho(p, rand() % (n-1) + 1);find_fac(p);find_fac(n / p);
}
4.方程相关
不定方程
- 扩展欧几里得求同余方程 \(ax + by = \gcd(a, b)\)
int exgcd(int a, int b, int &x, int &y)
{if(!b){x = 1, y = 0;return a;}int ans = exgcd(b, a % b, x, y), tmp = x;x = y, y = tmp - a / b * y;return ans;
}- 得到的解只是一组 \(ax + by = g\)， 让\(x += g / b, y -= g/a\)依旧成立
- 所以通解可以表示成\(x = x_1 + \frac{b}{\gcd(a,b)}, y = y_1 + \frac{a}{gcd(a, b)}\)
- 对于求解\(ax + by = c\)的同余方程， 首先判断c是否是\(\gcd(a, b)\)的倍数， 不是的话则无解
- 然后求出\(ax + by = \gcd(a, b)\) 的一组解， 之后让xy都乘以 \(g / \gcd(a, b)\)即可
线性同余方程组
- 互质情况： 中国剩余定理
- 求解
\[ x \equiv a_1\; mod\; m_1 \]
\[ x \equiv a_2\; mod\; m_2 \]
\[ x \equiv a_3\; mod\; m_3 \]
\[ x \equiv a_4\; mod\; m_4 \]
得到的通解可以表示成
\[ x = kM + \sum_{i = 1}^{n}a_it_iM_i \]
其中\(k \in Z\; M = \prod m_i\; M_i = \frac{M}{M_i}\; t_i = M_i^{-1}\; mod m_i\)
int cn(int n)
{int sum = 1, ans = 0, x, y;for(int i = 1; i <= n; i++) sum *= m[i];for(int i = 1; i <= n; i++){int op = sum / m[i];int zz = exgcd(op, m[i], x, y);ans = (ans + g[i] * op * x) % sum; }return (sum + ans) % sum;
}- 不互质情况， 扩展中国剩余定理
- 感觉和中国剩余定理不是很相似， 主要是基于方程的合并
首先考虑两个同余方程
\[ x \equiv a_1\; mod\; m_1\\ x \equiv a_2\; mod\; m_2 \]化成另一个形式
\[ x = n_1 * m_1 + a_1\\ x = n_2 * m_2 + a_2 \]
- 联立可得
\[ n_1 * m_1 + a_1 = n_2 * m_2 + a_2\\ n_1 * m_1 - n_2 * m_2 = a_2 - a_1 \] - 有解的前提是
\[ \gcd(m_1, m_2) |(a_2 - a_1) \] - 设
\[ d = \gcd(m_1, m_2)\\ c = a_2 - a_1 \] - 则
\[ n_1 \frac{m_1}{d} - n_2 \frac{m_2}{d} = \frac{c}{d}\\ n_1 \frac{m_1}{d} \equiv \frac{c}{d} \ mod \ \frac{m_2}{d} \] - 移项
\[ n_1 \equiv \frac{c}{d} * inv(\frac{m_1}{d}, \frac{m_2}{d}) \ mod\ \frac{m_2}{d}\\ n_1 = \frac{c}{d} * inv(\frac{m_1}{d}, \frac{m_2}{d}) + y_1 * \frac{m_2}{d} \]
然后\(n_1\)代入最上面的狮子可以得到
\[ x = (\frac{c}{d} * inv(\frac{m_1}{d}, \frac{m_2}{d}) + y_1 * \frac{m_2}{d}) * m_1 + a_1\\ x = m_1 * \frac{c}{d} * inv(\frac{m_1}{d}, \frac{m_2}{d}) + y_1 * \frac{m_2 m_1}{d} + a_1\\ x \equiv m_1 * \frac{c}{d} * inv(\frac{m_1}{d}, \frac{m_2}{d}) + a_1 \ mod \ \frac{m_2 m_1}{d} \]
- 然后就是个新方程了
- 当然也适用于互质情况
- 板子
int ex_crt()
{int a1 = a[1], m1 = m[1], a2, m2;for(int i = 2; i <= n; i++){a2 = a[i], m2 = m[i];int c = a2 - a1;int d = gcd(m2, m1);if(c%d) return -1;ll k = inv(m1 / d, m2 / d);a1 = a1 * c / d * k + a1;m1 = m1 * m2 / d;}return a1;
}
裴蜀定理
- 对于方程 \(ax + by = c\) 有解当且仅当 \(\gcd(a,b) | c\) 可以扩展到多元， 经常被出题人用来出套路题
5.数列相关
卡特兰数
- 前几项！！！！ \(1\ 1\ 2\ 5\ 14\ 42\ 132\)
递推式
\[ C_n = \sum_{i = 1}^{n - 1} C_i * C_{n - i} \\ C_n = C_{n - 1} * (4n - 2)/ (n + 1) \]
组合式
\[ h(n) = C_{2n}^{n} - C_{2n}^{n - 1}\\ h(n) = \frac{C_{2n}^{n}} { (n + 1)} \]
意义
- 括号化问题。矩阵链乘： P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
- 将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数
- 出栈次序问题。一个栈(无穷大)的进栈序列为1、2、3、...、n，有多少个不同的出栈序列?
- 给顶节点组成二叉树的问题。
组合数
求法
杨辉三角
可更改性比较好， 适用于非质数取模
阶乘法
预处理On， 计算一次logn， 需要On的空间
卢卡斯定理
适用于模数较小且为质数
\[ Lucas(n, m, p) = C_{n \% p}^{m \% p} * Lucas(n/p, m/p, p) \]扩展卢卡斯
- 适用于模数较小非质数或者模数较大但是分解后因子较小
- 相当于我们对于模数分解后分别求出在mod某个数字下组合数是多少
- 然后使用crt合并就好了
- 当质因数分解不干净的时候， 我们要求\(Lucas(n, m, p^t)\)这个也是个问题
- 这里利用循环节来统计阶乘中不含p因子的数字乘积， 对于含p因子的提出来递归计算
- Noip考这个我直播吃拖鞋
- 贴个板子
#include
using namespace std;int t,opt;
long long p[50],a[50];//存储质因数p的t次方,a存储CRT要用的余数
map mp;
long long ji;
inline long long ksm(long long x,long long y,long long mod)
{long long res=1;while(y){if(y&1)res=(res*x)%mod;x=(x*x)%mod;y>>=1;}return res;
}
inline void exgcd(long long a,long long b,long long &x,long long &y)
{if(!b){x=1;y=0;}else{exgcd(b,a%b,y,x);y-=a/b*x;}
}
inline long long inv(long long a,long long b)
{long long x=0,y=0;exgcd(a,b,x,y);x=(x%b+b)%b;if(!x)x+=b;return x;
}
inline long long cal(long long n,long long x,long long mod)//递归计算除了x的若干次方之外的部分(第一、第三部分)
{if(!n)return 1;long long ans=1;//提出来的那些不含因子x的乘积 if(n/mod)//有整块的 {for(int i=1;i<=mod;++i){if(i%x)//不含因子xans=ans*i%mod;}ans=ksm(ans,n/mod,mod);//有循环节，所以乘积用快速幂计算即可 }for(int i=n/mod*mod+1;i<=n;++i){if(i%x)ans=ans*i%mod;}return ans*cal(n/x,x,mod)%mod;//当前的不含因子x的乘积乘以递归下去求的剩余阶乘部分的结果
}
//计算出对于每一个质数的若干次方取模后的结果
inline long long exlucas(long long m,long long n,long long x,long long mod)//x是当前质数
{if(n>m)return 0;int cnt=0;for(int i=m;i;i/=x)cnt+=i/x;for(int i=n;i;i/=x)cnt-=i/x;for(int i=m-n;i;i/=x)cnt-=i/x;long long ans=ksm(x,cnt,mod)*cal(m,x,mod)%mod*inv(cal(n,x,mod),mod)%mod*inv(cal(m-n,x,mod),mod)%mod;return ans*(ji/mod)%ji*inv(ji/mod,mod)%ji;//CRT合并！
}
inline long long gcd(long long x,long long y)
{return y?gcd(y,x%y):x;
} int main()
{scanf("%d",&t);while(t--){scanf("%d",&opt);if(opt==1){long long x,y,p;scanf("%lld%lld%lld",&x,&y,&p);printf("%lld\n",ksm(x,y,p));}else if(opt==2){mp.clear();long long aa,b,p;int pd=0;scanf("%lld%lld%lld",&aa,&b,&p);if(b==1){printf("0\n");pd=1;}if(pd==1)continue;long long d=gcd(aa,p),t=1,k=0;while(d!=1){if(b%d){printf("Math Error\n");pd=1;break;}++k;b/=d;p/=d;t=(t*(aa/d))%p;if(b==t){printf("%lld\n",k);pd=1;break;}d=gcd(aa,p); }if(pd==1)continue;long long m=ceil(sqrt(p)),ans;for(int j=0;j<=m;++j){if(j==0){ans=b%p;mp[ans]=j;continue;}ans=(ans*aa)%p;mp[ans]=j;}long long x=ksm(aa,m,p);ans=t;for(int i=1;i<=m;++i){ans=(ans*x)%p;if(mp[ans]){x=i*m-mp[ans];printf("%lld\n",x+k);pd=1;break;}}if(!pd)printf("Math Error\n");}else {long long x,y,mod;scanf("%lld%lld%lld",&x,&y,&mod);ji=mod;//mod就是CRT的那个因子乘积和！ if(mod==1){printf("0\n");continue;}memset(p,0,sizeof(p));memset(a,0,sizeof(a));int cnt=0;//记录质数个数 for(int i=2;i*i<=mod;++i){if(mod%i==0){p[++cnt]=1;while(mod%i==0){p[cnt]*=i;mod/=i;//把当前因子除掉对看是否是后面数的倍数无影响 }a[cnt]=exlucas(y,x,i,p[cnt]); }} if(mod>1){p[++cnt]=mod;a[cnt]=exlucas(y,x,mod,mod);}long long res=0;for(int i=1;i<=cnt;++i)res=(res+a[i])%ji;printf("%lld\n",res);}}return 0;
}常见模型和性质
奇偶性
- 当且仅当
n & m == m时 \(C_n^m\) 为奇数
插板法
- n种元素，每种可选择任意次或者不选，共选m
\[ C_{n +m - 1} ^{n - 1} \]
全错排公式
\[ f[i] = (i - 1)(f[i - 1] + f[i - 2]) \]
情况1:插入第i个元素时，前i-1个已经错位排好，则选择其中任意一个与第i个互换一定满足要求,选择方法共i-1种，前i-1位错排f[i-1]种，记f[i-1]*(i-1)
情况2:插入第i个元素时，前i-1个中恰有一个元素a[j]使得a[j]=j，其他i-2个错位排好，则将i与j交换，j在i-2位中的插入共i-1种，前i-2位错排f[i-2]种，记f[i-2]*(i-1)
6.函数相关
- Noip函数？？？
- 貌似只有一次函数合二次函数了吧QAQ
转载于:https://www.cnblogs.com/luoyibujue/p/10505348.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！