AtCoder ARC 067 E - Grouping 形式的冪級数解

https://atcoder.jp/contests/arc067/tasks/arc067_c

hotmanさんの

https://blog.misw.jp/entry/2019/12/18/000000

の記事でGrouping がfpsで解けるとあったので解いてみました

解説

「i人含まれるグループの数は0かc~d人」というのが扱いづらいので、一つの式にまとめる。

(1 + x^ic + x^i(c+1) ... x^id)   

まとめるとこうなり

[x^N]Π (1 + x^ic + x^i(c+1) ... x^id)   {A<=i<=D} 

 答えはこういう空気になる

人を区別しない場合はこのままでいいが、今回は区別するためもう少し必要。

具体的には全体にN!を掛け、それぞれのグループ毎に重複した分を割ればいい

i人のグループがc組ある場合、i!^c * c!だけ重複するため

[x^N]Π (1 + 1/(i!^c * c!) * x^ic + 1/(i!^(c+1) * (c+1)!) * x^i(c+1) ... 1/(i!^d * d!) *  x^id)   {A<=i<=D}

 が答え

それぞれの項は長さがNでO(N)回掛けられるのでFFTでO(N*N log N)で解けた

void solve() {
    din(N, A, B, C, D);
    fps ret(1001);
    ret[0] = fac[N];
    rep(i, A, B + 1) {
        fps r(1001);
        r[0] = 1;
        rep(f, C, D + 1) {
            if (i * f > 1000)break;
            r[i * f] = mpow(finv[i], f) * finv[f];
        }
        ret *= r;
        ret.resize(1001);//しないと長さがやばい
    }
    out(ret[N]);
}