https://acm.hdu.edu.cn/showproblem.php?pid=7055
给出一个只含有小写字母组成的串s
sqc(s,l,r,c)表示字符c在s的[i,j]内的出现次数
设f[i]表示以i结尾的子区间字符串的答案
考虑从f[i]推到f[i+1]
由i到i+1，假设s[i+1]=c，那么除了字母c之外的其他字母x，sqc(s,L,i,x)=sqc(s,L,i+1,x)
对于字母c
sqc(s,L,i+1,c)^2 = (sqc(s,L,i,c)+1)^2 = sqc(s,L,i,c)^2 + 1 + 2*sqc(s,L,i,c) ， L∈[1,i]
sqc(s,L,i+1,c)^2 = 1 ， L=i+1
所以f[i+1]=f[i]+ ∑（1+2*sqc(s,L,i,c) ） + 1 ，L∈[1,i]
即 f[i+1]=f[i]+2*∑sqc(s,L,i,c) + i+1 L∈[1,i]
维护一下 ∑sqc(s,L,i,c) 即可
当从i变为i+1时， ∑sqc(s,L,i,c) 会加i，因为L∈[1,i]的每个[L,i+1]都会加上一个i+1位置的c
#include<bits/stdc++.h> using namespace std; #define N 100003 char s[N]; int f[N],sum[27]; const int mod=998244353; int main() { int T,n,ans; scanf("%d",&T); while(T--) { scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=26;++i) sum[i]=0; ans=0; for(int i=1;i<=n;++i) { f[i]=(f[i-1]+2*sum[s[i]-‘a‘+1]%mod+i)%mod; ans=(ans+f[i])%mod; sum[s[i]-‘a‘+1]=(sum[s[i]-‘a‘+1]+i)%mod; } printf("%d\n",ans); } }
hdu7055 /2021“MINIEYE杯”中国大学生算法设计超级联赛（7） 1012 Yiwen with Sqc
原文：https://www.cnblogs.com/TheRoadToTheGold/p/15222328.html