板子

快读快写

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int read()
{
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')//判负
			w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')//读入数字部分
	{
		s=s*10+c-'0';
		c=getchar();
	}
	return s*w;
}
void print(int x)
{
	if(x<0)//判负
	{
		putchar('-');
		x=-x;
	}
	if(x>=10)
		print(x/10);
	putchar(x%10+'0');
	return;
}

快速幂

ll ksm(ll a,ll p){
    ll ans=1;
    while(p)
    {
        if(p&1)ans=ans*a%mod;
        a=a*a%mod;
        p>>=1;
    }
    return ans;
}

树剖LCA

int dep[N],father[N],son[N],siz[N];
void dfs1(int now,int fa){
//printf("%d %d\n",now,fa);
    siz[now]=1;
    for(int x:G[now]){
        if(x==fa)continue;
        dep[x]=dep[now]+1;
        father[x]=now;
        dfs1(x,now);
        siz[now]+=siz[x];
        if(siz[x]>siz[son[now]])son[now]=x;
    }
}
int top[N],cnt=0;
void dfs2(int now,int fa,int t){
//printf("%d %d %d\n",now,fa,t);
    top[now]=t;
    ++cnt;
    if(son[now]>1)dfs2(son[now],now,t);
    for(auto x:G[now]){
        if(x==fa)continue;
        if(x==son[now])continue;
        dfs2(x,now,x);
    }
}
int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]])u = father[top[u]];
    else v = father[top[v]];
  }
  return dep[u] > dep[v] ? v : u;
}

数位dp记忆化搜索

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int bits[10],dp[10][3];
int dfs(int pos,int threeEight,bool isMax){
    if(!pos)return threeEight==2;
    if(isMax&&dp[pos][threeEight]!=-1)return dp[pos][threeEight];
    int ans=0,maxN=isMax?9:bits[pos];
    for(int i=0;i<=maxN;i++){
        
    }
    if(isMax) dp[pos][threeEight]=ans;
    return ans;
}
int cou(int x){
    int pos=0;
    while(x){
        bits[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0);
}
int main(){
    int n,m;
    memset(dp,-1,sizeof(dp));
    while((cin>>n>>m)&&(n||m)){
        cout<<cou(m)-cou(n-1)<<endl;
    }
}

线段树

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=2e5+7;
typedef long long ll;
#define endl '\n'
#define int long long
int tree[N*4],a[N],b[4*N];
void build(int l,int r,int p){
//cout<<l<<" "<<r<<" "<<p<<endl;
    if(l==r){
        tree[p]=a[l];return;
    }
    int mid=l+((r - l) >> 1);
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    tree[p]=tree[p*2]+tree[p*2+1];
}
int getsum(int l, int r, int s, int t, int p) {// [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
  if (l <= s && t <= r) return tree[p];// 当前区间为询问区间的子集时直接返回当前区间的和
  int m = s + ((t - s) >> 1);
  if (b[p]) {// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
    tree[p * 2] += b[p] * (m - s + 1), tree[p * 2 + 1] += b[p] * (t - m),
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 将标记下传给子节点
    b[p] = 0;                                    // 清空当前节点的标记
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}
void update(int l, int r, int c, int s, int t, int p) {// [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p为当前节点的编号
  if (l <= s && t <= r) {
    tree[p] += (t - s + 1) * c, b[p] += c;
    return;
  }  // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
  int m = s + ((t - s) >> 1);
  if (b[p] && s != t) {// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
    tree[p * 2] += b[p] * (m - s + 1), tree[p * 2 + 1] += b[p] * (t - m);
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 将标记下传给子节点
    b[p] = 0;                                // 清空当前节点的标记
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);
    int op,x,y,k;
    while(m--){
        cin>>op;
        if(op&1){
            cin>>x>>y>>k;
            update(x,y,k,1,n,1);
        }else{
            cin>>x>>y;
            cout<<getsum(x,y,1,n,1)<<endl;
        }
    }
}

欧拉筛

typedef long long ll;
const int N = 1e7 + 7;
int primes[N], pcnt = 0;
bool notprime[N];
inline void pre() {
    notprime[1] = 1;
    for (int i = 2, n = sqrt(N) + 1; i <= n; ++i)
        if (!notprime[i])
        for (int j = N / i; j >= i; --j)
        if (!notprime[j]) notprime[i * j] = 1;
    primes[pcnt++] = 2;
    for (int i = 3; i < N; ++i)
        if (!notprime[i])primes[pcnt++] = i;
}

线性筛

bool st[N];
int prime[N],cnt;
void get_primes(){
    cnt=0;
    memset(st,true,sizeof(st));
    st[1]=st[0]=false;
    for(int i=2;i<=N;i++){
        if(st[i]) prime[cnt++]=i;
        for(int j=0;j<cnt;j++){
            if(i*prime[j]>N) break;
            st[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
}

卢卡斯定理

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll mulit(ll a,ll b,ll m){
    ll ans=0;
    while(b){
        if(b&1) ans=(ans+a)%m;
        a=(a<<1)%m;
        b>>=1;
    }
    return ans;
}
ll quick_mod(ll a,ll b,ll m){
    ll ans=1;
    while(b){
        if(b&1){
            ans=mulit(ans,a,m);
        }
        a=mulit(a,a,m);
        b>>=1;
    }
    return ans;
}
ll comp(ll a,ll b,ll m){
    if(a<b) return 0;
    if(a==b) return 1;
    if(b>a-b) b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0;i<b;i++){
        ca=ca*(a-i)%m;
        cb=cb*(b-i)%m;
    }
    ans=ca*quick_mod(cb,m-2,m)%m;
    return ans;
}
ll lucas(ll a,ll b,ll m){
    ll ans=1;
    while(a&&b){
        ans=(ans*comp(a%m,b%m,m))%m;
        a/=m;
        b/=m;
    }
    return ans;
}
int main()
{
    ll a,b,m;
    while(cin>>a>>b>>m){
        cout<<lucas(a,b,m)<<endl;
    }
    return 0;
}

trie

void insert(string str)
{
    int p=0;
    for(int i=0;str[i];i++){
        int n=str[i]-'a';
        if(trie[p][n]==0)
            trie[p][n]=pos++;
        p=trie[p][n];
        num[p]++;
    }
}
int find(string str)
{
    int p=0;
    for(int i=0;str[i];i++){
        int n=str[i]-'a';
        if(trie[p][n]==0)return 0;
        p=trie[p][n];
    }
    return num[p];
}

欧拉函数

int euler_phi(int n) {//求一个数的欧拉函数
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}