問題一覧 > 通常問題

No.2636 No Waiting in Vain

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 37
作問者 : matcharate12 / テスター : kemuniku
お気に入りにしたユーザー ProblemId : 9685 / 自分の提出
問題文最終更新日: 2024-02-13 20:34:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Story (you do not need to read this)
Latte is a person with a lot of free time. He had no particular plans and was just spending one ordinary day after another. However, he takes part in every contest.
Deciding to stop idling his time away, he thought as follows:

"Maybe I should plan some wonderful new errands!!!"

Problem Statement

You are given a string $S$ of length $N$, which represents Latte's schedule for $N$ days. The $i\ (1\le i\le N)$-th character $S_i$ of $S$ means the following.

  • If $S_i=$ P, a plan is already scheduled on day $i$.
  • If $S_i=$ C, a contest is scheduled on day $i$.
  • If $S_i=$ N, nothing is scheduled on day $i$.

    • We also refer to $S_i$ as the schedule of day $i$. Latte has decided to add $1$ or more new plans P so that the conditions below are satisfied.
    New plans can only be added on days with $S_i=$ N. On the other days, that is, days with $S_i=$ P, C, no plan can be added.

    [Conditions]
  • On the day after a contest day, no plan other than a contest is scheduled. That is, after the schedule has been changed, for all $i\ (1\le i\le N-1)$, if $S_i=$ C then $S_{i+1}\ne$ P holds.
  • There are at least $K$ days with nothing scheduled. That is, after the schedule has been changed, for all $i\ (1\le i\le N)$, the number of $S_i=$ N such $i$ is at least $K$.

    • How many ways are there to add plans P so that all of the above conditions are satisfied? Since the answer can be very large, find it modulo $998244353$.

    Input

    $N\ K$
$S_1S_2\dots S_N$

    • $1\le N\le 3\times 10^5$
    • $0\le K\le N$
    • $|S|=N$
    • $S_i$ consists of P,C,N
    • $S$ satisfies the conditions in the problem statement. That is,
      • for all $i\ (1\le i\le N-1)$, if $S_i=$ C then $S_{i+1}\ne$ P
      • for $1\le i\le N$, the number of $S_i=$ N such $i$ is at least $K$
    • $N,K$ are integers

    Test case details (you do not need to read this)

    This problem has no subtasks, but the constraints differ depending on the case.

  • small.txt: $1\le N\le 2000$
  • large.txt: No additional constraints.

    • Output

    Output the answer.

    Sample

    Sample 1
    Input
    5 2
NNCNP
    Output
    2

    We add new plans P, and here we denote those plans by T.
    First, if we add $1$ or more new plans P without considering the conditions, there are the following $7(=2^3-1)$ ways.

  • TNCNP
  • NTCNP
  • NNCTP
  • TTCNP
  • TNCTP
  • NTCTP
  • TTCTP

    • Here, for example, NNCTP violates "no plan is scheduled on the day after a contest". Also, NTCTP violates "there are at least $K(=2)$ days with nothing scheduled".
    Removing the ones that violate the conditions in the problem statement in this way leaves NTCNP and TNCNP, which are $2$ ways. Therefore, the answer is $2$.

    Sample 2
    Input
    3 1
PNC
    Output
    0

    It is impossible to add even $1$ new plan.

    Sample 3
    Input
    10 1
PCNPCNNPCN
    Output
    1

    Only PCNPCNTPCN, that is, adding a plan on day $7$, satisfies the conditions.

    Sample 4
    Input
    9 0
PCCCCCCCN
    Output
    0

    The contest days are consecutive, but this satisfies the conditions in the problem statement. Perhaps Latte likes "contests"...?

    Sample 5
    Input
    29 10
NNCNNNNNPCNNNNNNCNNNNNNCNNNPN
    Output
    507623

    Do not forget to take the remainder modulo $998244353$.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。