树hash

#include <cctype>
#include <chrono>
#include <cstdio>
#include <random>
#include <set>
#include <vector>

typedef unsigned long long ull;

const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();

ull shift(ull x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= mask;
  return x;
}

const int N = 1e6 + 10;

int n;
ull hash[N];
std::vector<int> edge[N];
std::set<ull> trees;

void getHash(int x, int p) {
  hash[x] = 1;
  for (int i : edge[x]) {
    if (i == p) {
      continue;
    }
    getHash(i, x);
    hash[x] += shift(hash[i]);
  }
  trees.insert(hash[x]);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  getHash(1, 0);
  printf("%lu", trees.size());
}

本质不同子序列数量

#include<iostream>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
int n;
const int maxn=1e6+100;
int dp[maxn];
int a[maxn]; 
int last[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        if(!last[a[i]]){
            dp[i]=dp[i-1]*2+1;
        }
        else{
            dp[i]=(dp[i-1]*2-dp[last[a[i]]-1]);
        }
        dp[i]=(dp[i]+mod)%mod;
        last[a[i]]=i;
    }
    cout<<dp[n]<<endl;
}

随机hash

#include <bits/stdc++.h>

using i64 = long long;

bool isprime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int findPrime(int n) {
    while (!isprime(n)) {
        n++;
    }
    return n;
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    
    const int P = findPrime(rng() % 900000000 + 100000000);
    
    
    
    return 0;
}

ac自动机

Ac自动机
#include<cstdio> 
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
using namespace std;
typedef long long ll;
const int N=2e6+5;
const ll mo=1e9+7;
int ch[N][26],now,cnt,l,n,c,size[N],id[N],f[N],g[N];
char s[N];
vector<int> e[N];
queue<int> q;
void ins(int x){
	now=0;
	fo(i,1,l) {
		c=s[i]-'a';
		if (!ch[now][c]) ch[now][c]=++cnt;
		now=ch[now][c];
	}
	id[x]=now;
}
void build(){
	int r,u,v;
	fo(i,0,25) if (ch[0][i]) q.push(ch[0][i]);
	while (!q.empty()) {
		r=q.front(); q.pop();
		fo(i,0,25) {
			u=ch[r][i];
			if (!u) {
				ch[r][i]=ch[f[r]][i];
				continue;	
			}
			v=f[r];
			while (v && !ch[v][i]) v=f[v];
			f[u]=ch[v][i];
			q.push(u);
		}
	}
}
void match() {
	now=0;
	fo(i,1,l) {
		c=s[i]-'a';
		now=ch[now][c];
		g[now]++;
	}
}
void dfs(int x){
	for (int v:e[x]) {
		dfs(v);
		g[x]+=g[v];
	}
}
int main(){
//	freopen("data.in","r",stdin);
	
	scanf("%d",&n);
	fo(i,1,n) {
		scanf("%s",s+1);
		l=strlen(s+1);
		ins(i);
	}
	build();
	
	scanf("%s",s+1);
	l=strlen(s+1);
	match();
	
	fo(i,1,cnt) e[f[i]].eb(i);
	
	dfs(0);
	fo(i,1,n) printf("%d\n", g[id[i]]);

	return 0;
}

广义矩阵乘法+ac自动机

#include<bits/stdc++.h>
#define mk(x,y) make_pair((x),(y))
#define ll long long
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
using namespace std;
ll n, m, v, now, cnt;
const ll inf = 1ll << 60;
const int N=1000;
string s;
int ch[N][26];
ll val[N],f[N];
queue<int> q;
void cmax(ll & x, ll y) {
    x = max(x, y);
}
struct mat {
    ll a[205][205];

    void init() {
        fo(i, 0, cnt) fo(j, 0, cnt) a[i][j] = 0;
    }

    void initMin() {
        fo(i, 0, cnt) fo(j, 0, cnt) a[i][j] = -inf;
    }
	
	void print() {
		fo(i,0,cnt) {
			fo(j,0,cnt) {
				cout<<a[i][j]<<" ";
			}
			cout<<"\n";
		}
	}
};
mat A,t;

