devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

信息学竞赛常用函数/模板

作者：IT小白 | 2024-06-04 03:44:00

赞

踩

信息竞赛常用模板csdn

说明：

1.模板中maxn表示最大数据规模，可以用  常量\，\，\，\，INT\，\，\，\，MAXN=数 定义，其中数为数值

2.对于含有模板的模板，用类似于STL中的map，bitset的方法定义

数学模块

扩展欧几里得算法

说明：用于计算方程通过=dAX+ 其中d=GCD（A，B） 的一组解

  1. void exgcd(int a,int b,int& d,int& x,int& y){
  2.     if(!b){d=a,x=1,y=0;return;}
  3.     exgcd(b,a%b,d,y,x);y-=x*(a/b);
  4. }

　　

乘法逆元

说明：求a的模m乘法逆元（一个−1\，\，MOD\，\，米），其中a，m互质;如果返回值为-1说明无解，建议用参数类型用long long

  1. void exgcd(int a,int b,int& d,int& x,int& y){
  2.     if(!b){d=a,x=1,y=0;return;}
  3.     exgcd(b,a%b,d,y,x);y-=x*(a/b);
  4. }
  5. int inverse(int a,int m){
  6. 	int x,y,d;
  7. 	exgcd(a,m,d,x,y);
  8. 	return d==1?(x%m+m)%m:-1;
  9. }

　　

高精度模板

见：C ++中高精度正整数运算代码模板

O（ SQRTN）计算欧拉函数

  1. int phi(int x){
  2. 	int ans=x,m=sqrt(x+0.01);
  3. 	for(int i=2;i<=m;i++) if(x%i==0){
  4. 		ans=ans/i*(i-1);
  5. 		while(x%i==0) x/=i;
  6. 	}
  7. 	if(x>1) ans=ans/x*(x-1);//x为质数
  8. 	return ans;
  9. }

　　

线性时间复杂度生成欧拉函数表+质数表
  1. /* 
  2. p|n &&  p*p|n phi(n)=phi(n/p)*p
  3. p|n && !p*p|n phi(n)=phi(n/p)*(p-1) 
  4. */ 
  5. int v[maxn],pri[maxn],phi[maxn];
  6. void eular(int n){
  7. 	int num=0;//number of prime 
  8. 	for(int i=2;i<=n;i++) {
  9. 		if(v[i]==0){//v[i]:i 的最小质因子
  10. 			v[i]=i,pri[++num]=i;
  11. 			phi[i]=i-1;
  12. 		}
  13. 		for(int j=1;j<=num;j++){
  14. 			if(pri[j]>v[i]||pri[j]>n/i) break;
  15. 			v[i*pri[j]]=pri[j];
  16. 			phi[i*pri[j]]=phi[i]*(i%pri[j]?pri[j]-1:pri[j]);
  17. 		}
  18. 	}
  19. 	for(int i=1;i<=n;i++) printf("phi(%d)=%d\n",i,phi[i]);
  20. }

　　

BSGS算法

说明：用于计算高次同余方程  ax equivb\，\，（mod\，\，p） 的最小非负数解，其中p为素数，时间复杂度O（ SQRTP\，\），返回-1表示无解

  1. int pow_mod(int a,int n,int p){
  2. 	int ret=1;
  3. 	while(n){
  4. 		if(n&1) ret=(long long)ret*a%p;
  5. 		a=(long long)a*a%p,n>>=1;
  6. 	}
  7. 	return ret;
  8. }
  9. map<int,int>mp;
  10. int bsgs(int a,int b,int p){
  11. 	if(a%p==0) return b?-1:0;
  12. 	mp.clear();
  13. 	int m=ceil(sqrt(p)),T=b%p;
  14. 	mp[T]=0;
  15. 	for(int i=1;i<=m;i++)
  16. 		mp[T=(long long)T*a%p]=i;
  17. 	int t=pow_mod(a,m,p);T=1;
  18. 	for(int i=1;i<=m;i++){
  19. 		T=(long long)T*t%p;
  20. 		if(mp.count(T)) return i*m-mp[T];
  21. 	}
  22. 	return -1;
  23. }

