【模板】NOIP模板汇总

其他：

洛谷模板：a,b两个字符串，求b串在a串中出现的位置

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char s1[],s2[];

int len1,len2,Next[];

int main(){

    scanf("%s%s",s1+,s2+);

    len1=strlen(s1+);len2=strlen(s2+);

    for(int i=,k=;i<=len2;i++){

        for(;s2[i]!=s2[k+]&&k>;k=Next[k]);

        if(s2[i]==s2[k+])Next[i]=++k;

    }

    for(int i=,k=;i<=len1;i++){

        for(;s1[i]!=s2[k+]&&k>;k=Next[k]);

        if(s1[i]==s2[k+])++k;

        if(k==len2)printf("%d\n",i-len2+),k=Next[k];

    }

    for(int i=;i<=len2;i++)printf("%d ",Next[i]);

    return ;

}

KMP

洛谷模板：n个字符串求有几个不同的串

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<set>

#include<cstring>

using namespace std;

//#define mod 1e9+7//不能这样宏定义

const int mod=1e9+;

#define D 131

#define M 2333+7

long long n,g[M],f[M];

string s;

set<long long>t;

void predeal(int x){

    f[]=s[];

    for(int i=;i<=x;i++)

        f[i]=(1LL*f[i-]*D+s[i-])%mod;

    g[]=;

    for(int i=;i<=x;i++)

        g[i]=1ll*g[i-]*D%mod;

}

int Hash(int l,int r){

    long long a=f[r],b=1LL*f[l-]*g[r-l+]%mod;

    return (a-b+mod)%mod;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        cin>>s;

        long long len=s.length();

        predeal(len);

        long long k=Hash(,len);

        t.insert(k);

    }

    printf("%lld\n",t.size());

    return ;

}

hash

洛谷模板：最长回文串

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int maxn=1e7+;

char s[maxn*],str[maxn*];

int Len[maxn*],len;

void getstr()

{

    int k=;

    str[k++]='$';

    for(int i=;i<len;i++)

        str[k++]='#',

        str[k++]=s[i];

    str[k++]='#';

    len=k;

}

void Manacher()

{

    getstr();

    int mx=,id;

    for(int i=;i<len;i++)

    {

        if(mx>i) Len[i]=min(Len[*id-i],mx-i);

        else Len[i]=;

        while(str[i+Len[i]]==str[i-Len[i]])

            Len[i]++;

        if(Len[i]+i>mx)

            mx=Len[i]+i,id=i;

    }

}

int main()

{

        scanf("%s",&s);

        len=strlen(s);

        Manacher();

        int ans=;

        for(int i=;i<len;i++) ans=max(ans,Len[i]);

        printf("%d\n",ans-);

    return ;

}

Manacher

洛谷模板：快速排序

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,a[],tmp[];

void merge_sort(int l,int r){

    if(l==r)return;

    int mid=(l+r)>>;

    merge_sort(l,mid);

    merge_sort(mid+,r);

    int ii=l,jj=mid+,k=l;

    while(ii<=mid&&jj<=r){

        if(a[ii]<a[jj])tmp[k++]=a[ii++];

        else tmp[k++]=a[jj++];

    }

    while(ii<=mid)tmp[k++]=a[ii++];

    while(jj<=r)tmp[k++]=a[jj++];

    for(int i=l;i<=r;i++)a[i]=tmp[i];

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    merge_sort(,n);

    for(int i=;i<=n;i++)cout<<a[i]<<" ";

    return ;

}

归并排序

洛谷模板：Lucas定理

给定n,m,p(1\le n,m,p\le 10^51≤n,m,p≤105)

求C(n+m,m)

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

int T;

LL n,m,p,f[];

void pre(){

    f[]=;

    for(int i=;i<=p;i++)f[i]=f[i-]*i%p;

}

LL ksm(LL x,LL y){

    LL ret=%p;

    while(y){

        if(y&)ret=ret*x%p;

        x=x*x%p;

        y>>=;

    }

    return ret;

}

LL C(LL n,LL m){

    if(m>n)return ;//*******

    return f[n]*ksm(f[m],p-)%p*ksm(f[n-m],p-)%p;

}

LL Lucas(LL n,LL m){

    if(!m)return ;

    return C(n%p,m%p)*Lucas(n/p,m/p)%p;

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%lld%lld%lld",&n,&m,&p);

        pre();

        printf("%lld\n",Lucas(n+m,m)%p);

    }

    return ;

}

Lucas

洛谷模板：ST表

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int f[][];

int n,m,a,b;

int query(int l,int r){

    int k=log(r-l+)/log();

    return max(f[l][k],f[r-(<<k)+][k]);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&f[i][]);

    for(int i=;i<=;i++)

        for(int j=;j+(<<i)-<=n;j++)

           f[j][i]=max(f[j][i-],f[j+(<<(i-))][i-]);

    for(int i=;i<=m;i++){

        scanf("%d%d",&a,&b);

        printf("%d\n",query(a,b));

    }

}

洛谷模板：矩阵快速幂

#include<iostream>

#include<cstdio>

#include<cstring>

#define mod 1000000007

using namespace std;

int n;

struct matrix{

    long long m[][];

}A;

matrix mul(matrix a,matrix b){

    matrix t;

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            t.m[i][j]=;

            for(int k=;k<=n;k++){

                t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%mod;

            }

        }

    }

    return t;

}

matrix fast_mul(matrix a,long long k){

    matrix ret=a,now=a;

    k--;

    while(k){

        if(k&)ret=mul(ret,now);

        now=mul(now,now);

        k>>=;

    }

    return ret;

}

long long k;

int main(){

    scanf("%d%lld",&n,&k);

    for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

      scanf("%d",&A.m[i][j]);

    A=fast_mul(A,k);

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++)

        printf("%lld ",A.m[i][j]);

        printf("\n");

    }

    return ;

}

矩阵快速幂

洛谷模板：乘法逆元

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 3000010

using namespace std;

int n,p;

int inv[MAXN];

int main(){

    scanf("%d%d",&n,&p);

    inv[]=;

    printf("1\n");

    for(int i=;i<=n;i++){

        inv[i]=(p-p/i)*1ll*inv[p%i]%p;

        printf("%d\n",inv[i]);

    }

}

乘法逆元线性

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

using namespace std;

int n,p;

LL ksm(LL x,LL y){

    int ret=;

    while(y){

        if(y&)ret=1LL*ret%p*x%p;

        x=x*x%p;

        y>>=;

    }

    return ret%p;

}

int main(){

    scanf("%d%d",&n,&p);

    for(int i=;i<=n;i++){

        printf("%lld\n",ksm(i,p-)%p);

    }

    return ;

}

费马小定理

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,p;

void exgcd(int a,int b,int &x,int &y){

    if(b==){

        x=;y=;

        return;

    }

    exgcd(b,a%b,x,y);

    int t=x;x=y;y=t-a/b*y;

}

int main(){

    scanf("%d%d",&n,&p);

    for(register int i=;i<=n;i++){

        int x,y;

        exgcd(i,p,x,y);

        printf("%d\n",(x+p)%p);

    }

    return ;

}

扩展欧几里得

后两个在洛谷T一个点

经典算法：

希望看到有漏下的重要考点能够提出来

感谢

巴特西

【模板】NOIP模板汇总

最新文章

热门文章