mat operator * (mat& a, mat& b) {
    mat c;
    c.initMin();

    fo(i, 0, cnt) fo(j, 0, cnt) fo(k, 0, cnt) {
        cmax(c.a[i][j], a.a[i][k] + b.a[k][j]);
    }        
	return c;
}
void ins() {
    now = 0;
    int c;
    for (int i=0;i<(int)s.length();i++) {
        c = s[i] - 'a';
        if (!ch[now][c]) ch[now][c] = ++cnt;
        now = ch[now][c];
    }
    val[now] += v;
}
void build() {
    fo(i, 0, 25) if (ch[0][i]) q.push(ch[0][i]);
    
    while (!q.empty()) {
        int r = q.front(); q.pop();
        fo(i, 0, 25) {
            int u = ch[r][i];
            if (!u) {
                ch[r][i] = ch[f[r]][i]; continue;
            }

            v = f[r];
            while (v && !ch[v][i]) v = f[v];

            f[u] = ch[v][i];
            val[u] += val[f[u]];
            q.push(u);
        }
    }
}
void power(ll b) {
    while (b) {
        if (b & 1) t = t * A;
        A = A * A;
        b /= 2;
    }
}
signed main() {
	
	// freopen("data.in","r",stdin);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m;
    fo(i, 1, m) {
        cin >> s >> v;
        ins();
    }

    build();
 
    A.initMin();
    fo(i, 0, cnt) {
        fo(j, 0, 25) {
            A.a[ch[i][j]][i] = val[ch[i][j]];
        }
    }

	
    t.init();
    fo(i, 1, cnt) t.a[i][0] = -inf;
    power(n);

    ll ans = -inf;
    fo(i, 0, cnt) ans = max(ans, t.a[i][0]);
    cout << ans;
    return 0;
}

P5787 二分图 /【模板】线段树分治

#include<bits/stdc++.h>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef long long ll;
typedef double db; 
const int N=5e5+5;
int f[N],s[N],n,x,y,top,m,k,f1,f2,ans[N];
struct node{
	int x,y;
};
node st[N];
vector<node> e[N*4];
int find(int x){
	if (x==f[x]) return x;
	return find(f[x]);
}
void merge(int x,int y){
	f1=find(x); f2=find(y);
	if (s[f1]<s[f2]) swap(f1,f2);
	f[f2]=f1;
	s[f1]+=s[f2];
	st[++top]=(node){f1,f2};
}
void del(int now){
	while (top>now) {
		f1=st[top].x; f2=st[top].y; top--;
		s[f1]-=s[f2];
		f[f2]=f2;
	}
}
void upd(int o,int l,int r,int x,int y,int u,int v){
	if (x>y) return;
	if (x<=l && r<=y) {
		e[o].eb((node){u,v});
		return;
	}
	int m=(l+r)>>1;
	if (x<=m) upd(lc,l,m,x,y,u,v);
	if (m<y) upd(rc,m+1,r,x,y,u,v);
}
void ask(int o,int l,int r){
	int now=top;
	bool flag=1;
	for (int i=0;i<(int)e[o].size();i++) {
		f1=find(e[o][i].x); f2=find(e[o][i].y);
		
		if (f1==f2) {
			flag=0;
			break;
		}
		
		merge(e[o][i].x, e[o][i].y+n);
		merge(e[o][i].x+n, e[o][i].y);
	}
	
	if (flag) {
		if (l==r) {
		ans[l]=1;
		}
		else {
			int m=(l+r)>>1;
			ask(lc,l,m);
			ask(rc,m+1,r);
		}
	}
	
	del(now);
}
int main(){
//	freopen("data.in","r",stdin);
	
	int l,r;
	scanf("%d %d %d",&n,&m,&k);
	fo(i,1,n*2) {
		f[i]=i; s[i]=1;
	}
	fo(i,1,m) {
		scanf("%d %d %d %d",&x,&y,&l,&r);
		upd(1,1,k,l+1,r,x,y);
	}
	
	ask(1,1,k);
	fo(i,1,k) if (ans[i]) A; else B;
	
	return 0;
}