問題一覧 > 通常問題

No.840 Homu Homu Homura

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 87
作問者 : tempura_pp / テスター : keymoon
お気に入りにしたユーザー ProblemId : 2892 / 自分の提出
問題文最終更新日: 2019-06-13 00:15:52
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
yukicoder contest 215 (順位表) の他の問題:

Problem Statement

Tenpura likes Homu-chan. Tenpura also likes multiples of $K$.
Find the number of strings $S$ of length $N$ satisfying the following conditions, modulo $998244353$.

  1. The string contains no characters other than 「ほ」, 「む」, and 「ら」.
  2. The homu-degree of $S$ is a multiple of $K$. Here, the "homu-degree" is the number of tuples of integers $(i,\ j,\ k)$ satisfying all of the following conditions.
    • $1\le i < j < k \le N$
    • $S_i$ (the $i$-th character of $S$) $=$「ほ」
    • $S_j\ =$「む」
    • $S_k\ =$「ら」

Input

$N\ K$

  • $1\le N\le 10^9$
  • $2\le K\le 5$
  • Both inputs are integers.

Output

Print a newline at the end.

Sample

Sample 1
Input
4 2
Output
75

For example, 「ほむらら」 and 「ほむほむ」 have homu-degrees 2 and 0 respectively, so they satisfy the conditions. 「ほらむら」 has a homu-degree of 1, so it does not.

Sample 2
Input
7 4
Output
1430

The homu-degree of 「ほむほむほむら」 is 6.

Sample 3
Input
31415926 5
Output
753660663

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