Writer 解説: https://img.atcoder.jp/arc096/editorial.pdf

問題概要

ラーメンに $ N (\leq 3000)$ 種類のトッピングを乗せて注文する．乗せるトッピングの数に制限はなく，全部乗せることも全部乗せないこともできるので，トッピングの乗せ方は $ 2^N $ 通りある．

以下 2 つの条件を満たすラーメンの注文の仕方が何通りあるかを，$ \mathit{M}$ で割った余りをとって答えよ．

トッピングの組み合わせがまったく同じラーメンを複数杯注文しない．
$ N $ 種類のトッピングそれぞれが，注文したラーメンのうち 2 杯以上に乗っている．

解法概要

「すべてのトッピングが2回以上使われる」よりも「1回以下しか使われないトッピングがある」を数えた方が，トッピングの使われる回数について0回 / 1回だけ考えれば済んで良さそう．なので，数え上げる条件を「1回以下しか使われないトッピングがある」と考え，包除原理を用いる．つまり，

(1回以下しか使われないトッピングが0個以上ある) - (1回以下しか使われないトッピングが1個以上ある) + (1回以下しか使われないトッピングが2個以上ある) - ...

のような計算をすれば良い．

ここで，1回以下しか使われないトッピングが $ i$ 個以上ある場合に対応する項について考える．

この1回以下しか使われない$ i $種類のトッピングのいずれか1種類以上を含むようなラーメンが$ j$杯あったとしたときの$ i$種類のトッピングの分け方を$ f(i, j)$ とすると，$ f(i, j) = f(i-1, j) + f(i-1, j-1) + jf(i-1, j) = f(i-1, j-1) + (j+1)f(i-1, j)$のような Stirling 数のような漸化式が立てられる．$ f(i-1, j) $ は i 番目のトッピングを使わない場合，$ f(i-1, j-1) $ は i-1 番目までのトッピングを乗せていないラーメンに i 番目のトッピングを乗せる場合，$ jf(i-1, j) $ 他の "1回以下しか使われないことが確定しているトッピング" が乗っているラーメンに i 番目のトッピングも乗せる場合に対応する．

これを用いると，$ i $種類のトッピングのいずれか1種類以上を含むようなラーメンが$ j$杯あったとしたときのラーメンの注文方法の通り数は$ f(i, j) \times 2^{(N-i)j} \times 2^{2^{N-i}}$．$ 2^{(N-i)j} $ は $ i $種類のトッピングのいずれか1種類以上を含むような$ j$杯のラーメンにに対する，$ i $種類のトッピング以外のトッピングの乗せ方のパターン数である．また，$ 2^{2^{N-i}} $ は，$ j$杯のラーメン以外に注文するラーメンの注文方法に対応している．$ N-i$種類のトッピングの組み合わせ方は$ 2^{N-i} $ 通りで，そのそれぞれについて，注文する / しないが選べるためである．

また，$ N $種類のトッピングから $ i $種類選ぶ選び方は$ {}_N C_{i} $ 通りなので，$ i$ 種類以上のトッピングが1回以下しか使われないような注文の仕方の通り数は $ 2^{2^{N-i}} {}_N C_{i} \sum_{j=1}^{i} 2^{(N-i)j} f(i, j) $ となる．あとはこれを最初に包除原理を使って変形した式にぶちこむ．

2の累乗や2の2乗の累乗を事前に計算しておけば間に合う．

ソースコード

#include <iostream>

using namespace std;

using ll =  long long;

constexpr int N_MAX = 3001;

ll MOD;
ll s[N_MAX][N_MAX], pow2[N_MAX*N_MAX], powpow2[N_MAX];

void init_stirling(int n, int m) {
    for(int i=0;i<=n;++i) s[i][0] = 1;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            s[i][j] = (s[i-1][j-1] + (s[i-1][j]*(j+1)) % MOD) % MOD;
        }
    }
}

ll fact[N_MAX], rfact[N_MAX];

ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

void init(ll n){
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

int main() {
    ll n;
    cin >> n >> MOD;
    init(n);
    init_stirling(n, n);

    pow2[0] = 1LL;
    for(int i=0;i<n*n;++i) {
        pow2[i+1] = (2LL * pow2[i]) % MOD;
    }
    powpow2[0] = 2LL;
    for(int i=0;i<n;++i) {
        powpow2[i+1] = (powpow2[i] * powpow2[i]) % MOD; // 2^(2^n) = 2^(2^(n-1)) * 2^(2^(n-1))
    }

    ll ans = powpow2[n];
    for(ll i=1;i<=n;++i) {
        ll tmp = 0LL;
        for(ll j=0;j<=i;++j) {
            if(pow2[(n-i)*j] == 0) {
                pow2[(n-i)*j] = modpow(2LL, (n-i)*j);
            }
            tmp += pow2[(n-i)*j] * s[i][j];
            tmp %= MOD;
        }
        tmp *= comb(n, i);
        tmp %= MOD;
        tmp *= powpow2[n-i];
        tmp %= MOD;
        if(i % 2) {
            ans += MOD - tmp;
        } else {
            ans += tmp;
        }
        ans %= MOD;
    }

    cout << ans << endl;

}

所感

第二種スターリング数を学んだ問題その2．

$ 2^{2^{N+1}} = 2^{2^N} \times 2^{2^N} $ の変形ができなくて自分の算数力の無さにびっくりしちゃった．

NoiminのNoise

AtCoder Regular Contest 096 E - Everything on It

問題概要

解法概要

ソースコード

所感