noip一轮复习真的要开始啦！！！
大概顺序是这样的
1.数学
2.搜索贪心
3.数据结构
4.图论
5.dp
6.其他
数学
1.数论
数论被称为数学皇冠上的明珠，他的重要性主要在于它是其他学习的祖师，基本上什么代数问题都可以通过数论推导，其实有的图论也是（数学上）。
我们信息中的数论主要是说对整除同余的研究~~~~~~~
①：唯一分解定理与素数
这个之前我们先要讲素数（定义全部掠过）
素数筛法：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int prime[],phi[],n,m,k,l,a,b;
bool isprime[];
void shai()
{
int sum=;
memset(isprime,,sizeof(isprime));
memset(prime,,sizeof(prime));
for(int i=;i<=n;i++)
{
if(!isprime[i])
{
prime[sum++]=i;
phi[i]=i-;
}
for(int j=;j<sum&&prime[j]*i<=n;j++)
{
isprime[prime[j]*i]=;
if(i%prime[j]==)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
{
phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
}
}
int main()
{
phi[]=;
cin>>n;
shai();
for(int i=;i<=n;i++)
cout<<phi[i]<<" ";
return ;
}
这里面也有一个叫phi的东西。。。我们一会再说。
筛好以后我们就可以根绝唯一分解定理分解素数
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int prime[],phi[],cut[][],num=,n,m,k,l,a,b;
bool isprime[];
void shai()
{
int sum=;
memset(isprime,,sizeof(isprime));
memset(prime,,sizeof(prime));
for(int i=;i<=;i++)
{
if(!isprime[i])
{
prime[sum++]=i;
phi[i]=i-;
}
for(int j=;j<sum&&prime[j]*i<=n;j++)
{
isprime[prime[j]*i]=;
if(i%prime[j]==)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
{
phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
}
}
int main()
{
phi[]=;
shai();
cin>>m;
for(int i=;i<=;i++){
if(m==)break;
while(m%prime[i]==)m/=prime[i],cut[i][]=prime[i],cut[i][]++;
}
for(int i=;i<=;i++){
if(cut[i][]!=)
cout<<cut[i][]<<" "<<cut[i][]<<endl;
}
return ;
}
省选之后我们发现o跟下n求一个数的唯一分解是不够的
于是就有了miller rabin。
这个东西是根据那个费马小定理（欧拉定理）的p为素数的条件进行的素数测试。
这个东西有个兄弟叫rho
这个东西是用来解决找合数因子的
把主程序里的不断除m改为知道miler检测到为素数为止。
好了那么我们就可以对10^18次方之内的进行分解了（noip只会考on）
那么有什么用呢？
我们把分解后的表示为π（ai^pi）
1.因子数：π（pi+1）；
2.因子和：这个很有意思：
ans=(1+p1^1+p1^2+......+p1^a1)(1+p2^1+p2^2+......+p2^a2)(1+p3^1+p3^2+......+p3^a3)......(1+pn^1+pn^2+......+pn^an)
=π(1-pi^ai)/(1-pi);
这个东西逆元就行。
②快速幂（模数的最广泛应用（二进制））
//ksm
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<stack>
#include<fstream>
#include<cstring>
using namespace std;
#define ll long long
ll qpow(ll a,ll x)
{
ll base=a,ans=;
for(;x>;x>>=)//简单办法
{if(x&)
ans*=base;//当为奇数叠加求解
base*=base;
}
return ans;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".in","r",stdin);
ll a,b;
cin>>a>>b;
cout<<qpow(a,b);
return ;
}
这个东西根据费马小定理可以求逆元
方法是a^(mod-2)=a^(-1)mod mod;
快速乘其实是龟速乘
利用二进制实现调整中途溢出long long的膜意义下乘法
也是利用二进制表示
这样就可解决10^18次方的两个数在%意义下的乘法取模
（其实它是log length的复杂度，并不快，只是比n个相加取模要快（传统防止溢出）所以不是像noi2018龙和勇士那种问题不要乱用）
#include<iostream>
#define mod 1000000007
#define ll long long
using namespace std;
ll ksc(ll a,ll b){
ll ans=,base=a;
for(;b;b>>=){
if(b&)ans=(ans+base)%mod;
base=base*%mod;
}
return ans;
}
ll a,b;
int main(){
cin>>a>>b;
cout<<ksc(a,b);
return ;
}
③exgcd gcd
gcd太熟悉了现打一个
long long gcd(long long a,long long b){
return !b?a:gcd(b,a%b);
}
exgcd也差不多 exgcd也可以求逆元的，这个定义式推。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
}
void exgcd(int a,int b,int &d,int &x,int &y)
{
if(!b){d=a;x=;y=;return ;}
exgcd(b,a%b,d,y,x);
y-=(a/b)*x;
}
int main ()
{
int m,n,k;
cin>>m>>n>>k;
int gc=gcd(n,m);
m/=gc;n/=gc;
k/=gc;
int x,y,d;
cout<<m<<"x+"<<n<<"y="<<gc<<endl;
exgcd(m,n,d,x,y);
cout<<x<<" "<<y<<endl<<d<<endl<<endl;
for(int i=;i<=;i++)
{
x+=(n)*i;
y-=(m)*i;
cout<<x<<" "<<y<<endl;
}
return ;
}
④excrt。crt
excrt 在noip是在不大可能考，要考也是t3的最后一部分，毕竟noi t1难度不是盖的（当时本蒟蒻只拿了三十分那个题。。。。）
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
using namespace std;
long long m[],ma[],a[],c,mall=,ansx;
long long qpowmod(long long a,long long x,long long p)
{
long long base=a,ans=;
for(;x>;x>>=){
if(x&)
ans*=base,ans%=p;
base*=base,base%=p;
}
return ans%p;
}
int main()
{ cin>>c;
for(int i=;i<=c;i++){
cin>>a[i]>>m[i];
mall*=m[i];
}
for(int i=;i<=c;i++){
ma[i]=mall/m[i];
}
for(int i=;i<=c;i++){
ansx+=a[i]*ma[i]*qpowmod(ma[i],m[i]-,mall);
ansx%=mall;
} cout<<mall<<endl<<ansx<<endl;
}
excrt的话就是加一个exgcd就行。
另外 我们需要利用bezout解决问题比如小凯的疑惑
几个简单而熟知的结论
(a,b)=(a+b,b)=(a-b,b)
ax+by=(a,b) x,y∈z
2.计算几何
计算几何noip要是考也是向量题，最多带个凸包。
①向量点积a2b1-a1b2
②凸包：这个东西在斜率优化那里有（那里是个上凸壳），大概是完全一样的。栈维护进出
保证点积>0
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct node{
double x,y;
}p[],s[];
int n;
double ans,mid;
double CJ(node a1,node a2,node b1,node b2)
{
return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double dis(node p1,node p2)
{
return sqrt( (double)(p2.y-p1.y)*(p2.y-p1.y)*1.0+(double)(p2.x-p1.x)*(p2.x-p1.x)*1.0 );
}
bool cmp(node p1,node p2)
{
double tmp=CJ(p[],p1,p[],p2);
if(tmp>) return ;
if(tmp== && dis(p[],p1)<dis(p[],p2)) return ;
return ;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(i!=&&p[i].y<p[].y)
{
mid=p[].y;p[].y=p[i].y;p[i].y=mid;
mid=p[].x;p[].x=p[i].x;p[i].x=mid;
}
} sort(p+,p++n,cmp);
s[]=p[];
int tot=;
for(int i=;i<=n;i++)
{
while(tot>&&CJ(s[tot-],s[tot],s[tot],p[i])<=) tot--;
tot++;
s[tot]=p[i];
}
s[tot+]=p[];
for(int i=;i<=tot;i++) ans+=dis(s[i],s[i+]);
printf("%.2lf\n",ans);
return ;
}
3.递推，矩阵初步与数列
①几个有趣的特殊数列
②ologn求通项的几（两）种方法（noipt2t3）{
1.特征根
这个东西没有任何代码。。。就是求数列通项。
通过特征方程解出跟
然后带a1，a2，a3……an进去
可以看看这个
https://wenku.baidu.com/view/6e270e87284ac850ac024203.html
2.矩阵快速幂
这个十分好理解（在矩阵乘法理解的基础上）我们可以认为数列是一个行向量
而一个n阶递推数列对应一个列向量，所以因此我们就需要找到一个由前一个列向量递推到下一个的矩阵。
这个矩阵可以记一个结论
它是 对于n阶矩阵 ai为系数
n*n大小
[a1,a2,a3,a4,……,an]
[10000000000……00]
[010000000……00]
[0010000000……00]
[00010000000……00]
[000010000000……00]
.
.
[0………………1]
然后 矩阵快速幂！！！
就是矩阵乘法代替那个快速幂的乘就行
代码！！！
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k;
struct mix{
int a[][];
};
mix mx (mix a1,mix a2,int n)
{
mix a3;int ans=;
memset(a3.a,,sizeof(a3.a));
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
ans=;
for(int k=;k<=n;k++)
{
ans+=a1.a[i][k]*a2.a[k][j];
}
a3.a[i][j]=ans;
}
return a3;
}
mix ksm(mix a,int x)
{
mix ans;
memset(ans.a,,sizeof(ans.a));
for(int i=;i<=n;i++)
ans.a[i][i]=;
for(;x;x>>=)
{
if(x&)
mx(ans,a,n);
mx(a,a,n);
}
return ans;
}
int main()
{
mix m1;
cin>>n>>k;
cout<<endl<<n<<endl<<k;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>m1.a[i][j]; mix m=ksm(m1,k);
for(int i=;i<=n;i++)
{
cout<<endl;
for(int j=;j<=n;j++)
{
cout<<m.a[i][j]<<" ";
}
}
cout<<endl<<n<<endl<<n;
return ;
}
}
③关于高斯消元基础（noip不会考于t1t2）{
这个模板是用来解决n阶定方程的
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 100
using namespace std;
int n,m,k,l,a,b,c;double mp[maxn][maxn];
int main(){
cin >> n;
for(int i = ; i <= n; i ++)
for(int j = ; j <= n + ; j ++)
cin >> mp[i][j];
for(int j = ; j <= n; j ++){
int rgt = ;
for(int i = j; i <= n; i ++)
if(mp[i][j]){rgt = i; break;}
if(!rgt)continue;
if(rgt ^ j)swap(mp[rgt],mp[j]); for(int i = j + ; i <= n; i ++){
double div = mp[i][j] / mp[j][j];
for(int k = ; k <= n + ; k ++)mp[i][k] -= div*mp[j][k];
}
}
for(int j = n; j >= ; j --){
if(mp[j][j] == ){cout<<"No Solution"; return ;}
mp[j][n+] = mp[j][n+] / mp[j][j];
for(int i = j-; i >= ; i --)mp[i][n+] -= mp[j][n+] * mp[i][j];
}
for(int i = ; i <= n; i ++)printf("%.2lf\n" ,mp[i][n+]);
return ;
}
高斯消元还可以解决一些异或，异或这个东西跟加法很相似。
因为若 a+(1<<k)&&（a>>k)&1==0 这个时候更加一样，否则就是减。
我们发现高斯消元是on^3的，那么如果让跑1000之内的怎么办呢。
我们就需要一个玄学的东西叫做线型基！
这个东西是一个纯粹的省选算法，noip向了解即可。
}
④基本数列公式
{
1.等比数列求和
2.等差数列求和
3.等差数列性质
}
题目
1.P3938 斐波那契
2.P1306 斐波那契公约数
3.P1962 斐波那契数列
4.P1939 【模板】矩阵加速（数列）
4.函数（积性函数初步）
①三分法{
用于求单峰函数的极值
我们发现如果取两个点（三分之一位置）mid1 mid2
会有三种情况（还有一种是相等，那时候任意都行）
mid1>mid2那么峰值不可能在mid2-r;
mid1<mid2峰值不可能在 l-mid1;
那么我们就会发现递推即可缩小lr
锁定峰值
洛谷搜索三分法有模板
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#define maxn 1000
using namespace std;
double n,m,a,b,mid1,mid2,k[maxn];
double f(double x){
double ans;
ans=k[];
for(int i=;i<=n;i++){
ans+=pow(x,i)*k[i];
}
return ans;
}
double sanfen(double l,double r){
if(r-l<0.000001)return l;
double mid1=(r-l)/+l;
double mid2=r-(r-l)/;
//cout<<f(mid1)<<" "<<f(mid2)<<endl;
if(f(mid1)>f(mid2))r=mid2;
else l=mid1;
return sanfen(l,r);
}
int main(){
cin>>n>>a>>b; for(int i=n;i>=;i--){
cin>>k[i];
}//cout<<f(a)<<" "<<f(b)<<endl;
printf("%.5lf",sanfen(a,b));
return ;
}
这个东西还可以处理凸壳（见计算几何）
}
② 欧拉函数
我在前面写了筛法，自己回去找吧
有用的性质（莫比乌斯反演证明出来的）(Σ（d|n）φ（d）)=n
中间的竖杠，整除的意思。
③莫比乌斯反演初步——这个noip如果考了 ccf就是疯了，真的！！！！！
做题可以看一个叫popoqqq的人的博客最底下。
5.概率论
考过 不难 没啥好总结的 主要是推式子 那就结束吧
省选数学有哪些内容呢？
哎，加油吧！
一维数学
exgcd，crt，excrt，gcd，bsgs，exbsgs，快速幂，龟速乘，哈希，MillerRabin，Ruben rho，线性筛积性函数，素数线性筛，欧拉公式，费马小定理，乘法逆元，欧拉函数优化快速幂，拉格朗日查值，莫比乌斯反演，fft/ntt，杜教筛，高斯函数化简，牛顿迭代，泰勒展开。
计算几何
凸包，半平面交，旋转卡壳，三分法，导数，定积分分析时间复杂度
组合数学(二维数学)
卢卡斯定理，拓展卢卡斯，matrixtree，高斯消元，异或方程，线性基，行列式求值，矩阵乘法，矩乘快速幂，递推数列特征根