SAM 板子题。
在 P3804 【模板】后缀自动机 (SAM) 中,我们已经会求每个等价类(SAM 状态)在原串中的出现次数。
本题中,我们需要求所有长度能被出现次数整除的子串。我们知道一个等价类中的所有字符串的长度构成一段整数区间 \([\operatorname{minlen}(v),\operatorname{maxlen}(v)]\),其中 \(\operatorname{minlen}(v)=\operatorname{maxlen}(\operatorname{link}(v))\)。于是想到将每个整数的因数打表到 vector 中,然后二分即可统计这一等价类中有多少子串符合条件。
复杂度 \(\mathcal O(n\log n)\)。
// Problem: CF1780G Delicious Dessert
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1780G
// Memory Limit: 500 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e6+5;
char s[N];
int n, dp[N<<1]; ll ans;
vector<int> divisors[N], e[N<<1];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct State {
int len, link, nxt[26];
};
struct SAM {
State st[N<<1];
int sz, lst;
void init() {
st[0].len = 0;
st[0].link = -1;
sz = lst = 0;
}
void extend(char ch) {
int u = ++sz, c = ch - 'a';
st[u].len = st[lst].len + 1;
int p = lst;
for(;p!=-1&&!st[p].nxt[c];p=st[p].link) st[p].nxt[c] = u;
if(p == -1) st[u].link = 0;
else {
int q = st[p].nxt[c];
if(st[p].len + 1 == st[q].len) st[u].link = q;
else {
int v = ++sz;
st[v].len = st[p].len + 1;
st[v].link = st[q].link;
memcpy(st[v].nxt, st[q].nxt, sizeof(st[q].nxt));
for(;p!=-1&&st[p].nxt[c]==q;p=st[p].link) st[p].nxt[c] = v;
st[q].link = st[u].link = v;
}
}
lst = u;
dp[u] = 1;
}
}sam;
int calc(int c, int x) {
return upper_bound(divisors[c].begin(), divisors[c].end(), x) - divisors[c].begin();
}
void dfs(int u) {
for(auto v : e[u]) {
dfs(v);
dp[u] += dp[v];
}
if(!u) return;
int cnt = calc(dp[u], sam.st[u].len) - calc(dp[u], sam.st[sam.st[u].link].len);
ans += 1LL * cnt * dp[u];
}
int main() {
scanf("%d%s", &n, s+1);
rep(i, 1, n) for(int j = i; j <= n; j += i) divisors[j].push_back(i);
sam.init();
rep(i, 1, n) sam.extend(s[i]);
rep(i, 1, sam.sz) e[sam.st[i].link].push_back(i);
dfs(0);
printf("%lld\n", ans);
return 0;
}
标签:__,SAM,int,题解,CF1780G,Delicious,Dessert,operatorname
From: https://www.cnblogs.com/ruierqwq/p/CF-1780G.html