1 条题解

  • 0
    @ 2026-5-10 22:57:22

    题传

    细节好多/px

    考虑 naive 的 O(n2)O(n^{2}) DP，设 f[l,r]f_{[l, r]} 表示当前串为 [l,r][l, r] 的路径权值和，答案即为 ∑f[i,i]\sum f_{[i, i]}。

    我们考虑基本子串结构，注意到本题本质上在统计从点阵左上角到 y=xy=x 的所有路径经过的点的 occ⁡\operatorname{occ} 乘积的和。贡献分布在 y=xy=x 上不好算，考虑将路径全部反向统计到左上角 (1,n)(1, n)。

    若将 ff 刷表出来，一个等价类 aa 在图上出现的若干位置 G(a)G(a) 全部相等，所以考虑将等价类之间的包含关系建出一张 DAG 倒拓扑序处理等价类，得到了一个常数略小的 O(n2)O(n^{2}) 做法。

    发现我们的复杂度瓶颈在于等价类内部的 ff 转移，而对于不同等价类之间的转移需要用的只有等价类的上边界和左边界。

    考虑分治求每个等价类代表的阶梯图的左边界和上边界，每次我们选择长宽中更长的一部分折半，根据下面的部分切出一条平行于另一边的线，将所求的 ff 数组划分为三个部分，两个阶梯状的子图递归解决。

    处理完子问题后，对于中间的矩形 (a,b)−(c,d)(a, b)-(c, d) 部分，我们得到其右边界和下边界的 ff，我们希望快速得到上边界和左边界。设 kk 为等价类 aa 的出现次数。

    下边界转移到上边界：

    $$f_{b, y}\binom{y-x+b-a}{b-a}k^{y-x+b-a}\to f_{a, x}(x\le y)$$

    展开：

    $$f_{b, y}\frac{(y-x+b-a)!}{(b-a)!(y-x)!}k^{y-x+b-a}\to f_{a, x}$$

    不难发现这是个减法卷积的形式。

    下边界转移到左边界：

    $$f_{b, y}\binom {x-a+d-y}{x-a}k^{x-a+d-y}\to f_{x, b}$$$$f_{b, y}\frac {(x-a+d-y)!}{(x-a)!(d-y)!}k^{x-a+d-y}\to f_{x, b}$$

    同样也可以减法卷积，右边界的转移同理。

    于是一层分治 + 4 次卷积即可，卷积的长度不超过等价类行数和列数和（不超过 2n2n），复杂度 O(nlog⁡2n)O(n\log ^2 n)。

    实现细节：阶乘和 kk 的幂的处理要到两倍，递归后得到的数组其实是右边界右边一列 + 下边界下一列，注意 +1 之类的边界问题。

    Code

    #include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <functional>
