分数: 800 点
问题陈述
有 n 方块排成一排。每个方块都有一个向左或向右的足迹或一个洞。
每个方块的初始状态由一个字符串描述 s 组成 ., <, >。如果 i第一个字符 s is ., i左边第一个方格有一个洞;如果该字符是 <,该正方形有一个指向左的足迹;如果该字符是 >,该正方形有一个向右指向的足迹。
Snuke,猫,将重复以下过程,直到不再有带孔的方块。
- 步骤 1:以等概率随机选择一个有洞的方格。
- 步骤 2:填充所选方格中的洞,站在那里,以相等的概率随机面向左或右。
- 步骤 3:沿着Snuke所面对的方向继续行走,直到他踩到一个有洞的方格或退出这排方格。
这里,方格和方向的选择是相互独立的。
当斯努克在一个正方形(没有洞)上行走时,该正方形会在他行走的方向上留下足迹。
如果该方块已经有足迹,它将被擦除并被新的足迹取代。
例如,在这种情况下 >.<><.><,如果 Snuke 选择 6从左边数第一个方格,面朝左, 6-th, 5-th, 4-th, 3-rd 方块获得左指脚印: >.<<<<><.
求 Snuke 完成程序时左指足迹数量的期望值,取模 998244353.
注释
当寻求的期望值表示为不可约分数时 p/q,唯一存在一个整数 r 这样 rq\equiv p ~(\text{mod } 998244353) 和 0 \leq r \lt 998244353 这个问题的约束下。 这个 r 是要查找的值。
约束
- 1 \leq n \leq 10^5
- s 是一个长度为的字符串 n 组成
.,<,>. - s 包含至少一个
..
输入
输入由标准输入按以下格式给出:
n s
输出
打印左指足迹数量的期望值,模 998244353.
示例输入 1
5 ><.<<
示例输出 1
3
步步为营 1,Snuke 总是选择唯一有洞的方格。
如果 Snuke 在步骤中面向左侧 2,方块变成 <<<<<,其中 5 方块具有指向左的足迹。
如果 Snuke 在步骤中面向右侧 2,方块变成 ><>>>,其中 1 正方形有一个向左的足迹。
因此,答案是 \frac{5+1}{2}=3.
示例输入 2
20 >.>.<>.<<.<>.<..<>><
示例输出 2
848117770