# ARC145 F - Modulo Sum of Increasing Sequences

[リンク](https://atcoder.jp/contests/arc145/tasks/arc145_f)
だいたい公式解説と同じ方針だけども最後の方でよう分からん処理したら通ったのでメモ

#### 問題概要
$0\leq A_i \leq M$ の整数からなる長さ$N$の広義単調増加な数列$A$で、 $\sum_i A_i = k \pmod{P}$ なるものの個数を$k=0, 1, \cdots, P-1$ について998244353で求めて。
制約
$1 \leq N, M \leq M$
$1 \leq P \leq 500$

#### 解法メモ？
広義単調増加が扱いにくいので$B_1 = A_1, B_i = A_i - A_{i - 1}(i \geq 2)$ なる列$B$を考える。
$0 \leq A_i \leq M$ という制約は $0 \leq B_i, \sum_i B_i \leq M$ になる。
$B_N$ の$\sum_i A_i$ に対する寄与の係数は$1$, $B_{N - 1}$ は$2$,...,$B_1$ は$N$といった具合になる。
以上から求めるものは
$$[x^M]\frac{1}{1-x}\prod_{i=1}^N\frac{1}{1-y^ix}\pmod{y^P-1}$$
の各$y$の係数となる。
上の式を$f(y)$ とでも置くと
$$f(y) = [x^M]\prod_{i=0}^N\frac{1}{1-y^ix}\pmod{y^P-1}$$
と書き直せる。
さてここで$y$に1の原始$P$乗根$z$の$k$乗$(0 \leq k < P)$を突っ込んでみることを考える。
この時 $g = \gcd(P, k), q = P / g, a =\left\lfloor\frac{N+1}{q}\right\rfloor$ と置くと、$N+1$が$q$で割り切れない場合は
$$f(z^k)=[x^M]\frac{1}{(1-x^q)^{a+1}}\prod_{i=N+1}^{(a+1)q-1}(1-z^{ki}x)$$
と書ける。割り切れる場合は適当に。
分母が$q$次ごとにしか出てこないこと、分子が$q$次未満であることから適当なdpをすれば
$$f(z^k) = \sum_{i=0}^{P-1} C_{k, i} z^i$$
なる表現を得ることができる。各$k$についてdpを走らせると$O(P^4)$掛かるが計算結果を適切に使いまわせば$O(P^3)$となる。
ここから逆変換を行うことで
$$
\begin{aligned}
\left[y^i\right]f(y) &= \frac{1}{P}\sum_{j = 0}^{P-1} f(z^j)/z^{ij} \\
&= \frac{1}{P}\sum_{j=0}^{P-1} D_{i, j} z^j
\end{aligned}
$$
を得る。
よって解けた...と言いたいが$D_{i, j} \neq 0 (j \neq 0)$ な項あるし$998244353$のあまりで計算してるしで困ってしまう。
ところで何も考えずに $D_{i, j}$の計算を998244353 でやりきり、そのまま浮動小数点数を用いて上の式を計算して整数に丸めて998244353 のあまりに直すことを考える。するとサンプルあってくれて、投げると通る。
正当性は知らん。

[提出](https://atcoder.jp/contests/arc145/submissions/39765977)