卢卡斯（Lucas）定理

说明：Lucas定理：若 p 为质数，对于整数1⩽m⩽n有Cnm≡CnmodpmmodpCn/pm/p(modp)

代码中函数 C(N,M,p) 用于计算 Cnmmodp ，inv[ i ] 表示 i 模 p 的逆元

  1. int C(int N,int M,int p){
  2.     if(N<M) return 0;
  3.     if(!N) return 1;
  4.     return (ll)fac[N]*inv[fac[M]]*inv[fac[N-M]]%p;
  5. }
  6. int lucas(int N,int M,int p){
  7.     if(M==0) return 1;
  8.     return (ll)lucas(N/p,M/p,p)*C(N%p,M%p,p)%p;
  9. }

扩展中国剩余定理

说明：题目请参考：【模板】扩展中国剩余定理（EXCRT），算法请参考题解释：【模板】扩展中国剩余定理（EXCRT）题解

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int maxn=100005;
  7. #define ll __int128
  8. void exgcd(ll a,ll b,ll& d,ll& x,ll& y){
  9.     if(!b){x=1,y=0,d=a;return;}
  10.     exgcd(b,a%b,d,y,x),y-=x*(a/b);
  11. }
  12. ll gcd(ll a,ll b){
  13.     return b?gcd(b,a%b):a;
  14. }
  15. ll lcm(ll a,ll b){
  16.     return a*b/gcd(a,b);
  17. }
  18. ll a[maxn],b[maxn];
  19. long long a__,b__;
  20. int n;
  21. int main(){
  22.     scanf("%d",&n);
  23.     for(int i=1;i<=n;i++) 
  24.         scanf("%lld%lld",&a__,&b__),a[i]=a__,b[i]=b__;
  25.     for(int i=1;i<n;i++){
  26.         ll a_=a[i],b_=-a[i+1],c_=b[i+1]-b[i],d,x,y,md;
  27.         exgcd(a_,b_,d,x,y);
  28.         if(c_%d){break;/*No answer*/}
  29.         x=c_/d*x,md=b_/d;
  30.         if(md<0) md=-md;
  31.         x=(x%md+md)%md;
  32.         b[i+1]=a[i]*x+b[i];
  33.         a[i+1]=lcm(a[i],a[i+1]);
  34.     }
  35.     printf("%lld\n",(long long)b[n]);
  36.     return 0;
  37. }

矩阵运算

说明：T和MOD可以根据需要修改，其中unit_matrix（n）表示转化为n * n的单位矩阵

  1. struct matrix{
  2. 	#define T int
  3. 	#define MOD 0x7fffffff
  4.     int N,M;
  5. 	T mtx[maxn][maxn];
  6.     matrix(){M=N=0;memset(mtx,0,sizeof(mtx));}
  7.     void resize(int n,int m){N=n,M=m;}
  8.     void unit_matrix(int n){
  9.     	memset(mtx,0,sizeof(mtx));
  10.     	N=M=n;
  11.     	for(int i=0;i<n;i++) mtx[i][i]=1;
  12. 	}
  13.     void input(){//just for int
  14.         for(int i=0;i<N;i++)
  15.           for(int j=0;j<M;j++)
  16.             scanf("%d",&mtx[i][j]);
  17.     }
  18.     void output(){//just for int
  19.         for(int i=0;i<M;i++){
  20.         	for(int j=0;j<N;j++)
  21.         		printf("%d ",mtx[i][j]);
  22.         	putchar('\n');
  23.         }
  24.     }
  25.     friend matrix operator * (matrix x,matrix y){
  26.         matrix ans;
  27.     	if(x.N!=y.M) return ans; //Error
  28.         ans.N=x.N,ans.M=y.M;
  29.         for(int i=0;i<x.N;i++)
  30.           for(int j=0;j<y.M;j++){
  31.             T S=0;
  32.             for(int k=0;k<x.N;k++)
  33.                 S=(S+x.mtx[i][k]*y.mtx[k][j])%MOD;
  34.             ans.mtx[i][j]=S%MOD;
  35.         }
  36.         return ans;
  37.     }
  38.     friend matrix operator ^ (matrix x,int n){
  39.     	matrix ans;
  40.     	if(x.N!=x.M) return ans;//Error
  41.     	ans.unit_matrix(x.N);
  42.     	while(n){
  43.     		if(n&1) ans=ans*x;
  44.     		x=x*x,n>>=1;
  45. 		}
  46. 		return ans;
  47. 	}
  48.     #undef T
  49.     #undef MOD
  50. };

