[정수리] 다양한 어려운 템플릿, 지속적인 업데이트

대부분의 템플릿은 코드 세션으로, 일부분의 완전한 프로그램이 있을 수 있습니다
인접표

struct os
{
    int fa,son,next,v;
}a[100000];//  
int first[10000]//  
//  

void add(int x,int y,int z)
{
    a[++tot].fa=x;
    a[tot].son=y;
    a[tot].v=z;
    a[tot].next=first[x];
    first[x]=tot;
}
……
    for (int i=1;i<=m;i++)
    scanf("%d%d%d",&x,&y,&z),
    add(x,y,z),
    //add(y,x,z);        
//  
for (int i=first[x];i;i=a[i].next)
……
//     x     

행렬 곱셈 (mod는 추출 모드)

struct matrix
{
    int map[130][130];
}；
matrix mul(matrix a,matrix b)
{
    matrix c;
    memset(c.map,0,sizeof(c.map));
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    for (int k=1;k<=n;k++)
    c.map[i][j]=(c.map[i][j]+(a.map[i][k]*b.map[k][j]%mod))%mod;
    return c;
}

행렬 쾌속 멱(위에서 사용)

matrix qr(matrix a,int b)
{
    matrix c;
    c=a;
    b--;
    while (b)
    {
        if (b&1) c=mul(c,a);
        a=mul(a,a);
        b>>=1;
    }
    return c;
}

일반 쾌속멱

int qr(int x,int y,int z)
{
    int ans=1;
    x%=z;
    while (y)
    {
        if (y&1) ans=ans*x%z;
        x=x*x%z;
        y>>=1;
    }
    return ans;
}

오라체(1-n의phi와 질수 구하기)

    int prime[1000000],phi[1000000]
    ……
    phi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!pd[i])
        prime[++prime[0]]=i,phi[i]=i-1;
        for (int j=1;j<=prime[0];j++)
        {
            if (prime[j]*i>n) break;
            pd[prime[j]*i]=1;
            if (i%prime[j]==0) {phi[i*prime[j]]=phi[i]*prime[j];break;}
            else phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }

구역원

void exgcd(int a,int b,int &x,int &y)
{
    if (b==0) {x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int x1=y,y1=x-a/b*y;
    x=x1;y=y1;
}
int getinv(int p)
{
    int x,y;
    exgcd(p,r,x,y);
    return (x%r+r)%r;
}

비트 연산 팁:http://blog.csdn.net/xym_csdn/article/details/50725540Lucas의 정리

……
#define LL long long
……
LL lucas(LL p,LL q,LL num)
{
    LL sum=1;
    while (p&&q)
    {
        LL x=p%prime[num],y=q%prime[num];
        if (y>x) return 0;
        sum=(sum*(fac[x]*qr(fac[y]*fac[x-y],prime[num]-2,prime[num]))%prime[num])%prime[num];
        p/=prime[num];
        q/=prime[num];
    }
    return sum;
}
……
for (LL j=1;j<=prime[i];j++)
 fac[j]=fac[j-1]*j%mod;

SPFA(인접 테이블)

#include<bits/stdc++.h>
using namespace std; 
struct os
{
    int fa,son,next,w;
}a[100010];
bool flag[10010];
int first[10010],tot,dis[10010],n,m,x,y,z;
queue <int>q;
void add(int x,int y,int z)
{
    a[++tot].fa=x;
    a[tot].son=y;
    a[tot].w=z;
    a[tot].next=first[x];
    first[x]=tot;
}
main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    scanf("%d%d%d",&x,&y,&z),
    add(x,y,z);
// add(y,x,z);//         
    memset(dis,63,sizeof(dis));
    dis[1]=0;
    q.push(1);
    flag[1]=1;
    while (!q.empty())
    {
        int t=q.front();
        flag[t]=0;
        q.pop();
        for (int i=first[t];i;i=a[i].next)
        {
            int p=a[i].son;
            if (dis[t]+a[i].w<dis[p])
            {
                dis[p]=dis[t]+a[i].w;
                if (!flag[p]) q.push(p),flag[p]=1;
            }
        }
    }
    printf("%d",dis[n]);
}

빠른 읽기

int in()
{
    int f=1,t=0;
    char ch=getchar();
    while (ch>'9'||ch<'0')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') t=t*10+ch-'0',ch=getchar();
    return f*t;
}

