背诵内容

内容"/>

背诵内容

坑在继续

1.读入优化

inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c='-') f=-1;c=getchar();}while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();return x*f;
}

2.快速幂

int ksm(int a,int b,int x){int ans=1;while(b!=0){if(b&1) ans=ans*a%c;a=(a*a)%c;b>>=1;}return ans;
}

3.矩阵快速幂

const int N=1e9;struct mat{long long a[100];}ans,mp;mat matrix(mat x,mat y){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){mp.a[i][j]=0;for(int p=1;p<=n;p++)mp.a[i][j]=(mp.a[i][j]+x.a[i][p]*y.a[p][j])%N;}return mp;
} int work(int k){while(k!=0){if(k&1) ans=matrix(ans,shu);shu=matrix(shu,shu);k>>=1;}
}

4.树状数组

int lowbit(int x){return x&(-x);}void add(int x,int d){for(int i=x;i<=n;i+=lowbit(i))b[i]+=d;
}int sum(int p){//求前缀和 ans=0;for(int i=p;i>0;i+=lowbit(i))ans+=b[i];return ans;
}

5.线段树

//从下向上更新
int update(int x){t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum; 
}//向下分支建线段树 
int build(int a,int b){cnt++;int now=cnt;t[now].l=a;t[now].r=b;if(a==b){t[now].sum=q[a];return now;}int mid=(a+b)>>1;t[now].ls=build(a,mid);t[now].rs=(mid+1,b);update (now);return now;
}

6.Spfa

queue<int> q;
int dis[N];
bool vis[N];void Spfa(int s){memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)dis[i]=inf;q.push(s);vis[s]=true;dis[s]=0;while(!q.empty()){int now=q.front();q.pop();vis[now]=false;for(int i=head[now];i;i=e[i].last){int id=e[i].to;if(dis[id]>dis[now]+e[i].w){dis[id]=dis[now]+e[i].w;if(!vis[id])vis[id]=true,q.push(id);}}}
}

7.大小根堆

大根堆：priority_queue<int> Max;
小根堆：priority_queue<int, vector<int>, greater<int> > Min;

8.