AT_abc470_f.Googol Swaps

普及+/提高

通过率：0%

时间限制：2.00s

内存限制：1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N$ 、仅由小写英文字母组成的字符串 $S$ 。

进行下面的操作 恰好 $10^{100}$ 次 后，求字符串 $S$ 最终可能变成多少种不同的字符串。

答案对 $998244353$ 取模。

每次操作如下：

选择一个满足 $1\le i\le M$ 的整数 $i$ ，交换字符串 $S$ 的第 $A_i$ 个字符和第 $B_i$ 个字符。

输入格式

输入格式如下：

N M
S
A1 B1
⋮
AM BM

输出格式

输出答案。

输入输出样例

输入#1
```
5 3
miria
1 3
2 5
4 5
```
输出#1
```
6
```
输入#2
```
6 6
yiwayi
1 2
1 3
2 3
4 5
4 6
5 6
```
输出#2
```
18
```

输入#3

29 25
hexakosioihexekontahexaphobia
1 2
1 4
1 6
1 8
1 15
1 16
2 3
3 4
4 20
5 6
5 8
8 22
8 23
9 15
9 17
11 21
12 20
13 19
14 29
15 28
16 17
18 19
18 21
19 20
20 21

输出#3

346192062

说明/提示

样例一解释

最终的 $S$ 一共有以下六种可能：

marii
mirai
miria
ramii
rimai
rimia

数据范围

$N$ 和 $M$ 均为整数。
$2\le N\le2\times10^5$
$1\le M\le2\times10^5$
$S$ 是一个长度为 $N$ 、仅由小写英文字母组成的字符串。
$A_i$ 和 $B_i$ 均为整数。
$1\le A_i<B_i\le N$
$(A_1,B_1),\ldots,(A_M,B_M)$ 两两不同。

输入解题思路，AI测评打分。不知道怎么写?

首页