数据结构模块

并查集

  1. struct union_set{
  2. 	int f[maxn];
  3. 	void init(int n){for(int i=1;i<=n;i++) f[i]=i;}
  4. 	int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
  5. 	bool merge(int x,int y){
  6. 		int fx=find(x),fy=find(y);
  7. 		if(fx!=fy) f[fx]=fy;
  8. 		return fx==fy;
  9. 	}
  10. };

链表

数组版

  1. struct node{
  2.     int v,pre,nxt;
  3. };
  4. struct link_list{
  5.     node E[maxn];
  6.     int now,head,tail;
  7.     link_list(){
  8.         now=2,head=1,tail=2;
  9.         E[head].nxt=tail,E[tail].pre=head;
  10.     }
  11.     int insert(int pos,int v){
  12.         now++,E[now].v=v;
  13.         E[E[pos].nxt].pre=now,E[now].nxt=E[pos].nxt;
  14.         E[pos].nxt=now,E[now].pre=pos;
  15.         return now;
  16.     }
  17.     int insert_to_tail(int v){
  18.         return insert(E[tail].pre,v);
  19.     }
  20.     void del(int pos){
  21.         E[E[pos].pre].nxt=E[pos].nxt;
  22.         E[E[pos].nxt].pre=E[pos].pre;
  23.     }
  24. };

指针加强版

  1. template<typename T>
  2. struct node{
  3.     T v;
  4.     node *pre,*nxt;
  5. };
  6. template<typename T>
  7. struct link_list{
  8.     node<T> *head,*tail,*tmp;
  9. 	link_list(){
  10.         head=new node<T>(),tail=new node<T>();
  11.         head->nxt=tail,tail->pre=head;
  12.     }
  13.     node<T>* insert(node<T> *pos,T v){
  14.         tmp=new node<T>();
  15.         tmp->v=v;
  16.         pos->nxt->pre=tmp,tmp->nxt=pos->nxt;
  17.         pos->nxt=tmp,tmp->pre=pos;
  18.         return tmp;
  19.     }
  20.     node<T>* insert_to_tail(T v){
  21.         return insert(tail->pre,v);
  22.     }
  23.     node<T>* insert_to_head(T v){
  24.         return insert(head,v);
  25.     }
  26.     void del(node<T>* pos){
  27.         pos->pre->nxt=pos->nxt;
  28.         pos->nxt->pre=pos->pre;
  29.         delete pos;
  30.     }
  31.     node<T>* pre(node<T>* pos){return pos->pre;}
  32.     node<T>* nxt(node<T>* pos){return pos->nxt;}
  33.     T posv(node<T>* pos){return pos->v;}
  34.     T prev(node<T>* pos){return pos->pre->v;}
  35.     T nxtv(node<T>* pos){return pos->nxt->v;}
  36. };

二叉堆

