← 返回题目列表

AtCoder · arc132_e

E. 爪子

中文机器翻译题面 查看原题

分数: 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