C - Cheating and Stealing
Description
给出一场乒乓球赛每回合的输赢情况，总回合数为(n(nleq10^6))，用(W)和(L)表示赢球和输球。在(k)分制中，若双方中有一方得分大于(k)且分差大于1分，则一小局结束，结算胜负。求在(kin[1,n])时，能够赢得的小局数目。
Solution
(k)分制下最多有(n/k)小局，那么总局数约为(nlogn)，考虑用(O(1))的复杂度求得每局的结果。
记录(sum)，(pos)，(br)，前(i)回合中赢/输球的数目为(sum[0/1,i])，第(i)次赢/输球是在第(pos[0/1,i])回合，第(i)回合前是平分的情况下直到第(br[i])回合分差能大于1，这些数组都能(O(n))求得。
那么对于从第(t)回合开始的一小局，我方得(k)分是在(j_0=pos[0,sum[0,i-1]+k])回合，对方得(k)分是在(j_1=pos[1,sum[1,i-1]+k])回合。检查先得(k)分的一方到达(k)分时，即第(j=min(j_0,j_1))回合时对方的分数是否为(k-1)，若小于(k-1)则该方赢下一局，否则持续比赛直到(br[j])。该过程是(O(1))的。
Code
//Cheating and Stealing
#include <cstdio>
const int N=1e6+10;
const int P=998244353;
int n; char s[N];
int sum[2][N],pos[2][N*2]; int br[N];
int pow_n[N];
int main()
{
scanf("%d",&n); scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
sum[0][i]=sum[0][i-1]+(s[i]=='W');
sum[1][i]=sum[1][i-1]+(s[i]=='L');
if(s[i]=='W') pos[0][sum[0][i]]=i;
if(s[i]=='L') pos[1][sum[1][i]]=i;
}
br[n+1]=br[n]=n+1; for(int i=n-1;i>=1;i--) br[i]=(s[i]==s[i+1])?i+1:br[i+2];
long long ans=0;
pow_n[0]=1; for(int i=1;i<=n;i++) pow_n[i]=1LL*pow_n[i-1]*(n+1)%P;
for(int k=1;k<=n;k++)
{
int r=0;
for(int i=1;i<=n;i++)
{
int j0=pos[0][sum[0][i-1]+k];
int j1=pos[1][sum[1][i-1]+k];
if(!j0) break;
if(!j1)
{
if(sum[1][j0]-sum[1][i-1]<k-1) i=j0,r++;
else i=br[j0],r+=(s[i]=='W');
}
else if(j0<j1)
{
if(sum[1][j0]-sum[1][i-1]<k-1) i=j0,r++;
else i=br[j0],r+=(s[i]=='W');
}
else if(j0>j1)
{
if(sum[0][j1]-sum[0][i-1]<k-1) i=j1;
else i=br[j1],r+=(s[i]=='W');
}
}
ans=(ans+1LL*r*pow_n[k-1])%P;
}
printf("%lld
",ans);
return 0;
}