← 返回题目列表

AtCoder · arc150_e

E. 风标

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

分数: 800 点

问题陈述

NK 人们从左到右站成一排。让我们将他们表示为人 i (0\leq i \leq NK-1) 从左到右。

每个人始终面向左或右。每个人当时的方向 t=0 用长度的字符串表示 N, S=S_0 S_1 \dots S_{N-1},包括 L 和 R。时 t=0, 人 i 面向左,如果 S_{i \bmod N} is L,如果是,则正确 R.

时间 t=0.5,\ 1.5,\ 2.5 ,\ \dots,这些人 同时 根据以下规则改变方向。

  • 当一个人面向左时:
    如果该人所面向的方向有一个或多个人,并且其中一半以上的人面向右侧,则该人会改变方向并面向右侧。否则,该人不会改变方向。
  • 当一个人面朝右侧时:
    如果该人所面对的方向有一个或多个人,并且其中一半以上的人面向左,则该人会改变方向并面向左。否则,该人不会改变方向。

求总和,模 998244353,次数 NK 人们会随着时间改变方向 t=0 to t=10^{100}.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • S 是一个长度为 N 组成 L 和 R.
  • 输入中的所有数值均为整数。

输入

输入由标准输入按以下格式给出:

N K
S

输出

打印答案。


示例输入 1

7 1
RRLRLLL

示例输出 1

9

如果我们代表七个人每次的方向,我们有 LLRLRRL at t=1, LLRLRLL at t=2,和 LLLLLLL at t=3.

之后 黑板上写着 t=3,七人的方向没有改变。因此,答案是 1+1+2+1+2+2+0=9.


示例输入 2

4 10
LLRR

示例输出 2

0

示例输入 3

23 200
RLRRRLLLLLLLLRRRLLRLRRR

示例输出 3

2207