問題一覧 > 通常問題

No.840 ほむほむほむら

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : tempura_pptempura_pp / テスター : keymoonkeymoon
3 ProblemId : 2892 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-06-13 00:15:52

問題文

てんぷらはほむちゃんが好きです。あと $K$ の倍数も好きです。
以下の条件をみたす長さ $N$ の文字列 $S$ の個数を $998244353$ で割った余りを求めてください。

  1. 「ほ」「む」「ら」以外の文字を含まない。
  2. $S$ のほむ度が $K$ の倍数である。 ただし「ほむ度」とは以下の条件をすべてみたす整数 $(i,\ j,\ k)$ の組の個数のことを言う。
    • $1\le i < j < k \le N$
    • $S_i$($S$の$i$文字め) $=$「ほ」
    • $S_j\ =$「む」
    • $S_k\ =$「ら」

入力

$N\ K$

  • $1\le N\le 10^9$
  • $2\le K\le 5$
  • 入力はともに整数

出力

最後に改行してください。

サンプル

サンプル1
入力
4 2
出力
75

例えば「ほむらら」や「ほむほむ」はほむ度がそれぞれ2, 0なので条件をみたします。 「ほらむら」はほむ度が1なのでダメです。

サンプル2
入力
7 4
出力
1430

「ほむほむほむら」のほむ度は6です。

サンプル3
入力
31415926 5
出力
753660663

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