树状数组
struct BIT{
int tr[N];
// int inline lowbit(int x){
// return x&(-x);
// }
void add(int k,int x){
for(int i=k;i<=n;i+=lowbit(i)) tr[i]+=x;
}
int query(int k){
int res=0;
for(int i=k;i;i-=lowbit(i)) res+=tr[i];
return res;
}
int ask(int l,int r){// 先左再右
return query(r)-query(l-1);
}
void clear(){
for(int i=0;i<=n+2;i++) tr[i]=0;
}
}tree;
组合数+快速幂
// 快速幂+组合数
int fn[N],fnm[N];
LL qmi(LL a,LL b,LL p){// 快速幂
LL res=1;
while(b){
if(b&1) res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
void intn(){
fn[0]=fnm[0]=1;
for(int i=1;i<N;i++){
fn[i]=(LL)fn[i-1]*i%mod;
fnm[i]=(LL)fnm[i-1]*qmi(i,mod-2,mod)%mod;
}
}
LL C(int a,int b){ // -> C a中选b
//if(a<b) return 0;
return (LL)fn[a]*fnm[b]%mod*fnm[a-b]%mod;
}
LL A(int a,int b){ // A a中b
//if(a<b) return 0;
return (LL)fn[a]*fnm[a-b]%mod;
}
LL inv(LL x){
return qmi(x,mod-2,mod);
}
st表
for(int j=1;j<=log2(n);j++)
for(int i=0;i<=n-(1<<j)+1;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
int l,r; cin>>l>>r;
int len=log2(r-l+1);
max(f[l][len],f[r-(1<<len)+1][len])
线段树
int w[N];
struct code{
int l,r;
}tr[4*N];
void pushup(code&u,code&l,code&r){
}
void pushdown(code&u,code&l,code&r){
}
void pushup(int u){
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void pushdown(int u){
pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
if(l==r){
tr[u]={};
return ;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int x){
if(tr[u].l>= l && tr[u].r<=r){
return ;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,x);
if(r>mid) modify(u<<1|1,l,r,x);
pushup(u);
}
code query(int u,int l,int r){
if(tr[u].l>=l && tr[u].r<=r){
return tr[u];
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else{
code res;
code ll=query(u<<1,l,r);
code rr=query(u<<1|1,l,r);
pushup(res,ll,rr);
return res;
}
}
trie01树的查询之类的操作
LL tr[N*32][2],cnt[N*32],idx;
void insert(int x,LL val){
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(!tr[p][u]) tr[p][u]=++idx;
p=tr[p][u];
(cnt[p]+=val)%mod;
}
}
LL query(int x,int y){
int p=0;
LL res=0;
for(int i=30;i>=0;i--){
int ux=x>>i&1,uy=y>>i&1;
if(uy){
res=(res+cnt[tr[p][ux]])%mod;
if(!tr[p][!ux]) return res;
p=tr[p][!ux];
}
else{
if(!tr[p][ux]) return res;
p=tr[p][ux];
}
}
res=(res+cnt[p])%mod;
return res;
}
void intn(){
for(int i=0;i<=idx;i++)
for(int j=0;j<=1;j++)
tr[i][j]=0,cnt[i]=0;
idx=0;
}
字符串hash
int p[N][2];
LL h[N][2];
const int P0=1e9+3,P1=1e9+7,base=131;
// 超级大数记得base取10
struct Hash{
void intn(int n){
p[0][0]=p[0][1]=1;
for(int i=1;i<=max(n,m);i++){
p[i][0]=p[i-1][0]*base%P0;
p[i][1]=p[i-1][1]*base%P1;
}
}
void get(LL h[][2],string a,int n){
for(int i=1;i<=n;i++){
h[i][0]=(h[i-1][0]*base+a[i]-'0')%P0;
h[i][1]=(h[i-1][1]*base+a[i]-'0')%P1;
}
}
pair<LL,LL> query(LL h[][2],int l,int r){
LL res1=((h[r][0]-h[l-1][0]*p[r-l+1][0]%P0)%P0+P0)%P0;
LL res2=((h[r][1]-h[l-1][1]*p[r-l+1][1]%P1)%P1+P1)%P1;
return {res1,res2};
}
}hx;
struct HasH{
LL h1,h2;
bool operator < (const HasH &B) const
{return h1==B.h1?h2<B.h2:h1<B.h1;}
HasH operator * (const HasH &B) const
{return {h1*B.h1%P0,h2*B.h2%P1};}
}a[N];
map<HasH,int> mp;
矩阵快速幂
void mul(i64 A[],i64 B[][N]){
i64 ans[N]={0};
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
ans[i]=(ans[i]+A[j]*B[i][j])%m;
for(int i=0;i<N;i++)
A[i]=ans[i]%m;
}
void mul(i64 A[][N],i64 B[][N]){
i64 ans[N][N]={0};
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
ans[i][j]=(ans[i][j]+A[i][k]*B[k][j]%m)%m;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
A[i][j]=ans[i][j]%m;
}
扩展欧几里得
ax+by==__gcd(a,b);
// 一定要是a b 的约数
LL exgcd(LL a,LL b,LL&x, LL&y){
if(!b){
x=1,y=0;
return a;
}
LL d = exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
tarjan算法
vector<int> g[N];
int low[N],dfn[N],id[N],scc_cnt,timestamp;
bool is_stk[N];
int stk[N],top;
int dout[N],siz[N];
void tarjan(int u){
dfn[u]=low[u]=++timestamp;
stk[++top]=u,is_stk[u]=true;
for(auto&v:g[u]){
if (!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (is_stk[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u]==dfn[u]){
++scc_cnt;
int y;
do{
y=stk[top--];
is_stk[y]=false;
id[y]=scc_cnt;
siz[scc_cnt]++;
}while(y!=u);
}
}