https://www.luogu.com.cn/problem/AT_arc132_e
由于一旦走到头那么这一个后缀/前缀就一定是对应的颜色，所以最终答案形如一段左脚印，一段保留原来的，一段右脚印。
保留原来的段一定是在两个洞之间的一段完整段，考虑枚举这个段，左脚印的数量是确定的，转化成算概率的问题。
这实际上等价于这样一个问题：给 \(n\) 个点，每次随机一个点向左/向右，问一直触碰不到右边界的概率。
考虑触碰到右边界一定是选择了一个最右边的点并且向右走，那么就可以列出 dp 式：
\[f_i=\sum_{j=1}^{i} \cfrac{1}{2i}f_{j-1}
\]
其中 \(j\) 表示的是最靠右的点出现在排列中的位置，每个位置概率相等都是 \(\cfrac{1}{i}\)，再乘上在这里一定向左，概率 \(\cfrac{1}{2}\)。
前缀和优化，复杂度 \(O(n)\)。
#include<bits/stdc++.h>
#define N 301001
#define MAX 2001
using namespace std;
typedef long long ll;
typedef double db;
const ll inf=1e9,mod=998244353,inv2=(mod+1)/2;
inline void read(ll &ret)
{
ret=0;char c=getchar();bool pd=false;
while(!isdigit(c)){pd|=c=='-';c=getchar();}
while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
ret=pd?-ret:ret;
return;
}
ll n,sum[N],pre[N],dp[N],st[N],inv[N],ans;
char s[N];
signed main()
{
read(n);
scanf("%s",s+1);
for(int i=1;i<=n;i++)
pre[i]=pre[i-1]+(s[i]=='.');
ll las=0;
dp[0]=1;
st[0]=1;
inv[1]=1;
for(int i=2;i<N;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<N;i++)
dp[i]=st[i-1]*inv2%mod*inv[i]%mod,st[i]=(st[i-1]+dp[i])%mod;
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+(s[i]=='<');
if(s[i]=='.')
{
if(las)
ans+=dp[pre[las]]*(las-1+sum[i]-sum[las]+1)%mod*dp[pre[n]-pre[i-1]]%mod;
else
ans+=dp[pre[n]-pre[i-1]]*sum[i]%mod;
las=i;
}
}
if(!las)
ans=sum[n];
else
ans+=(sum[n]-sum[las]+las)*dp[pre[las]]%mod;
printf("%lld\n",(ans%mod+mod)%mod);
exit(0);
}