#define mem(arr, bit) memset(arr, bit, sizeof(arr))
#define mcy(arr, v) memcpy(arr, v, sizeof(arr))
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef vector <int> poly;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){return x+(x<0?cp:0)-(x>=cp?cp:0);}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
	char ch=getchar();int x=0, f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
	int ret=1;
	for(; b; b>>=1, a=1ll*a*a%cp)
		if(b&1) ret=1ll*ret*a%cp;
	return ret;
}
const int N=1e5+6, M=N<<1, g0=3, invg=ksm(g0);
struct SAM{
	int ch[M][26], fail[M][26], fa[M], occ[M], len[M], mxp[M], rnk[M], id[M], pos[N], tot, lst;
	inline int clr(int x){mem(ch[x], 0);mem(fail[x], 0);fa[x]=occ[x]=rnk[x]=id[x]=len[x]=mxp[x]=0;return x;}
	inline void cpy(int x, int p){mcy(ch[x], ch[p]);len[x]=len[p], fa[x]=fa[p];}
	inline void rmk(){clr(tot=lst=1);}
	inline int insert(char cc){
		int p=lst, c=cc-'a', cur=clr(++tot);len[cur]=len[p]+1;
		for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=cur;int q=ch[p][c];
		if(!q) fa[cur]=1;else if(len[q]==len[p]+1) fa[cur]=q;
		else{
			int nex=clr(++tot);cpy(nex, q);len[nex]=len[p]+1;
			for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nex;fa[q]=fa[cur]=nex;
		}return lst=cur;
	}
	inline void ins(char *s, int m){
		rmk();
		for(int i=1; i<=m; ++i) mxp[pos[i]=insert(s[i])]=i, occ[pos[i]]=1;
		vector < vector <int> >  G(tot+1, vector <int> ());
		for(int i=2; i<=tot; ++i) G[fa[i]].pb(i);
		function <void(int)> dfs=[&](int x){
			for(auto v:G[x]) dfs(v), occ[x]+=occ[v], 
				mxp[x]=max(mxp[x], mxp[v]);
			return ;
		};dfs(1);
		for(int i=2; i<=tot; ++i) fail[fa[i]][s[mxp[i]-len[fa[i]]]-'a']=i;
	}
	inline int EDP(int x){return len[x]-len[fa[x]];}
	inline void merge(){
        for(int i=tot; i>1; --i) if(!id[i]) 
            for(int c=0; c<26; ++c) if(ch[i][c])
                {id[i]=id[ch[i][c]];break;}
	}
}S, T;
int n, deg[M], Ec, tfn[M];char s[N];
vi row[M], col[M], E[M];
void DFS(int u, int v){
    int lenu=S.len[u], lenv=T.len[v];
    if(lenu==lenv&&u!=1&&v!=1) S.id[u]=T.id[v]=++Ec;
    for(int c=0, x, y; c<26; ++c)
        if((x=S.ch[u][c])&&(S.len[x]==lenu+1)&&(y=(lenu==lenv)?T.fail[v][c]:v))
            DFS(x, y);
}
map <Pii, bool> inG;
void add(int x, int y){
	if(!y) return ;if(inG[{x, y}]) return ;
	inG[{x, y}]=1;E[y].pb(x);++deg[x];
}
inline void build(){
	S.ins(s, n);reverse(s+1, s+n+1);T.ins(s, n);
	DFS(1, 1);S.merge();T.merge();
	for(int i=S.tot; i>=2; --i) row[S.id[i]].pb(i);
	for(int i=T.tot; i>=2; --i) col[T.id[i]].pb(i);
	for(int i=1; i<=Ec; ++i){
		int rc=0;for(auto r:row[i]) add(i, S.id[S.fa[r]]), S.rnk[r]=rc++;
		int cc=0;for(auto c:col[i]) add(i, T.id[T.fa[c]]), T.rnk[c]=cc++;
	}
}
vi ran[M], can[M];//左 上 
int fac[M], inv[M], pw[M<<1];
inline int Com(int a, int b){if(a<b||b<0) return 0;return 1LL*fac[a]*inv[b]%cp*inv[a-b]%cp;}
typedef pair <poly, poly> Ply;int k, len, to[M*3];
inline void init(int L){len=1;while(len<=L) len<<=1;
for(int i=0; i<len; ++i) to[i]=(to[i>>1]>>1)|((i&1)?len>>1:0);}
inline void NTT(poly &f, bool flg){
	f.resize(len);
	for(int i=0; i<len; i++)
		if(i<to[i]) swap(f[i], f[to[i]]);
	for(int s=2; s<=len; s<<=1){
		int size=s>>1;
		int omega=ksm(flg?g0:invg, (cp-1)/s);
		for(int L=0; L<len; L+=s){
			int buf=1;
			for(int i=L; i<L+size; ++i, buf=1ll*omega*buf%cp){
				int F2=1ll*buf*f[i+size]%cp;
				f[i+size]=mod(f[i]-F2);f[i]=mod(f[i]+F2);
			}
		}
	}
	if(!flg) for(int i=0, iv=ksm(len); i<len; ++i) f[i]=1LL*f[i]*iv%cp;
}
inline poly mTT(poly &a, poly &b, int l, int r){
	int n=a.size(), m=b.size();reverse(b.begin(), b.end());init(n+m);
	// printf("times [%d %d]\n", l, r);
	// for(auto v:a) printf("%d ", v);puts("");
	// for(auto v:b) printf("%d ", v);puts("");
	NTT(a, 1);NTT(b, 1);poly res;res.resize(len);
	for(int i=0; i<len; ++i) res[i]=1LL*a[i]*b[i]%cp;NTT(res, 0);
	// for(auto v:res) printf("%d ", v);puts("");
	// printf("<<<<%d %d %d\n", len, m, r-l);return res;
	poly p;for(int i=l; i<=r; ++i) p.pb(res[i-l+m-1]);return p;
}
inline Ply slv(int id, int r, int c, int dep=0){
	//计算等价类 id 以 (r, c) 为左上角的梯形贡献
	int R=T.EDP(col[id][c])-1, C=S.EDP(row[id][r])-1;
	// if(id==6)printf("%d:solve %d %d %d\n", dep, id, r, c);
	if(r<R&&c<C){
		int nc, nr;
		if((C-c)>(R-r)) nc=(c+C)/2+1, nr=T.EDP(col[id][nc]);
		else nr=(r+R)/2+1, nc=S.EDP(row[id][nr]);
		Ply res;res.st.resize(R-r+1);res.nd.resize(C-c+1);
		{
			Ply rig;if(nc<=C) rig=slv(id, r, nc, dep+1);//, puts("end");//右边需要继续递归
			for(int i=r+rig.st.size(), u; i<nr; ++i) u=S.fa[row[id][i]], rig.st.pb(ran[S.id[u]][S.rnk[u]]);
			for(int i=nc; i<=C; ++i) res.nd[i-c]=rig.nd[i-nc];--nc, --nr;
			// printf("right:");for(auto v:rig.st) printf("%d ", v);puts("");
			int rss=rig.st.size();//rig.st.resize(nr-r+1);
			for(int i=rss, u; i<=nr-r; ++i) 
				u=S.fa[row[id][i]], rig.st.pb(ran[S.id[u]][S.rnk[u]]);
			poly cl=rig.st;
			{//列转移列
				poly h;for(int t=0, z=nc-c; t<=nr-r; ++t) h.pb(1LL*Com(t+z, t)*pw[t+z+1]%cp);
				poly tmp=mTT(rig.st, h, 0, nr-r);for(int i=0; i<=nr-r; ++i) plust(res.st[i], tmp[i]);
			}
			{//列转移行
				poly h;cl.resize(nr+nc-r-c+1);
				for(int i=nr+nc-c-r; i>=0; --i) cl[i]=(i<nc-c)?0:(1LL*cl[i-nc+c]*inv[i-nc+c]%cp);
				for(int i=c-nc; i<=nr-r; ++i) h.pb(1LL*fac[i+nc-c]*pw[i+nc-c+1]%cp);
				poly tmp=mTT(cl, h, 0, nc-c);
				for(int i=0; i<=nc-c; ++i) plust(res.nd[i], 1LL*tmp[i]*inv[nc-i-c]%cp);
			}++nc, ++nr;
		}
		// printf("(%d %d)-(%d %d)slv %d(%d) (%d)%d\n", r, c, R, C, nr, c, r, nc);
		// printf("?:");for(auto v:res.st) printf("%d ", v);puts("");
		// printf("!:");for(auto v:res.nd) printf("%d ", v);puts("");
		{
			Ply dwn;if(nr<=R) dwn=slv(id, nr, c, dep+1);//, puts("end");
			for(int i=c+dwn.nd.size(), u; i<nc; ++i) u=T.fa[col[id][i]], dwn.nd.pb(can[T.id[u]][T.rnk[u]]);
			// printf("down:");for(auto v:dwn.nd) printf("%d ", v);puts("");
			for(int i=nr; i<=R; ++i) res.st[i-r]=dwn.st[i-nr];--nr, --nc;
			int dns=dwn.nd.size();//dwn.nd.resize(nc-c+1);
			for(int i=dns, u; i<=nc-c; ++i) 
				u=T.fa[col[id][i]], dwn.nd.pb(can[T.id[u]][T.rnk[u]]);
			poly rw=dwn.nd;
			{//行转移行
				poly h;for(int t=0, z=nr-r; t<=nc-c; ++t) h.pb(1LL*Com(t+z, t)*pw[t+z+1]%cp);
				poly tmp=mTT(dwn.nd, h, 0, nc-c);for(int i=0; i<=nc-c; ++i) plust(res.nd[i], tmp[i]);
			}
			{//行转移列
				poly h;rw.resize(nc+nr-c-r+1);
				for(int i=nc+nr-c-r; i>=0; --i) rw[i]=(i<nr-r)?0:(1LL*rw[i-nr+r]*inv[i-nr+r]%cp);
				for(int i=r-nr; i<=nc-c; ++i) h.pb(1LL*fac[i+nr-r]*pw[i+nr-r+1]%cp);
				poly tmp=mTT(rw, h, 0, nr-r);
				for(int i=0; i<=nr-r; ++i) plust(res.st[i], 1LL*tmp[i]*inv[nr-i-r]%cp);
			}++nr, ++nc;
		}
		// // printf("(%d %d)-(%d %d)slv %d(%d) (%d)%d\n", r, c, R, C, nr, c, r, nc);
		// if(id==6){printf("?:");for(auto v:res.st) printf("%d ", v);puts("");}
		// if(id==6){printf("!:");for(auto v:res.nd) printf("%d ", v);puts("");}
		return res;
	}
	else if(r==R){//顶到下边界
		poly rs, cs;cs.resize(C-c+1);ran[0][0]=0;can[0][0]=1;
		for(int i=C; i>=c; --i){
			int u=T.fa[col[id][i]], val=can[T.id[u]][T.rnk[u]];
			if(i==C) u=S.fa[row[id][R]], plust(val, ran[S.id[u]][S.rnk[u]]); 
			else plust(val, cs[i+1-c]);cs[i-c]=1LL*val*k%cp;
		}rs.pb(cs[0]);//if(id==6){for(auto v:cs) printf("%d ", v);puts("");}
		return {rs, cs};
	}
	else if(c==C){//顶到右边界
		poly rs, cs;rs.resize(R-r+1);can[0][0]=0;ran[0][0]=1;
		for(int i=R; i>=r; --i){
			int u=S.fa[row[id][i]], val=ran[S.id[u]][S.rnk[u]];
			if(i==R) u=T.fa[col[id][C]], plust(val, can[T.id[u]][T.rnk[u]]);
			else plust(val, rs[i+1-r]);rs[i-r]=1LL*val*k%cp;
		}cs.pb(rs[0]);//if(id==6){for(auto v:rs) printf("%d ", v);puts("");}
		return {rs, cs};
	}
}
signed main(){
	scanf("%s", s+1);n=strlen(s+1);build();
	for(int i=fac[0]=1; i<=n+n; ++i) fac[i]=1LL*fac[i-1]*i%cp;
	inv[n+n]=ksm(fac[n+n]);for(int i=n+n; i>=1; --i) inv[i-1]=1LL*inv[i]*i%cp;
	function <void()> topo=[&](){
		queue <int> Q;int top=0;
		for(int i=1; i<=Ec; ++i) if(!deg[i]) Q.push(i);
		while(!Q.empty()){
			int x=Q.front();Q.pop();tfn[++top]=x;
			for(auto v:E[x]) if(!(--deg[v])) Q.push(v);
		}
		return ;
	};topo();
	ran[0].pb(1);can[0].pb(1);//printf("%d\n", Ec);
	for(int i=1; i<=Ec; ++i)
		ran[i].resize(row[i].size()),
		can[i].resize(can[i].size());
	for(int i=1, x; i<=Ec; ++i){
		x=tfn[i], k=S.occ[row[x][0]];//printf("%d(%d):%d\n", x, row[x][0], k);
		int nn=row[x].size(), mm=col[x].size();pw[0]=1;
		for(int j=1; j<=2*(nn+mm+2); ++j) pw[j]=1LL*pw[j-1]*k%cp;
		Ply res=slv(x, 0, 0);ran[x]=res.st, can[x]=res.nd;
		ran[x].resize(nn);can[x].resize(mm);
	}
	// for(int i=1; i<=Ec; ++i){
		// printf("%d %d\n", i, S.occ[row[i][0]]);
		// for(auto v:ran[i]) printf("%d ", v);puts("");
		// for(auto v:can[i]) printf("%d ", v);puts("");
		// puts("");
	// }
	printf("%d\n", ran[S.id[S.pos[n]]][0]);
	// printf("you will ak ioi");
	return 0;
}

    我的写法常数相当大，通过预处理单位根的幂可以在 2s 内极限在 lg 过。Code2。

    #include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <functional>
