「FPS 24 題」全部解く: E「数列 3」

解きます

解く

「順番を無視して数えあげたもの」は
$$\left[x^N\right]\prod_{i=1}^M\sum_{j=0}^i x^j$$
です. (あえてシグマを有理関数に直してないです) これの順番を考慮すると,
$$N!\left[x^N\right]\prod_{i=1}^M\sum_{j=0}^i\frac{x^j}{j!}$$
になります. 全ての数が区別できる前提で並べかえるパターン数として$N!$を掛けて, 同じ数が複数あって区別できない分$j!$で割るといい感じに補正されます.

で, これを愚直に実装すればFFTを使わずとも$O\left(NM^2\right)$ができて, 十分高速です.

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

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize,
        m: usize,
    }
    // 階乗テーブル
    let factorial = {
        let mut r = vec![Mint::raw(1)];
        for i in 1..=300 {
            r.push(r[i - 1] * i);
        }
        r
    };
    // 階乗の逆数のテーブル (逆数計算は遅いので, あらかじめ計算して使い回せるようにする)
    let inv_factorial = factorial.iter().map(|x| x.inv()).collect::<Vec<_>>();

    // 最初に定数関数1にセットする
    let mut fps = vec![Mint::raw(0); n + 1];
    fps[0] = Mint::raw(1);

    for i in 1..=m {
        // fpsに Σ[0<=j<=i] x^j/j! をかける
        for k in (0..=n).rev() {
            // かけた後のk次の項の値を求める
            let mut c = Mint::raw(0);
            for j in 0..=k.min(i) {
                c += fps[k - j] * inv_factorial[j];
            }
            // その値にセットする
            fps[k] = c;
        }
    }
    // n次の係数のn!倍を出力して終了
    println!("{}", fps[n] * factorial[n]);
}

提出(18 ms):

終わり

これ指数型母関数っていうらしいですね.
以上です