说明：比起优先队列，多了一个remove操作

  1. template<typename T>
  2. class Heap{
  3.   private:
  4.     T heap[maxn];
  5.     int now;
  6.   public:
  7.     Heap(){now=0;}
  8.     void up(int p){
  9.         while(p){
  10.           if(heap[p]<heap[p/2])
  11.             swap(heap[p],heap[p/2]),p/=2;
  12.           else break;
  13.         }
  14.     }
  15.     void down(int p){
  16.         int p_=p*2;
  17.         while(p_<=now){
  18.             if(p_<now&&heap[p_+1]<heap[p_]) p_++;
  19.             if(heap[p_]<heap[p])
  20.               swap(heap[p_],heap[p]),p=p_,p_*=2;
  21.             else break;
  22.         }
  23.     }
  24.     void push(T v){heap[++now]=v,up(now);}
  25.     void pop(){heap[1]=heap[now--],down(1);}
  26.     void remove(int p){heap[p]=heap[now--],up(p),down(p);}
  27.     T top(){return heap[1];}
  28. };

二维树状数组

说明：支持单点修改，区间求值

简易版

  1. struct BIT_2{
  2.   private:
  3.   	#define lowbit(x) ((x)&-(x))
  4.     int C[maxn][maxn];
  5.   public:
  6.   	void update(int x,int y,int d){
  7.   		for(int i=x;i<=n;i+=lowbit(i))
  8.   		  for(int j=y;j<=m;j+=lowbit(j))
  9.   		    C[i][j]+=d;
  10.     }
  11.     int query(int x,int y){
  12.         int ret=0;
  13.         for(int i=x;i>0;i-=lowbit(i))
  14.           for(int j=y;j>0;j-=lowbit(j))
  15.             ret+=C[i][j];
  16.         return ret;
  17.     }
  18. };

加强版

  1. template<typename T,int N,int M>
  2. class BIT_2{
  3.   private:
  4.   	#define lowbit(x) ((x)&-(x))
  5.     T C[N+1][M+1],N_,M_;
  6.   public:
  7.   	BIT_2(){N_=N,M_=M;}
  8.   	void reset(int n_,int m_){N_=n_,M_=m_;}
  9.   	void update(int x,int y,int d){
  10.   		for(int i=x;i<=N_;i+=lowbit(i))
  11.   		  for(int j=y;j<=M_;j+=lowbit(j))
  12.   		    C[i][j]+=d;
  13.     }
  14.     T query(int x,int y){
  15.         T ret=0;
  16.         for(int i=x;i>0;i-=lowbit(i))
  17.           for(int j=y;j>0;j-=lowbit(j))
  18.             ret+=C[i][j];
  19.         return ret;
  20.     }
  21.     T query(int x,int y,int x_,int y_){
  22.         return query(x_,y_)-query(x-1,y_)-query(x_,y-1)+query(x-1,y-1);
  23.     }
  24. };

Splay

Splay实现平衡树

