「FPS 24 題」全部解く: A「お菓子」

解きます

解く

$n$次の係数が「$n$円になる組合せ」を表すとすると, 1日に対応するFPSは$x+x^3+x^4+x^6$です.
これを$D$日間繰り返すので$D$乗して, 求めるものは$\left[x^N\right]\left(x+x^3+x^4+x^6\right)^D$です.

↓によるとこれが$O\left(N\right)$で計算できるらしいので, 読んでやってみます.

とりあえず
$$\left[x^N\right]\left(x+x^3+x^4+x^6\right)^D=\left[x^{N-D}\right]\left(1+x^2+x^3+x^5\right)^D$$
という式変形をして, 定数項を非零にしてやります.

さて, $f:=1+x^2+x^3+x^5$, $g:=f^D$とし, $g$を$x$について微分すると
$$\frac{\mathrm d g}{\mathrm dx} = \frac{\mathrm d f}{\mathrm dx}Df^{M-1}$$
更に両辺に$f$を掛けると
$$f\frac{\mathrm d g}{\mathrm dx} = D\frac{\mathrm d f}{\mathrm dx}g$$
となります.

両辺の$M$次の項の係数を見ると
左辺:
$$\begin{alignat}{2}
\left[x^M\right]f\frac{\mathrm d g}{\mathrm dx}
&= \left[x^M\right]\left(\frac{\mathrm d g}{\mathrm dx}+x^2\frac{\mathrm d g}{\mathrm dx}+x^3\frac{\mathrm d g}{\mathrm dx}+x^5\frac{\mathrm d g}{\mathrm dx}\right) \\
&= \left[x^M\right]\frac{\mathrm d g}{\mathrm dx}+\left[x^{M-2}\right]\frac{\mathrm d g}{\mathrm dx}+\left[x^{M-3}\right]\frac{\mathrm d g}{\mathrm dx}+\left[x^{M-5}\right]\frac{\mathrm d g}{\mathrm dx} \\
&= \left(M+1\right)\left[x^{M+1}\right]g+\left(M-1\right)\left[x^{M-1}\right]g\\ &\qquad+\left(M-2\right)\left[x^{M-2}\right]g+\left(M-4\right)\left[x^{M-4}\right]g
\end{alignat}$$

右辺:
$$\begin{alignat}{2}
\left[x^M\right]D\frac{\mathrm d f}{\mathrm dx}g
&= \left[x^M\right]\left(2Dxg+3Dx^2g+5Dx^4g\right) \\
&= 2D\left[x^{M-1}\right]g+3D\left[x^{M-2}\right]g+5D\left[x^{M-4}\right]g \\
\end{alignat}$$
で, この両辺が等しいので, 左辺から右辺を引いて
$$\begin{align}
&\left(M+1\right)\left[x^{M+1}\right]g+\left(M-1-2D\right)\left[x^{M-1}\right]g\\
&\quad+\left(M-2-3D\right)\left[x^{M-2}\right]g+\left(M-4-5D\right)\left[x^{M-4}\right]g=0
\end{align}$$
$M$を$M-1$に置き換えて整理すると
$$\begin{align}
&M\left[x^M\right]g\\
&\quad=\left(2D+2-M\right)\left[x^{M-2}\right]g+\left(3D+3-M\right)\left[x^{M-3}\right]g+\left(5D+5-M\right)\left[x^{M-5}\right]g
\end{align}$$
こういう形で漸化式になりました.
$\left[x^0\right]g=1$なので, ここからループを回せば$O(N)$で答えが求められます.

use ac_library::*;
use proconio::*;

type Mint = ModInt998244353;

fn main() {
    input! {
        d: i32,
        n: i32,
    }
    // n < dなら常に答えが0なので先に弾く
    if n < d {
        println!("0");
        return;
    }
    // [x^0]g = 1
    let mut g = vec![Mint::raw(1)];
    for m in 1..=n - d {
        // 上記の式の右辺
        let rhs = [2, 3, 5]
            .map(|r| if r > m { Mint::raw(0) } else { g[(m - r) as usize] } * (r * d + r - m))
            .iter()
            .sum::<Mint>();
        // rhsをmで割ったら[x^m]gになる
        g.push(rhs / m);
    }
    // [x^(n-d)]gを出力
    println!("{}", g[(n - d) as usize]);
}

提出(107 ms):

解説を読んでみる

解説はこれとは違う方法で解いているようです.

$\left[x^{N-D}\right]\left(1+x^2+x^3+x^5\right)^D$に変形するところまでは一緒ですが,
これを$\left[x^{N-D}\right]\left(1+x^2\right)^D\left(1+x^3\right)^D$に因数分解し,

$$\sum_{k=0}^{N-D}\left(\left[x^k\right]\left(1+x^2\right)^D\right)\left(\left[x^{N-D-k}\right]\left(1+x^3\right)^D\right)$$
と変形します. 二項定理から任意の自然数$n$で
$\left[x^k\right]\left(1+x^n\right)^D=\begin{cases}
\binom{D}{k\div n} &\text{if } n\mid k \\
0 &\text{if } n\nmid k
\end{cases}$
なので, これを使って$O\left(N\right)$で答えが求められます.

use ac_library::*;
use proconio::*;

type Mint = ModInt998244353;

fn main() {
    input! {
        d: usize,
        n: usize,
    }
    // n < dなら常に答えが0なので先に弾く
    if n < d {
        println!("0");
        return;
    }
    // 階乗テーブル
    let factorial = {
        let mut r = vec![Mint::raw(1)];
        for i in 1..=1000000 {
            r.push(r[i - 1] * i);
        }
        r
    };
    // 二項係数
    let binom = |a: usize, b: usize| {
        if b > a {
            Mint::raw(0)
        } else {
            factorial[a] / (factorial[b] * factorial[a - b])
        }
    };
    let mut ans = Mint::raw(0);
    for k in 0..=n - d {
        // 因数の片方が0になるケースを弾く
        if k % 2 != 0 || (n - d - k) % 3 != 0 {
            continue;
        }
        ans += binom(d, k / 2) * binom(d, (n - d - k) / 3);
    }
    println!("{ans}");
}

提出(27 ms):

終わり

初日から結構ハードですね
以上です