問題一覧 > 通常問題

No.2636 No Waiting in Vain

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 36
作問者 : matcharate12 / テスター : kemuniku
ProblemId : 9685 / 自分の提出
問題文最終更新日: 2024-02-13 20:34:36
ストーリー(読まなくていいです)
ラテ君は暇な人です。別に予定もなく、ただ平凡な毎日を過ごしていました。しかしコンテストには毎回参加しています。
暇をもてあそぶのは、もうやめようということで、次のように考えました。

「なんか素敵な用事を新たに計画するか！！！」

問題文

長さ $N$ の文字列 $S$ が与えられ、これはラテ君の $N$ 日間の予定を表します。$S$ の $i\ (1\le i\le N)$ 番目の文字 $S_i$ は、次のようなことを表します。

  • $S_i=$ P のとき、$i$ 日目には既に予定が入っていることを表す
  • $S_i=$ C のとき、$i$ 日目にはコンテストの予定が入っていることを表す
  • $S_i=$ N のとき、$i$ 日目には何も予定が無いことを表す

    • また $S_i$ を $i$ 日目の予定と言うことにします。ここでラテ君は次の条件を満たすように、新たに $1$ つ以上、予定 P を入れることにしました。
    ただし新たに予定を入れる日は、$S_i=$ N の日に限ります。他の日、すなわち $S_i=$ P, C の日には予定を入れることはできません。

    [条件]
  • コンテストの日の翌日には、コンテスト以外の予定を入れない。すなわち新たに予定を変更した後、すべての $i\ (1\le i\le N-1)$ に対して $S_i=$ C ならば $S_{i+1}\ne$ P が成り立つ。
  • 予定が入っていない日は少なくとも $K$ 日以上ある。すなわち新たに予定を変更した後、すべての $i\ (1\le i\le N)$ に対して $S_i=$ N なる $i$ の個数は $K$ 以上である。

    • 上の条件をすべて満たすような、予定 P の入れ方は何通り考えられますか？ただし答えはとても大きくなることがあるので、$998244353$ で割ったあまりを求めて下さい。

    入力

    $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$ は P,C,Nからなる
    • $S$ は問題文の条件を満たす。すなわち
      • すべての $i\ (1\le i\le N-1)$ に対して $S_i=$ C ならば $S_{i+1}\ne$ P である
      • $1\le i\le N$ に対して $S_i=$ N なる $i$ の個数は $K$ 以上である
    • $N,K$ は整数

    テストケース詳細 (読まなくても構いません)

    この問題では部分点は存在しませんが、ケースによって制約が異なります。

  • small.txt: $1\le N\le 2000$
  • large.txt: 追加の制約はない。

    • 出力

    答えを出力してください。

    サンプル

    サンプル1
    入力
    5 2
NNCNP
    出力
    2

    新たに予定 P を入れますが、ここではその予定を T とします。
    まず、条件を考えずに新たに $1$ つ以上の予定 P を入れるとすると、次の $7(=2^3-1)$ 通りが存在します。

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

    • ここで、例えば NNCTP は「コンテストの翌日には予定を入れない」ことに違反します。また NTCTP は「予定が入っていない日が少なくとも $K(=2)$ 日以上ある」ことに違反します。
    こうして問題文の条件に違反するものを除くと、NTCNP 、TNCNP の $2$ つが残ります。したがって答えは $2$ 通りとなります。

    サンプル2
    入力
    3 1
PNC
    出力
    0

    新たに予定を $1$ つも入れることはできません。

    サンプル3
    入力
    10 1
PCNPCNNPCN
    出力
    1

    PCNPCNTPCN のみ、すなわち $7$ 日目に予定を入れることだけが条件を満たします。

    サンプル4
    入力
    9 0
PCCCCCCCN
    出力
    0

    コンテストの日が続いていますが、これは問題文の条件を満たしています。ラテ君は"コンテスト"が好きなのでしょうか...？

    サンプル5
    入力
    29 10
NNCNNNNNPCNNNNNNCNNNNNNCNNNPN
    出力
    507623

    $998244353$ で割った余りであることを忘れないでください。

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