早期模板整理_牛客博客

数论

最大公约数/欧几里得算法/裴蜀定理

求非负整数a,b的最大公约数 (如果a,b可能为负数的话就提前让a和b取绝对值)
int gcd(int a,int b){
       int tmp;
       while(b!=0){
           tmp=a%b;a=b;b=tmp;}
       return a;
}
扩展欧几里得

a*x+b*y=gcd(a,b)求解gcd(a,b)以及x和y
int ex_gcd(int a,int b,int &x,int &y){//a*x+b*y=1
   if(b==0){x=1,y=0;return a;}
   int d=ex_gcd(b,a%b,x,y);
       int tmp=x;
       x=y;
       y=tmp-(a/b)*y;
       return d;
   }
中国剩余定理（Chinese Remainder Theorem）

求解满足x=a[i](modm[i])的最小正整数x (其中m[i]需要两两互质）。 //需要ex_gcd()
int CRT(){//n为方程组数
   int Mi,xi,yi,d,ans=0,M=1;
   for(int i=1;i<=n;i++) M*=m[i];
       for(int i=1;i<=n;i++){
          Mi=M/m[i];
          //Mi*xi=1(modm[i])<=>Mi*xi+m[i]*yi=1
           d=ex_gcd(Mi,m[i],xi,yi);
           ans=(ans+Mi*xi*a[i])%M;
        }
        return (ans+M)%M;
   }
扩展中国剩余定理（Extended Chinese Remainder Theorem）

//需要ex_gcd()

如果函数返回 -1，表示方程组无解 时间复杂度：O(nlogM)，其中 n 是同余方程的个数，M 是所有模数的乘积。
int EX_CRT(){
   int aa=b[1],rr=a[1],x,y;
   for(int i=2;i<=n;i++){
          int bb=b[i];
          int c=a[i]-rr;
           int d=ex_gcd(aa,bb,x,y);
           if(c%d) return -1;
           c=c/d, bb=bb/d;
           x=(x*c%bb+bb)%bb;
           int lcm=aa*bb;
           rr=(x*aa%lcm+rr)%lcm;
           aa=lcm;
        }
        return rr=0?aa:rr;
   }
欧拉线性筛/质数线性筛(get_prime)

求小于N的所有素数，vis[i]返回i是不是质数(1/0)，p[1...cnt]储存前p[0]个质数。
bool vis[N];
int p[N];
void get_prime(){
  for(int i=2;i<N;i++){
      if(!vis[i]) p[++p[0]]=i;
           for(int j=1;j<=p[0]&&i*p[j]<N;j++){
               vis[i*p[j]]=1;
               if(i%p[j]==0) break;
           }
       }
    }
欧拉函数

·1.求正整数n的欧拉函数φ(n)
int phi(int x){
int res=x;
for(int i=2;i*i<=x;i++){
      if(x%i==0){
          res=res-res/i;
           while(x%i==0) x/=i;
       }
    }
    if(x>1) res=res-res/x;
   return res;
   }
·2.欧拉函数的线性求法

在欧拉线性筛的基础上增加的功能，在求质数的同时计算欧拉函数。
int phi[N],p[N];
bool vis[N];
void lin_phi(){
   phi[1]=1;
   for(int i=2;i<=n;i++){
          if(!vis[i]) p[++p[0]]=i,phi[i]=i-1;//φ(p)=p-1
          for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
               vis[i*p[j]]=1;
               if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
               phi[i*p[j]]=phi[i]*(p[j]-1);
           }
        }
    }
扩展欧拉函数/欧拉降幂(ex_eular)

//需要phi()和ksm()
int ex_eular(int a,string b,int c){//a**b(modc)
   int ans=0,phic=phi(c);
   bool flag=0;//标记b是否大于等于φ(c)
       for(int i=0;i<b.size();i++){
          ans=ans*10+(b[i]-'0');
          if(ans>=phic){ans%=phic;flag=true;}
        }
        if(flag) ans+=phic;  
       return ksm(a,ans,c);
   }
