[PA 2022] Wielki Zderzacz Termionów

Luogu
IDLGP9252
Time2000ms
Memory512MB
DifficultyP6
2022PA(波兰)
**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 1 [Wielki Zderzacz Termionów](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/wzt/)** Albert Bynstein 教授发现了一种新的基本粒子:热离子。如果他的实验成功,就可以在他的帮助下修建一个发电站,这样就可以解决 Byteland 的能源问题了。 这些粒子有三种类型,用红色,绿色和蓝色表示。这个名称与粒子实际的颜色或者光的波长无关,只是 Bynstein 教授用这些颜色的马克笔标记这些粒子。 红色和绿色的热离子可以发生反应,但只与另一个相同颜色的粒子发生反应。当两个红色热离子碰撞时,产生一个绿色热离子,并释放 $1$ 字节焦耳的能量。如果两个绿色热离子发生碰撞,就会产生一个红色热离子,同时释放 $1$ 字节焦耳的能量。 蓝色热离子不与其他热离子反应,但是它们是不稳定的。产生蓝热离子 $72$ 小时后,它会随机变成红热离子或绿热离子中的一个,变成任何离子都不会释放能量。 教授正在准备一个受控的实验反应。为此,他在实验室里准备了排成一排的 $n$ 个热离子。几天后,他打算把这些离子带到目前正在首都地下建造的大型热离子对撞机。到那时,所有的蓝色热离子都将变成红色或绿色热离子。 在对撞实验中,教授想进行一连串的反应,以产生 $n-1$ 字节焦耳的能量,并最后只留下一个热离子。每次反应可以选择相邻的两个热离子。所产生的热离子与左边和右边的热离子相邻,并能与它们发生进一步的反应。 问题是,当所有的蓝色热离子都发生变化时,有多大概率存在一个可行的反应序列。 你的任务是计算蓝色热离子有多少种变化方式(对 $10^9+7$ 取模)能使完整的反应序列进行下去。 此外,教授还会在他的实验室里对热离子的位置进行改变,每次都把一个热离子换成另一个(也许不会改变其类型)。在每一次这样的变化之后,也要计算出结果。 ## Input 第一行包含两个整数 $n$ 和 $q$ 分别表示热离子个数和改变次数。 第二行一个长为 $n$ 的字符串,表示初始时热离子的排列情况。字符串只包含 `C`,`Z` 和 `N` 三种字符,分别表示红色,绿色和蓝色热离子。左起第 $k$ 个字符表示第 $k$ 个热离子的颜色。 接下来 $q$ 行表示对上述字符串的修改。每行包含一个数字 $k_i$ 和一个字符(`C`,`Z` 和 `N` 之一)。表示第 $i$ 步中,教授将第 $k_i$ 个粒子换成了这个字符所表示的新粒子。 ## Output 输出 $q+1$ 行,第 $i+1$ 行输出一个整数,表示经过前 $i$ 个修改后的答案。 输出蓝色热离子有多少种变化方式(对 $10^9+7$ 取模)能使完整的反应序列进行下去,生成 $n-1$ 字节焦耳能量。 [samples] ## Note 对于 $100\%$ 的数据,满足: $1\le n\le 2 \times 10 ^ 5, 0\le q\le 10 ^ 5, 1\le k_i\le n$。
Samples
Input #1
5 3
NNCCZ
3 N
2 Z
1 Z
Output #1
3
5
3
1
API Response (JSON)
{
  "problem": {
    "name": "[PA 2022] Wielki Zderzacz Termionów",
    "description": {
      "content": "**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 1 [Wielki Zderzacz Termionów](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/wzt/)** Albert Bynstein 教授发现了一种新的基本粒子:热离子。如果他的实验成功,就可以在他",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9252"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 1 [Wielki Zderzacz Termionów](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/wzt/)**\n\nAlbert Bynstein 教授发现了一种新的基本粒子:热离子。如果他的实验成功,就可以在他...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments