L
给一个长度为\(n\)的字符串\(s\)，它只包含I,C,P三种字符。有\(q\)个询问，每次问\(s[l:r]\)子串中有多少个子序列是ICPC。
\(n,q\leq 2\times 10^6\)
题解
硬算。固定I,P的位置后只需查询C的个数。
\[\sum_{s_i=\mathtt{I}}\sum_{s_j=\mathtt{P}}(\text{cnt}_C[j]-\text{cnt}_C[i])(\text{cnt}_C[r]-\text{cnt}_C[j]) \]拆开为四项，单独计算。反复运用前缀和消去求和符号。
1
\[\sum_{s_i=\mathtt{I}}\sum_{s_j=\mathtt{P}}\text{cnt}_C[j]\text{cnt}_C[r]\\ =\text{cnt}_C[r]\sum_{s_i=\mathtt{I}}(\text{sum}_{\text{cnt}_CP}[r]-\text{sum}_{\text{cnt}_CP}[i])\\ =\text{cnt}_C[r](\text{cnt}_I[r]-\text{cnt}_I[l-1])\text{sum}_{\text{cnt}_CP[r]}\\ -\text{cnt}_C[r](\text{sum}_{\text{sum}_{\text{cnt}_CP}I}[r]-\text{sum}_{\text{sum}_{\text{cnt}_CP}I}[l-1]) \]2
\[-\sum_{s_i=\mathtt{I}}\sum_{s_j=\mathtt{P}}\text{cnt}_C[j]^2\\ =-\sum_{s_i=\mathtt{I}}(\text{sum}_{(\text{cnt}_CP)^2}[r]-\text{sum}_{(\text{cnt}_CP)^2}[l-1])\\ =-(\text{cnt}_I[r]-\text{cnt}_I[l-1])\text{sum}_{(\text{cnt}_CP)^2}[r]\\ +\text{sum}_{\text{sum}_{(\text{cnt}_CP)^2}I}[r]-\text{sum}_{\text{sum}_{(\text{cnt}_CP)^2}I}[l-1] \]3
\[-\sum_{s_i=\mathtt{I}}\sum_{s_j=\mathtt{P}}\text{cnt}_C[i]\text{cnt}_C[r]\\ =-\text{cnt}_C[r]\sum_{s_i=\mathtt{I}}\text{cnt}_C[i](\text{cnt}_P[r]-\text{cnt}_P[i])\\ =-\text{cnt}_C[r]\text{cnt}_P[r](\text{sum}_{\text{cnt}_CI}[r]-\text{sum}_{\text{cnt}_CI}[l-1])\\ +\text{cnt}_C[r](\text{sum}_{\text{cnt}_CI\times\text{cnt}_PI}[r]-\text{sum}_{\text{cnt}_CI\times\text{cnt}_PI}[l-1]) \]4
\[\sum_{s_i=\mathtt{I}}\sum_{s_j=\mathtt{P}}\text{cnt}_C[i]\text{cnt}_C[j]\\ =\sum_{s_i=\mathtt{I}}\text{cnt}_C[i](\text{sum}_{\text{cnt}_CP}[r]-\text{sum}_{\text{cnt}_CP}[l-1])\\ =\text{sum}_{\text{cnt}_CP}[r](\text{sum}_{\text{cnt}_CI}[r]-\text{sum}_{\text{cnt}_CI}[l-1])\\ -(\text{sum}_{\text{cnt}_CI\times\text{sum}_{\text{cnt}_CP}I}[r]-\text{sum}_{\text{cnt}_CI\times\text{sum}_{\text{cnt}_CP}I}[l-1]) \]列出公式后实现不困难。时间复杂度\(O(n+q)\)。
constexpr int N=2e6+10;
char s[N];
int u[N], v[N];
int cnt_C[N], cnt_I[N], cnt_P[N];
int sum_cnt_C_P[N], sum_cnt_C_I[N], sum_cnt_C_P_2[N];
int sum_sum_cnt_C_P_I[N], sum_sum_cnt_C_P_2_I[N];
int sum_cnt_C_I_mul_cnt_P_I[N];
int sum_sum_cnt_C_P_I_mul_cnt_C_I[N];
int main(){
int n=read<int>(), q=read<int>();
scanf("%s", s+1);
for(int i=1; i<=n; ++i){
cnt_C[i]=cnt_C[i-1]+(s[i]=='C');
cnt_I[i]=cnt_I[i-1]+(s[i]=='I');
cnt_P[i]=cnt_P[i-1]+(s[i]=='P');
sum_cnt_C_P[i]=sum_cnt_C_P[i-1];
if(s[i]=='P') cadd(sum_cnt_C_P[i], cnt_C[i]);
sum_cnt_C_I[i]=sum_cnt_C_I[i-1];
if(s[i]=='I') cadd(sum_cnt_C_I[i], cnt_C[i]);
sum_cnt_C_P_2[i]=sum_cnt_C_P_2[i-1];
if(s[i]=='P') cadd(sum_cnt_C_P_2[i], mul(cnt_C[i], cnt_C[i]));
sum_sum_cnt_C_P_I[i]=sum_sum_cnt_C_P_I[i-1];
if(s[i]=='I') cadd(sum_sum_cnt_C_P_I[i], sum_cnt_C_P[i]);
sum_sum_cnt_C_P_2_I[i]=sum_sum_cnt_C_P_2_I[i-1];
if(s[i]=='I') cadd(sum_sum_cnt_C_P_2_I[i], sum_cnt_C_P_2[i]);
sum_cnt_C_I_mul_cnt_P_I[i]=sum_cnt_C_I_mul_cnt_P_I[i-1];
if(s[i]=='I') cadd(sum_cnt_C_I_mul_cnt_P_I[i], mul(cnt_C[i], cnt_P[i]));
sum_sum_cnt_C_P_I_mul_cnt_C_I[i]=sum_sum_cnt_C_P_I_mul_cnt_C_I[i-1];
if(s[i]=='I') cadd(sum_sum_cnt_C_P_I_mul_cnt_C_I[i], mul(sum_cnt_C_P[i], cnt_C[i]));
}
int64 x=read<int64>(), a=read<int64>(), b=read<int64>(), p=read<int64>();
for(int i=1; i<=q; ++i){
x=(a*x+b)%p;
u[i]=x%n+1;
}
for(int i=1; i<=q; ++i){
x=(a*x+b)%p;
v[i]=x%n+1;
}
int ans=0;
for(int i=1; i<=q; ++i){
int l=u[i], r=v[i];
if(l>r) swap(l, r);
// cerr<<"l="<<l<<" r="<<r<<endl;
// cnt_C_P*cnt_C_r
cadd(ans, mul(cnt_C[r], mul(add(cnt_I[r], MOD-cnt_I[l-1]), sum_cnt_C_P[r])));
cadd(ans, mul(cnt_C[r], add(MOD-sum_sum_cnt_C_P_I[r], sum_sum_cnt_C_P_I[l-1])));
// -cnt_C_P^2
cadd(ans, MOD-mul(add(cnt_I[r], MOD-cnt_I[l-1]), sum_cnt_C_P_2[r]));
cadd(ans, add(sum_sum_cnt_C_P_2_I[r], MOD-sum_sum_cnt_C_P_2_I[l-1]));
// -cnt_C_I*cnt_C_r
cadd(ans, MOD-mul(cnt_C[r], mul(cnt_P[r], add(sum_cnt_C_I[r], MOD-sum_cnt_C_I[l-1]))));
cadd(ans, mul(cnt_C[r], add(sum_cnt_C_I_mul_cnt_P_I[r], MOD-sum_cnt_C_I_mul_cnt_P_I[l-1])));
// cnt_C_I*cnt_C_P
cadd(ans, mul(sum_cnt_C_P[r], add(sum_cnt_C_I[r], MOD-sum_cnt_C_I[l-1])));
cadd(ans, MOD-add(sum_sum_cnt_C_P_I_mul_cnt_C_I[r], MOD-sum_sum_cnt_C_P_I_mul_cnt_C_I[l-1]));
/*for(int i=l; i<=r; ++i)if(s[i]=='I')
for(int j=i+1; j<=r; ++j)if(s[j]=='P')
cadd(ans, mul(add(cnt_C[j], MOD-cnt_C[i]), add(cnt_C[r], MOD-cnt_C[j])));*/
}
printf("%d\n", ans);
return 0;
}
考场上输入看错了，不然能很早过题。
std
这种方法就不用手推那么多公式了。
标签：ICPC2022,cnt,int,text,sum,网络,CP,mathtt From： https://www.cnblogs.com/autoint/p/16730206.html