[접미사 트리 & 가상 트리 DP] BZOJ3879.SvT
여러 조가 물어보면 허수로
카드 제한 초과 +1
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1000010;
const ll P=23333333333333333LL;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
char c=nc(); x=0;
for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}
int n,q;
char a[N];
int nxt[N][26],fail[N],len[N],pos[N],p=1,cnt=1;
inline int extend(char c){
c-='a'; int np=++cnt; len[np]=len[p]+1;
while(p && !nxt[p][c]) nxt[p][c]=np,p=fail[p];
if(!p) fail[np]=1;
else{
int q=nxt[p][c];
if(len[q]==len[p]+1) fail[np]=q;
else{
int nq=++cnt; len[nq]=len[p]+1;
memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
fail[nq]=fail[q];
fail[q]=fail[np]=nq;
while(p && nxt[p][c]==q) nxt[p][c]=nq,p=fail[p];
}
}
return p=np;
}
int ct,G[N];
struct edge{
int t,nx;
}E[N];
int lst[N<<1],lg2[N<<1],t,st[N<<1][25],lnd[N];
inline void addedge(int x,int y){
E[++ct].t=y; E[ct].nx=G[x]; G[x]=ct;
}
int dpt[N];
void dfs(int x){
lnd[x]=++t; lst[t]=x;
for(int i=G[x];i;i=E[i].nx){
dpt[E[i].t]=dpt[x]+1; dfs(E[i].t); lst[++t]=x;
}
}
inline void Pre(){
for(int i=1;i<=t;i++) lg2[i]=lg2[i-1]+((1<1]+1)==i);
int tt=lg2[t];
for(int i=1;i<=t;i++) st[i][0]=lst[i];
for(int k=1;k<=tt;k++)
for(int i=1;i+(1<1<=t;i++)
st[i][k]=dpt[st[i][k-1]]1<1)][k-1]]?st[i][k-1]:st[i+(1<1)][k-1];
}
inline int LCA(int x,int y){
x=lnd[x]; y=lnd[y];
if(x>y) swap(x,y);
int t=lg2[y-x+1];
return dpt[st[x][t]]1<1][t]]?st[x][t]:st[y-(1<1][t];
}
inline ll mul(ll a,ll b,ll p){
a%=p; b%=p;
return ((a*b-(ll)((ll)((long double)a/p*b+1e-3)*p))%p+p)%p;
}
inline ll add(ll &a,ll b){
(a+=b)%=P;
}
void PutAns(ll x){
if(x>=10) PutAns(x/10); putchar(x%10+'0');
}
namespace iT{
int n,lst[N<<1],vis[N],S[N],G[N],t,root,cnt,clk;
ll f[N]; int g[N],val[N];
struct edge{
int t,nx;
}E[N<<1];
inline bool cmp(int a,int b){
return lnd[a]inline void addedge(int x,int y){
E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt;
E[++cnt].t=x; E[cnt].nx=G[y]; G[y]=cnt;
}
void dp(int x,int p){
f[x]=0; g[x]=(val[x]==clk);
for(int i=G[x];i;i=E[i].nx)
if(E[i].t!=p){
dp(E[i].t,x);
add(f[x],len[x]*g[x]%P*g[E[i].t]%P);
g[x]+=g[E[i].t];
}
}
inline void solve(){
read(n); cnt=0; ++clk;
for(int i=1;i<=n;i++) read(lst[i]),val[lst[i]=pos[lst[i]]]=clk;
sort(lst+1,lst+1+n,cmp); n=unique(lst+1,lst+1+n)-lst-1;
int t=n;
for(int i=1;i1]);
sort(lst+1,lst+1+t,cmp); t=unique(lst+1,lst+1+t)-lst-1;
n=t; t=0;
for(int i=1;i<=n;i++){
G[lst[i]]=0;
while(t && LCA(S[t],lst[i])!=S[t]) t--;
if(!t) root=lst[i]; else addedge(S[t],lst[i]);
S[++t]=lst[i];
}
dp(root,0); ll ans=0;
for(int i=1;i<=n;i++) add(ans,f[lst[i]]);
PutAns(ans); putchar('
');
}
}
int main(){
read(n); read(q);
for(int i=1;i<=n;i++) while((a[i]=nc())>'z' || a[i]<'a');
for(int i=n;i;i--) pos[i]=extend(a[i]);
for(int i=2;i<=cnt;i++)
addedge(fail[i],i);
dfs(1); Pre();
while(q--) iT::solve();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.