$x$についての形式的冪級数$f$の$x^i$の係数を$[x^i]f$と表すと、サイコロを$k$回振った時、出た目の合計が$i$になる確率は$[x^i]\left(\frac{1}{n}x+\frac{1}{n}x^2+\cdots+\frac{1}{n}x^n\right)^k$となります。よって、$g(x)=\left(\frac{1}{n}x+\frac{1}{n}x^2+\cdots+\frac{1}{n}x^n\right)^k$とおくと、求める確率は$2^m$の倍数であるような$i$について$[x^i]g$を合計した値となります。ここで、$[x^i]g=c_i$とすると、$g(x)=\displaystyle\sum_{i}c_ix^i$となります。また、求める確率$p=\displaystyle\sum_{2^m \mid i}c_i$となります。

ここで、$1$の$2^m$乗根を$\xi$とすると、$i$が$2^m$の倍数の時$\displaystyle\sum_{j=0}^{2^m-1}\xi^{ij}=\displaystyle\sum_{j=0}^{2^m-1}1^{j}=2^m$となり、そうではない時は$\xi^i \neq 1$なので、 $\displaystyle\sum_{j=0}^{2^m-1}\xi^{ij}=\frac{1-(\xi^i)^{2^m}}{1-\xi^i}=\frac{1-(\xi^{2^m})^i}{1-\xi^i}=\frac{1-1^i}{1-\xi^i}=0$となります。よって、$\displaystyle\sum_{j=0}^{2^m-1}g(\xi^j)=\sum_{i}c_i\displaystyle\sum_{j=0}^{2^m-1}\xi^{ij}=2^m\displaystyle\sum_{2^m \mid i}c_i=2^m p$となるので、$p=\displaystyle\frac{1}{2^m}\displaystyle\sum_{j=0}^{2^m-1}g(\xi^j)$となります。

次に、適切な$\xi$を求めます。$3$は$998244353(=119 \times 2^{23}+1)$の原始根の1つなので、$2^{119 \times 2^{23-m}}$は$1$の$2^m$乗根の1つです。よって、$2^{119 \times 2^{23-m}}$を$998244353$で割った余りを$\xi$とすれば良いです。

最後に、$g(\xi_j)$の求め方について述べます。$x+x^2+\cdots+x^n$をそのまま計算すると、$0 \leq j < 2^m$における計算量が$O(2^mn)$となってしまい、制限時間に間に合いません。そこで、$x=1$すなわち$j=0$の場合は$g(x)=1$とし、それ以外の場合は$g(x)=\left(\displaystyle\frac{1}{n}x\cdot\frac{x^n-1}{x-1}\right)^k=\displaystyle\frac{x^k(x^n-1)^k}{n^k(x-1)^k}$として、これに$x=\xi^j$を代入します。

これにより、${\rm mod}\ 998244353$における除算は定数時間で行えるものとすると、$p$は$O(2^m\log k)$で計算できるため、十分時間内に間に合います。

解答例

modint型を利用するため、AC Libraryの一部を引用しました。引用した部分に関しては、解答例にその旨を明記してあります。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378