附：带(mod c)快速幂
int ksm(int a,int b,int c){
  int ans=1;
  while(b){
           if(b&1) ans=(ans*a)%c;
           b>>=1;
           a=(a*a)%c;
       }
       return ans;
    }
    ```

---

---

线段树

线段树1

int n,m,a[N],op,x,y,k;
struct node{
       int sum,lazy=0;
}t[N<<2];
void build(int x,int l,int r){
       if(l==r){t[x].sum=a[l];return;}
       build(x<<1,l,mid);
       build(x<<1|1,mid+1,r);
       t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
void down(int x,int l,int r){
       if(t[x].lazy){
           t[x<<1].sum+=t[x].lazy*(mid-l+1);
           t[x<<1].lazy+=t[x].lazy;
           t[x<<1|1].sum+=t[x].lazy*(r-mid);
           t[x<<1|1].lazy+=t[x].lazy;
           t[x].lazy=0;
       } 
}
void update(int x,int l,int r,int L,int R,int k){
       if(L<=l&&r<=R){
           t[x].sum+=k*(r-l+1);
           t[x].lazy+=k;
           return;
       }
       down(x,l,r);
       if(L<=mid) update(x<<1,l,mid,L,R,k);
       if(mid+1<=R) update(x<<1|1,mid+1,r,L,R,k);
       t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
int query(int x,int l,int r,int L,int R){
       if(L<=l&&r<=R) return t[x].sum;
       if(L>r||R<l) return 0;
       down(x,l,r);
       return query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R);
}

线段树2

struct node{
       int sum,add,mul;
}t[N<<2];
int n,m,L,R,q,op,k,a[N];
void build(int x,int l,int r){
       if(l==r){t[x]={a[l],0,1};return;}
       build(x<<1,l,mid);
       build(x<<1|1,mid+1,r);
       t[x]={(t[x<<1].sum+t[x<<1|1].sum)%m,0,1};
}
void down(int x,int l,int r){
       if(t[x].mul!=1||t[x].add!=0){
           t[x<<1].sum=(t[x<<1].sum*t[x].mul+t[x].add*(mid-l+1))%m;
           t[x<<1|1].sum=(t[x<<1|1].sum*t[x].mul+t[x].add*(r-mid))%m;
           t[x<<1].mul=(t[x<<1].mul*t[x].mul)%m;
           t[x<<1|1].mul=(t[x<<1|1].mul*t[x].mul)%m;
           t[x<<1].add=(t[x<<1].add*t[x].mul+t[x].add)%m;
           t[x<<1|1].add=(t[x<<1|1].add*t[x].mul+t[x].add)%m;
           t[x].mul=1,t[x].add=0;
       }
}
void update_add(int x,int l,int r){
       if(L<=l&&r<=R){
           t[x].sum+=k*(r-l+1);
           t[x].sum%=m;
           t[x].add=(t[x].add+k)%m;
           return;
       }
       down(x,l,r);
       if(mid>=L) update_add(x<<1,l,mid);
       if(mid<R) update_add(x<<1|1,mid+1,r);
       t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%m;
}
void update_mul(int x,int l,int r){
       if(L<=l&&r<=R){
           t[x].sum=t[x].sum*k%m;
           t[x].mul=(t[x].mul*k)%m;
           t[x].add=t[x].add*k%m;
           return;
       }
       down(x,l,r);
       if(mid>=L) update_mul(x<<1,l,mid);
       if(mid<R) update_mul(x<<1|1,mid+1,r);
       t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%m;
}
int query(int x,int l,int r){
       if(L<=l&&r<=R){return t[x].sum;}
       if(r<L||l>R){return 0;}
       down(x,l,r);
       return (query(x<<1,l,mid)+query(x<<1|1,mid+1,r))%m;
}

STL

Bitset:

![f60d1be339418ce0f7f63d98847913a](../WeChat Files/wxid_8h8yrput2dqw22/FileStorage/Temp/f60d1be339418ce0f7f63d98847913a.png)

高斯消元

P2455 [SDOI2006] 线性方程组

题目描述

已知 $n$ 元线性一次方程组。

$\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}$

请根据输入的数据，编程输出方程组的解的情况。

输入格式

第一行输入未知数的个数 $n$ 。
接下来 $n$ 行，每行 $n + 1$ 个整数，表示每一个方程的系数及方程右边的值。

输出格式

如果有唯一解，则输出解。你的结果被认为正确，当且仅当对于每一个 $x_i$ 而言结果值与标准答案值的绝对误差或者相对误差不超过 $0.01$ 。

如果方程组无解输出 $-1$ ；如果有无穷多实数解，输出 $0$ ；

输入 #1

输出 #1

x1=1.00
x2=0.00
x3=-1.00

【数据范围】
对于 $100\%$ 的数据， $1 \le n \le 50$ 。对于 $\forall 1\le i, j \le n$ ，有 $|a_{i, j}| \le 100$ ， $|b_i| \le 300$ 。

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
const int N=1e2+5;
int n,m;
double a[N][N];
int gauss(int n,int m){//n行m+1列的增广矩阵:a[0..n-1][0..n]
   int r=0;//r:有效方程数(矩阵的秩),操作时的行下标
   for(int c=0;c<m;++c){//遍历列 c:列下标
      	int t=r;
      	for(int i=r;i<n;++i)//寻找列主元
          		if(fabs(a[i][c])>fabs(a[t][c]))
              		t=i;
      	if(fabs(a[t][c])<eps) continue;//若主元列为0，不考虑，当前全列为0
      	//交换列主元t行与当前r行的数
      	for(int j=c;j<=m;j++) swap(a[t][j],a[r][j]);
      	for(int j=m;j>=c;j--) a[r][j]/=a[r][c];//使得主对角线系数均为1
      	for(int i=r+1;i<n;i++)//与r+1~n-1进行消元
        		if(fabs(a[i][c])>eps)
             		for(int j=m;j>=c;j--)
                  		a[i][j]-=a[r][j]*a[i][c];
     	 	++r;             
   }
   for(int i=r;i<n;i++)
      	if(fabs(a[i][m])>eps)
          		return 2;//无解
   if(r<m) return 1;//无穷多解    
   for(int i=m-1;i>=0;i--)//回代求解方程
      	for(int j=i+1;j<m;j++)
          		a[i][m]-=a[j][m]*a[i][j];
   return 0;//一般情况(有唯一确定解）             
}
signed main(){
   cin>>n;
   for(int i=0;i<n;i++)
      for(int j=0;j<=n;j++)
          cin>>a[i][j];
   int flag=gauss(n,n);
   if(flag==1) cout<<0;
   else if(flag==2) cout<<-1; 
   else for(int i=0;i<n;i++) printf("x%d=%.2lf\n",i+1,a[i][n]);
}

矩阵快速幂

const int siz=2;
struct matrix{int m[siz+1][siz+1];};
matrix operator *(const matrix& a,const matrix& b){//广义乘法运算（可自定义）
      matrix c;memset(c.m,0,sizeof(c.m));
      rep(i,1,siz)rep(j,1,siz)rep(k,1,siz)
          c.m[i][j]=(a.m[i][k]*b.m[k][j]+c.m[i][j])%mm;
      return c;
}
matrix ksm(matrix a,int k){
      matrix ans=a;
      k--;
      while(k){
          if(k&1) ans=ans*a;
          a=a*a;k>>=1;
      }
      return ans;
}

Manacher(马拉车)

const int N=1.1e7+5;
char s[N<<1];//修改串
int d[N<<1];//回文半径函数
int getstr(string str){//返回修改串后的长度
   int k=0;
   s[0]='@',s[++k]='#';
   for(auto u:str){
       s[++k]=u;
       s[++k]='#';
   }
   s[k+1]='$';
   return k;
}
void manacher(int n){
   d[1]=1;
   for(int i=2,l,r=1;i<=n;i++){
       if(i<=r) d[i]=min(d[r-i+l],r-i+1);
       while(s[i-d[i]]==s[i+d[i]]) d[i]++;
       if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
   }
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   string str;
   cin>>str;
   int len=getstr(str);
   manacher(len);
   int ans=0;
   rep(i,1,len) ans=max(ans,d[i]-1);
   cout<<ans;
   return 0;
}

kmp

const int N=1e6+5;
int nxt[N];//模式串P[1,i]中最长相等前后缀的长度
int ls,lp;//ls:S的长度,lp:P的长度
string S,P;
void kmp(){
   cin>>S>>P;
   ls=S.size(),lp=P.size();
   S=" "+S,P=" "+P;
   nxt[1]=0;
   for(int i=2,j=0;i<=lp;i++){
       while(j&&P[i]!=P[j+1]) j=nxt[j];
       if(P[i]==P[j+1]) j++;
       nxt[i]=j;
   }
   for(int i=1,j=0;i<=ls;i++){
       while(j&&S[i]!=P[j+1]) j=nxt[j];
       if(S[i]==P[j+1]) j++;
       if(j==lp) cout<<i-lp+1<<endl;
       //按从小到大的顺序输出P在S中出现的位置
   }
   for(int i=1;i<=lp;i++) cout<<nxt[i]<<" ";
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   kmp();
   return 0;
}