模板题目见：【模板】普通平衡树，模板修改自洛谷日报，原文+详解见：Splay简易教程

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int maxn=100005;
  6. int fa[maxn],ch[maxn][2],val[maxn],cnt[maxn],sz[maxn],rt,now;
  7. int chk(int x){
  8.     return ch[fa[x]][1]==x;
  9. }
  10. #define pushup(x) sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x]
  11. void rotate(int x){
  12.     int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
  13.     ch[y][k]=w,fa[w]=y;
  14.     ch[z][chk(y)]=x,fa[x]=z;
  15.     ch[x][k^1]=y,fa[y]=x;
  16.     pushup(y),pushup(x);
  17. }
  18. void splay(int x,int goal=0){
  19.     while(fa[x]!=goal){
  20.         int y=fa[x],z=fa[y];
  21.         if(z!=goal){
  22.             if(chk(x)==chk(y)) rotate(y);
  23.             else rotate(x);
  24.         }
  25.         rotate(x);
  26.     }
  27.     if(!goal) rt=x;
  28. }
  29. void rebuild(int x){//将小于等于x的最大元素重建到根
  30.     int cur=rt;
  31.     while(ch[cur][x>val[cur]]&&x!=val[cur])
  32.         cur=ch[cur][x>val[cur]];
  33.     splay(cur);
  34. }
  35. void insert(int x){
  36.     int cur=rt,p=0;
  37.     while(cur&&val[cur]!=x)
  38.         p=cur,cur=ch[cur][x>val[cur]];
  39.     if(cur) cnt[cur]++;
  40.     else{
  41.         cur=++now;
  42.         if(p) ch[p][x>val[p]]=cur;
  43.         ch[cur][0]=ch[cur][1]=0;
  44.         val[cur]=x,fa[cur]=p;
  45.         cnt[cur]=sz[cur]=1;
  46.     }
  47.     splay(cur);
  48. }
  49. int rank(int x){
  50.     rebuild(x);
  51.     return sz[ch[rt][0]];
  52. }
  53. int kth(int k){
  54.     int cur=rt;
  55.     while(true){
  56.         if(ch[cur][0]&&k<=sz[ch[cur][0]])
  57.             cur=ch[cur][0];
  58.         else if(k>sz[ch[cur][0]]+cnt[cur])
  59.             k-=sz[ch[cur][0]]+cnt[cur],cur=ch[cur][1];
  60.         else return cur;
  61.     }
  62. }
  63. int beside(int x,int pre){
  64.     rebuild(x);
  65.     if((val[rt]<x&&pre)||(val[rt]>x&&!pre)) return rt;
  66.     int cur=ch[rt][pre^1];
  67.     while(ch[cur][pre]) cur=ch[cur][pre];
  68.     return cur;
  69. }
  70. void remove(int x){
  71.     int pre=beside(x,1),nxt=beside(x,0);
  72.     splay(pre),splay(nxt,pre);
  73.     int cur=ch[nxt][0];
  74.     if(cnt[cur]>1) cnt[cur]--,splay(cur);
  75.     else ch[nxt][0]=0,sz[nxt]--,sz[pre]--;
  76. }
  77. int main(){
  78.     int c,x,m;
  79.     scanf("%d",&m);
  80.     insert(0x3f3f3f3f);
  81.     insert(-0x3f3f3f3f);
  82.     while(m--){
  83.     	scanf("%d%d",&c,&x);
  84.     	switch(c){
  85.     		case 1:insert(x);break;
  86.     		case 2:remove(x);break;
  87.     		case 3:printf("%d\n",rank(x));break;
  88.     		case 4:printf("%d\n",val[kth(x+1)]);break;
  89.     		case 5:printf("%d\n",val[beside(x,1)]);break;
  90.     		case 6:printf("%d\n",val[beside(x,0)]);break;
  91.         }
  92.     }
  93.     return 0;
  94. }

Splay实现序列翻转