#define mem(arr, bit) memset(arr, bit, sizeof(arr))
#define mcy(arr, v) memcpy(arr, v, sizeof(arr))
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef vector <int> poly;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){return x+(x<0?cp:0)-(x>=cp?cp:0);}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
	char ch=getchar();int x=0, f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
	int ret=1;
	for(; b; b>>=1, a=1ll*a*a%cp)
		if(b&1) ret=1ll*ret*a%cp;
	return ret;
}
const int N=1e5+6, M=N<<1, g0=3, invg=ksm(g0);
struct SAM{
	int ch[M][26], fail[M][26], fa[M], occ[M], len[M], mxp[M], rnk[M], id[M], pos[N], tot, lst;
	inline int clr(int x){mem(ch[x], 0);mem(fail[x], 0);fa[x]=occ[x]=rnk[x]=id[x]=len[x]=mxp[x]=0;return x;}
	inline void cpy(int x, int p){mcy(ch[x], ch[p]);len[x]=len[p], fa[x]=fa[p];}
	inline void rmk(){clr(tot=lst=1);}
	inline int insert(char cc){
		int p=lst, c=cc-'a', cur=clr(++tot);len[cur]=len[p]+1;
		for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=cur;int q=ch[p][c];
		if(!q) fa[cur]=1;else if(len[q]==len[p]+1) fa[cur]=q;
		else{
			int nex=clr(++tot);cpy(nex, q);len[nex]=len[p]+1;
			for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nex;fa[q]=fa[cur]=nex;
		}return lst=cur;
	}
	inline void ins(char *s, int m){
		rmk();
		for(int i=1; i<=m; ++i) mxp[pos[i]=insert(s[i])]=i, occ[pos[i]]=1;
		vector < vector <int> >  G(tot+1, vector <int> ());
		for(int i=2; i<=tot; ++i) G[fa[i]].pb(i);
		function <void(int)> dfs=[&](int x){
			for(auto v:G[x]) dfs(v), occ[x]+=occ[v], 
				mxp[x]=max(mxp[x], mxp[v]);
			return ;
		};dfs(1);
		for(int i=2; i<=tot; ++i) fail[fa[i]][s[mxp[i]-len[fa[i]]]-'a']=i;
	}
	inline int EDP(int x){return len[x]-len[fa[x]];}
	inline void merge(){
        for(int i=tot; i>1; --i) if(!id[i]) 
            for(int c=0; c<26; ++c) if(ch[i][c])
                {id[i]=id[ch[i][c]];break;}
	}
}S, T;
int n, deg[M], Ec, tfn[M];char s[N];
vi row[M], col[M], E[M];
void DFS(int u, int v){
    int lenu=S.len[u], lenv=T.len[v];
    if(lenu==lenv&&u!=1&&v!=1) S.id[u]=T.id[v]=++Ec;
    for(int c=0, x, y; c<26; ++c)
        if((x=S.ch[u][c])&&(S.len[x]==lenu+1)&&(y=(lenu==lenv)?T.fail[v][c]:v))
            DFS(x, y);
}
map <Pii, bool> inG;
void add(int x, int y){
	if(!y) return ;if(inG[{x, y}]) return ;
	inG[{x, y}]=1;E[y].pb(x);++deg[x];
}
inline void build(){
	S.ins(s, n);reverse(s+1, s+n+1);T.ins(s, n);
	DFS(1, 1);S.merge();T.merge();
	for(int i=S.tot; i>=2; --i) row[S.id[i]].pb(i);
	for(int i=T.tot; i>=2; --i) col[T.id[i]].pb(i);
	for(int i=1; i<=Ec; ++i){
		int rc=0;for(auto r:row[i]) add(i, S.id[S.fa[r]]), S.rnk[r]=rc++;
		int cc=0;for(auto c:col[i]) add(i, T.id[T.fa[c]]), T.rnk[c]=cc++;
	}
}
vi ran[M], can[M];//左 上 
int fac[M], inv[M], pw[M<<1], W[2][25][M<<2];
inline int Com(int a, int b){if(a<b||b<0) return 0;return 1LL*fac[a]*inv[b]%cp*inv[a-b]%cp;}
typedef pair <poly, poly> Ply;int k, len, to[M*3];
inline void init(int L){len=1;while(len<=L) len<<=1;for(int i=0; i<len; ++i) to[i]=(to[i>>1]>>1)|((i&1)?len>>1:0);}
inline void INIT(int m){
	for(int i=fac[0]=1; i<=m; ++i) fac[i]=1LL*fac[i-1]*i%cp;
	inv[m]=ksm(fac[m]);for(int i=m; i>=1; --i) inv[i-1]=1LL*inv[i]*i%cp;
	for(int s=2, p=0; s<=m+m; s<<=1, ++p){
		for(int op=0; op<2; ++op){
			int w=ksm(op?g0:invg, (cp-1)/s);
			W[op][p][0]=1;for(int i=1; i<=s/2; ++i) W[op][p][i]=1LL*W[op][p][i-1]*w%cp;
		}
	}
}
inline void NTT(poly &f, bool flg){
	f.resize(len);
	for(int i=0; i<len; ++i)
		if(i<to[i]) swap(f[i], f[to[i]]);
	for(int s=2, p=0; s<=len; s<<=1, ++p){
		int size=s>>1, *w=W[!flg][p];
		for(int L=0; L<len; L+=s){
			for(int i=L; i<L+size; ++i){
				int F2=1ll*w[i-L]*f[i+size]%cp;
				f[i+size]=mod(f[i]-F2);f[i]=mod(f[i]+F2);
			}
		}
	}
	if(!flg) for(int i=0, iv=ksm(len); i<len; ++i) f[i]=1LL*f[i]*iv%cp;
}
inline poly mTT(poly &a, poly &b, int l, int r){
	int n=a.size(), m=b.size();reverse(b.begin(), b.end());init(n+m);
	NTT(a, 1);NTT(b, 1);poly res;res.resize(len);
	for(int i=0; i<len; ++i) res[i]=1LL*a[i]*b[i]%cp;NTT(res, 0);
	poly p;for(int i=l; i<=r; ++i) p.pb(res[i+m-1]);return p;
}
inline Ply slv(int id, int r, int c, int dep=0){
	//计算等价类 id 以 (r, c) 为左上角的梯形贡献
	int R=T.EDP(col[id][c])-1, C=S.EDP(row[id][r])-1;
	if(r<R&&c<C){
		int nc, nr;
		if((C-c)>(R-r)) nc=(c+C)/2+1, nr=T.EDP(col[id][nc]);
		else nr=(r+R)/2+1, nc=S.EDP(row[id][nr]);
		Ply res;res.st.resize(R-r+1);res.nd.resize(C-c+1);
		{
			Ply rig;if(nc<=C) rig=slv(id, r, nc, dep+1);
			for(int i=r+rig.st.size(), u; i<nr; ++i) u=S.fa[row[id][i]], rig.st.pb(ran[S.id[u]][S.rnk[u]]);
			for(int i=nc; i<=C; ++i) res.nd[i-c]=rig.nd[i-nc];--nc, --nr;
			int rss=rig.st.size();
			for(int i=rss, u; i<=nr-r; ++i) 
				u=S.fa[row[id][i]], rig.st.pb(ran[S.id[u]][S.rnk[u]]);
			poly cl=rig.st;
			{//列转移列
				poly h;for(int t=0, z=nc-c; t<=nr-r; ++t) h.pb(1LL*Com(t+z, t)*pw[t+z+1]%cp);
				poly tmp=mTT(rig.st, h, 0, nr-r);for(int i=0; i<=nr-r; ++i) plust(res.st[i], tmp[i]);
			}
			{//列转移行
				poly h;cl.resize(nr+nc-r-c+1);
				for(int i=nr+nc-c-r; i>=0; --i) cl[i]=(i<nc-c)?0:(1LL*cl[i-nc+c]*inv[i-nc+c]%cp);
				for(int i=c-nc; i<=nr-r; ++i) h.pb(1LL*fac[i+nc-c]*pw[i+nc-c+1]%cp);
				poly tmp=mTT(cl, h, 0, nc-c);
				for(int i=0; i<=nc-c; ++i) plust(res.nd[i], 1LL*tmp[i]*inv[nc-i-c]%cp);
			}++nc, ++nr;
		}
		{
			Ply dwn;if(nr<=R) dwn=slv(id, nr, c, dep+1);
			for(int i=c+dwn.nd.size(), u; i<nc; ++i) u=T.fa[col[id][i]], dwn.nd.pb(can[T.id[u]][T.rnk[u]]);
			for(int i=nr; i<=R; ++i) res.st[i-r]=dwn.st[i-nr];--nr, --nc;
			int dns=dwn.nd.size();
			for(int i=dns, u; i<=nc-c; ++i) 
				u=T.fa[col[id][i]], dwn.nd.pb(can[T.id[u]][T.rnk[u]]);
			poly rw=dwn.nd;
			{//行转移行
				poly h;for(int t=0, z=nr-r; t<=nc-c; ++t) h.pb(1LL*Com(t+z, t)*pw[t+z+1]%cp);
				poly tmp=mTT(dwn.nd, h, 0, nc-c);for(int i=0; i<=nc-c; ++i) plust(res.nd[i], tmp[i]);
			}
			{//行转移列
				poly h;rw.resize(nc+nr-c-r+1);
				for(int i=nc+nr-c-r; i>=0; --i) rw[i]=(i<nr-r)?0:(1LL*rw[i-nr+r]*inv[i-nr+r]%cp);
				for(int i=r-nr; i<=nc-c; ++i) h.pb(1LL*fac[i+nr-r]*pw[i+nr-r+1]%cp);
				poly tmp=mTT(rw, h, 0, nr-r);
				for(int i=0; i<=nr-r; ++i) plust(res.st[i], 1LL*tmp[i]*inv[nr-i-r]%cp);
			}++nr, ++nc;
		}
		return res;
	}
	else if(r==R){//顶到下边界
		poly rs, cs;cs.resize(C-c+1);ran[0][0]=0;can[0][0]=1;
		for(int i=C; i>=c; --i){
			int u=T.fa[col[id][i]], val=can[T.id[u]][T.rnk[u]];
			if(i==C) u=S.fa[row[id][R]], plust(val, ran[S.id[u]][S.rnk[u]]); 
			else plust(val, cs[i+1-c]);cs[i-c]=1LL*val*k%cp;
		}rs.pb(cs[0]);
		return {rs, cs};
	}
	else if(c==C){//顶到右边界
		poly rs, cs;rs.resize(R-r+1);can[0][0]=0;ran[0][0]=1;
		for(int i=R; i>=r; --i){
			int u=S.fa[row[id][i]], val=ran[S.id[u]][S.rnk[u]];
			if(i==R) u=T.fa[col[id][C]], plust(val, can[T.id[u]][T.rnk[u]]);
			else plust(val, rs[i+1-r]);rs[i-r]=1LL*val*k%cp;
		}cs.pb(rs[0]);
		return {rs, cs};
	}
}
signed main(){
	scanf("%s", s+1);n=strlen(s+1);build();INIT(n+n);
	function <void()> topo=[&](){
		queue <int> Q;int top=0;
		for(int i=1; i<=Ec; ++i) if(!deg[i]) Q.push(i);
		while(!Q.empty()){
			int x=Q.front();Q.pop();tfn[++top]=x;
			for(auto v:E[x]) if(!(--deg[v])) Q.push(v);
		}
		return ;
	};topo();
	ran[0].pb(1);can[0].pb(1);
	for(int i=1; i<=Ec; ++i)
		ran[i].resize(row[i].size()),
		can[i].resize(can[i].size());
	for(int i=1, x; i<=Ec; ++i){
		x=tfn[i], k=S.occ[row[x][0]];
		int nn=row[x].size(), mm=col[x].size();pw[0]=1;
		for(int j=1; j<=2*(nn+mm+2); ++j) pw[j]=1LL*pw[j-1]*k%cp;
		Ply res=slv(x, 0, 0);ran[x]=res.st, can[x]=res.nd;
		ran[x].resize(nn);can[x].resize(mm);
	}
	printf("%d\n", ran[S.id[S.pos[n]]][0]);
	return 0;
}
    • 1

    [SDOI/SXOI2022] 子串统计

    信息

    ID
    7253
    时间
    3000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 17ms
    4. Powered by Hydro v5.0.1 Community