진구소 알고리즘

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,x,a[100000];
LL ans;
main()
{
    scanf("%d%d",&n,&x);
    for(int i=0;i<=n;i++) scanf("%d",&a[i]);
    for (int i=n;i>=0;i--)
    ans=ans*x+a[i];
    printf("%lld",ans);
}

단조로운 대기열은 N 길이의 정수 수열 a (i), i = 0, 1,..., N -1과 창 길이 k를 지정합니다.
요구 사항:
f(i)=max(a(i−k+1),a(i−k+2),...,a(i))i=1,2,3,..n

#include<bits/stdc++.h>
using namespace std;
int x,n,k,head=1,tail;
struct os
{
    int data,num;
}q[500000];
main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if (head<=tail&&i-q[head].num>=k) head++;
        while (head<=tail)
        {
            if (q[tail].data>x) break;
            tail--;
        }
        q[++tail].data=x;
        q[tail].num=i;
        if (i>=k) printf("%d ",q[head].data);
    }
}

인접표+더미 최적화 dijskra는 최단거리 대중의 우선순위 비교first>second를 구하기 때문에 dis를first로 간주합니다

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int tot,n,m;
int first[10010],dis[10010];
bool flag[10010];
struct os
{
    int w,u,v,next;
}e[200010];
void add(int x,int y,int z)
{
    e[++tot].u=x;
    e[tot].v=y;
    e[tot].w=z;
    e[tot].next=first[x];
    first[x]=tot;
}
typedef pair<int,int> xy;
priority_queue<xy,vector<xy>,greater<xy> >q; 
main()
{
    scanf("%d%d",&n,&m);
    int x,y,z;
    for (int i=1;i<=m;i++)
    scanf("%d%d%d",&x,&y,&z),
    add(x,y,z),add(y,x,z);//   
    memset(dis,63,sizeof(dis));
    dis[1]=0;
    q.push(make_pair(dis[1],1));
    while (!q.empty())
    {
        xy now=q.top();
        q.pop();
        if (flag[now.second]) continue;
        flag[now.second]=1;
        for (int i=first[now.second];i;i=e[i].next)
        if (dis[now.second]+e[i].w<dis[e[i].v])
        {
            dis[e[i].v]=dis[now.second]+e[i].w;
            if (!flag[e[i].v]) q.push(make_pair(dis[e[i].v],e[i].v));
        }
    }
    printf("%d",dis[n]);
}

kmp 알고리즘

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
char s[100002],ch[102];
int l,next[102];
main()
{
    scanf("%s%s",s,ch);
    for (int i=1;i<strlen(ch);i++)
    {
        int k=i;
        while (ch[i]!=ch[next[k]]&&next[k]) k=next[k];
        next[i+1]=next[k]+(ch[i]==ch[next[k]]);
    }
    int now=0;
    for (int i=0;i<strlen(s);i++)
    {
        while (ch[now]!=s[i]&&now) now=next[now];
        now+=(ch[now]==s[i]);
        if (now==strlen(ch)) {printf("%d
",i-now+1);break;}
    }
}

AC자동기: AC자동기 연습 LCT: 면양모대: 작은 Z의 양말 Splay(이것은 너무 못생겨서 다른 문제를 볼 수 있다): 일반 평형수 가방: 가방 작은 예제 오라 체구φ,μ,d

#include<cstdio>
using namespace std;
int n,prime[1000010];
bool flag[1000010];
int t[1000010],d[1000010],mu[1000010],phi[1000010];
main()
{
    scanf("%d",&n);
    mu[1]=1;d[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!flag[i])
            prime[++prime[0]]=i,
            mu[i]=-1,
            phi[i]=i-1,
            t[i]=i,
            d[i]=2;
        for (int j=1;j<=prime[0];j++)
        {
            if (i*prime[j]>n) break;
            flag[prime[j]*i]=1;
            if (i%prime[j])
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
                mu[i*prime[j]]=-mu[i];
                t[i*prime[j]]=1;
                d[i*prime[j]]=d[i]<<1;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                mu[i*prime[j]]=0;
                t[i*prime[j]]=t[i]+1;
                d[i*prime[j]]=d[i]/(t[i]+1)*(t[i]+2);
                break;
            }
        }
    }

}

O(n) 1-n의 역원(mod는 질수) 증명 구하기

#include<cstdio>
using namespace std;
int n,mod,inv[100000];
main()
{
    scanf("%d%d",&n,&mod);
    inv[1]=1;
    printf("1 ");
    for (int i=2;i<=n;i++)
    inv[i]=(mod-mod/i)*inv[mod%i]%mod,
    printf("%d ",inv[i]);
}