模板题目见：【模板】文艺平衡树（Splay）

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int maxn=100005;
  6. int fa[maxn],ch[maxn][2],val[maxn],cnt[maxn],sz[maxn],rt,now;
  7. int n,m,l,r,rev[maxn];
  8. int chk(int x){
  9.     return ch[fa[x]][1]==x;
  10. }
  11. void pushup(int x){
  12.     sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
  13. }
  14. void pushdown(int x){
  15.     if(!rev[x]) return;
  16.     swap(ch[x][0],ch[x][1]);
  17.     if(ch[x][0]) rev[ch[x][0]]^=1;
  18. 	if(ch[x][1]) rev[ch[x][1]]^=1;
  19.     rev[x]=0;
  20. }
  21. void rotate(int x){
  22.     int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
  23.     ch[y][k]=w,fa[w]=y;
  24.     ch[z][chk(y)]=x,fa[x]=z;
  25.     ch[x][k^1]=y,fa[y]=x;
  26.     pushup(y),pushup(x);
  27. }
  28. void splay(int x,int goal=0){
  29.     while(fa[x]!=goal){
  30.         int y=fa[x],z=fa[y];
  31.         pushdown(z),pushdown(y),pushdown(x);//在这道题里可以不要 
  32.         if(z!=goal){
  33.             if(chk(x)==chk(y)) rotate(y);
  34.             else rotate(x);
  35.         }
  36.         rotate(x);
  37.     }
  38.     if(!goal) rt=x;
  39. }
  40. void insert(int x){
  41.     int cur=rt,p=0;
  42.     while(cur&&val[cur]!=x)
  43.         p=cur,cur=ch[cur][x>val[cur]];
  44.     if(cur) cnt[cur]++;
  45.     else{
  46.         cur=++now;
  47.         if(p) ch[p][x>val[p]]=cur;
  48.         ch[cur][0]=ch[cur][1]=0;
  49.         val[cur]=x,fa[cur]=p;
  50.         cnt[cur]=sz[cur]=1;
  51.     }
  52.     splay(cur);
  53. }
  54. int kth(int k){
  55.     int cur=rt;
  56.     while(true){
  57.         pushdown(cur);
  58.         if(ch[cur][0]&&k<=sz[ch[cur][0]])
  59.             cur=ch[cur][0];
  60.         else if(k>sz[ch[cur][0]]+cnt[cur])
  61.             k-=sz[ch[cur][0]]+cnt[cur],cur=ch[cur][1];
  62.         else return cur;
  63.     }
  64. }
  65. void reverse(int l,int r){
  66.     int x=kth(l),y=kth(r+2);
  67.     splay(x),splay(y,x);
  68.     rev[ch[y][0]]^=1;
  69. }
  70. void output(int x){
  71.     pushdown(x);
  72.     if(ch[x][0]) output(ch[x][0]);
  73.     if(val[x]&&val[x]<=n) printf("%d ",val[x]);//要判断虚拟节点
  74.     if(ch[x][1]) output(ch[x][1]);
  75. }
  76. int main(){
  77.     scanf("%d%d",&n,&m);
  78.     for(int i=0;i<=n+1;i++) insert(i);
  79.     while(m--)
  80.         scanf("%d%d",&l,&r),reverse(l,r);
  81.     output(rt);
  82.     return 0;
  83. }

其他

对拍器

说明：写入记事本，保存为后缀名为。蝙蝠 的文件，即可执行;其中randdata.exe为数据生成器，code1.exe code2.exe分别为测试程序与标准程序。

  1. @echo off
  2. for /l %%i in (1,1,100) do (
  3.   randdata.exe > in.txt
  4.   code1.exe < in.txt > out1.txt
  5.   code2.exe < in.txt > out2.txt
  6.   fc out1.txt out2.txt > result.txt
  7.   if errorlevel 1 echo %%i:WA! && pause
  8.   if not errorlevel 1 echo %%i:AC!
  9. )
  10. pause

快速输入输出（适用于非负整数）

  1. char in_c;
  2. template<typename T>
  3. void scan(T &in_n){
  4. 	for(in_c=getchar();in_c<'0'||in_c>'9';in_c=getchar());
  5. 	for(in_n=0;in_c>='0'&&in_c<='9';in_c=getchar()) in_n=in_n*10+in_c-'0';
  6. }
  7. char out_c[25];
  8. int sz_out_c;
  9. template<typename T>
  10. void print(T out_n){
  11. 	sz_out_c=0;
  12. 	if(!out_n) out_c[sz_out_c++]='0';
  13. 	while(out_n) out_c[sz_out_c++]=out_n%10+'0',out_n/=10;
  14. 	while(sz_out_c--) putchar(out_c[sz_out_c]);
  15. }

 

主要参考资料：

1.《算法竞赛 - 进阶指南》 -李煜东

2.  我校信息学竞赛讲义       -Mr_He

转载于:https://www.cnblogs.com/floatingcloak/p/10343208.html

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/670242
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号