AtCoder Regular Contest 096 E - Everything on It
問題文: E - Everything on It
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} $ の変形ができなくて自分の算数力の無さにびっくりしちゃった.