考虑最后形态,一定是有某一个区间 \([l,r]\) 保持初始的样子, \(l\) 前面都是 <
,\(r\) 后面都是 >
。
这个区间一定是某两个相邻圆点的位置。设 \(f_i\) 为前 \(i\) 个数全部被覆盖成 <
的概率。设 \(x\) 为 \(l\) 前面圆点的数量,\(y\) 为 \(r\) 后面圆点的数量,那么区间 \([l,r]\) 的概率就是 \(f_{x}\times f_{y}\)(\(y\) 那里是对称的)。同时区间的 <
数量我们也是好求的。
考虑如何求出 \(f_i\),从 \(f_{i-1}\) 转移。此时 \(i\) 这个圆点有 \(2n\) 种选择(方向两种,时间 \(n\) 种)。唯一不合法的是在第一次就往右走。所以 \(f_{i}=f_{i-1}\times \frac{2n-1}{2n}\)
// LUOGU_RID: 139275577
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,P=998244353;
char s[N];
int inv[N],n,f[N],c,g[N],ans,nx[N];
int main()
{
inv[1]=1;
for(int i=2;i<N;i++)
inv[i]=1LL*(P-P/i)*inv[P%i]%P;
scanf("%d%s",&n,s+1);
for(int i=f[0]=1;i<=n;i++)
c+=s[i]=='.',g[i]=g[i-1]+(s[i]=='<'),f[i]=1LL*f[i-1]*(P+1-inv[2*i])%P;
s[0]='.',s[n+1]='.';
for(int i=n;~i;i--)
{
nx[i]=nx[i+1];
if(s[i+1]=='.')
nx[i]=i+1;
}
for(int i=0,p=0;i<=n;i++)
{
if(s[i]=='.'&&nx[i])
{
(ans+=1LL*f[p]*f[c-p]%P*(i+g[nx[i]-1]-g[i])%P)%=P;
// printf("%d %d %d %d %d %d\n",i,nx[i],p,c-p,i+g[nx[i]-1]-g[i]);
++p;
}
}
printf("%d",ans);
}
标签:ARC132E,Paw,int,圆点,区间,2n
From: https://www.cnblogs.com/mekoszc/p/17896537.html