Beautiful Palindrome

解説

$M = 1$ の場合、$N ~ \mathrm{mod} ~ 998244353$ が答えです。以降 $M \ge 2$ の場合を考えます。

正整数 $k$ が長さ $M$ の文字列の中に含まれるループ文字の個数としてあり得ることと、$k - 1$ が $M - 1$ の約数であることは同値です。
理由は、文字列の末尾のループ文字 $1$ 個を除いたとき、$1$ 個のループ文字とある非負整数個のスペースがこの順に並べられた文字列が $k$ 個並べられた文字列として考えられるためです。

また $k$ 個のループ文字を含む回文の個数は、先頭 $\lceil k / 2 \rceil$ 個のループ文字を決めれば、他の文字も決まるため $N^{\lceil k / 2 \rceil}$ 個となります。
よって、$\displaystyle \sum_{k - 1 |M - 1} N ^{\lceil k/2 \rceil} ~ \mathrm{mod} ~ 998244353$ が答えです。

$M - 1$ の約数の個数は $O(\sqrt M)$ 個に抑えられ、累乗計算は繰り返し二乗法を用いて $O(\log N)$ で計算可能なため、 $O(\sqrt{M}\log N)$ で解くことができました。

想定解