ARC096 E - Everything on It - くれなゐの雑記

問題

問題概要 & note

トッピングが $N$ 種類ある
一つのラーメンにはそれぞれのトッピングを1つか0つ乗せる
つまり全部で $2^{N}$ 個ラーメンができる
そのラーメンをいくつか選ぶ組み合わせは全部で $2^{2^{N}}$
そのようなラーメンを幾つか選んで、それぞれのトッピングが2個以上ラーメンに乗っているようにしたい。
全部で何通りのラーメンの組み合わせがあるでしょうか

考察(解説見た)

全部で $2^{2^{N}}$ 通りあって、そこから 一つ以上ののトッピングが1個以下 のようなものを除外する方針にする。どのように除外していくうかと言うと、たとえば、トッピングが2種類の場合は

「トッピングAが1個以下でほかは気にしない(1個以下でも2個以上でもいい)ラーメンの組み合わせ」除外する。
「トッピングBが1個以下でほかは気にしないラーメンの組み合わせ」を除外する
「トッピングAとトッピングBの両方が1個以下のラーメンの組み合わせ」を 追加する (なぜなら、Aを除外してBを除外すると、AB両方共通のものは2回減算されることになるから1回たさなければならない)

じゃあ3つの時はというとそれは3つめはまた引き算になる。一般化すると包除原理になる。

ここでよく考えてみると、「トッピングAが1個以下でほかは気にしないラーメンの組み合わせ」も「トッピングBが1個以下でほかは気にしないラーメンの組み合わせ」も数が一緒である「トッピングAB(ry」も「トッピングAC(ry」も数が一緒になるはずである。なのでより一般化すると「トッピング1~jまではi個以下で、ほかは気にしない組み合わせ」 * nCi とすれば、いちいち全部列挙しなくてもよくなる。

さて、それでは「トッピング1~iまでが一個以下ほかはどうでもいい」ラーメンの組み合わせの数は幾つあるのか？ここで $ways2(i,j)$ を, iまでのトッピングをjこのグループに分ける組み合わせの数(但し、グループに選ばないものがあっても良い)とする。これは、iまでのトッピングを、j個のラーメンに、2つ以上乗らないようにする組み合わせ数と同じで、 $\sum_{j=0}^N ways2(i,j)$ とすることで、iまでのトッピングが一つ以下しか乗っていないものの個数がO(N)で求められる。

ways2は第二種スターリング数に似たdpで解くことができる。第二種スターリングのままでは、選ばないトッピングがものを数え上げてしまうので、選ばないものを許すために、二項目の\tex[k]を\tex[(k+1)]とすることで、うまくいく(どこにも所属しないという新たなグループを作るイメージ)また、第二種スターリング数と違い、0個の選択を許すので、\tex[k=0]の時は1になることに注意する。

あとは、図を書いて説明しないといけないので、こちらの解説放送を見ていただきたい　AtCoder Regular Contest 096/ Beginner Contest 095 解説放送 - YouTube

source code

// binomial coefficients O(n^2)
// res[i][j] = C(i,j) (i , j <= n)
// C(i,j) =  C(i-1, j-1) + C(i-1, j)
vector<vector<int> > BinomialCoefficients(int n) {
    vector<vector<int > > res;
    res.resize(max(n+1,2LL));
    res[0].push_back(1);
    res[1].push_back(1);
    res[1].push_back(1);
 
    FOR(i, 2, res.size()){
        res[i].push_back(1);
        FOR(j,1,i){
            res[i].push_back((res[i - 1][j - 1] + res[i - 1][j])%MOD);
        }
        res[i].push_back(1);
    }
    return res;
}
 
// Stirling NUmber of The Second Kind O(n^2)
// note: NOT symmetry!!!
// S(n, k) = S(n, k-1) + k*S(n-1, k)
vector<vector<int> > StirlingNumber2(int n) {
    vector<vector<int > > res;
    res.resize(max(n+1,2LL));
    res[0].push_back(1);
    res[1].push_back(1);
    res[1].push_back(1);
 
    FOR(i, 2, res.size()) {
        res[i].push_back(1);
        FOR(j,1,i){
            res[i].push_back((res[i-1][j - 1] + (j+1)*res[i-1][j]) % MOD);
        }
        res[i].push_back(1);
    }
    return res;
}
 
void solve() {
    int N; cin >> N >> MOD;
    vector<vector<int> > b = BinomialCoefficients(N);
    vector<vector<int> > s2 = StirlingNumber2(N);
    vector<int> pow2(N*N+1);
    vector<int> powpow2(N+1);
    pow2[0] = 1;
    powpow2[0] = 2;
    FOR(i, 1, pow2.size()) pow2[i] = (pow2[i - 1] * 2)%MOD;
    FOR(i, 1, powpow2.size()) powpow2[i] = (powpow2[i - 1] * powpow2[i - 1]) % MOD;
    vector<int> ways(N + 1);
 
    int res = 0;
    REP(i, ways.size()) {
        int w = 0;
        REP(j, i + 1) {
            int temp = (s2[i][j] * pow2[(N - i)*j]) % MOD;
            temp = (temp * powpow2[N - i]) % MOD;
            w = (w + temp) % MOD;
        }
        int temp = (w * b[N][i]) % MOD;
        temp *= (i % 2 == 0 ? 1 : -1);
        res = (res + temp);
        while (res < 0) res += MOD;
        res %= MOD;
    }
    cout << res << endl;
}

note

$a^{b} (\mathrm{mod}\ p) = a^{b\ \mathrm{mod}\ (p-1)} (\mathrm{mod}\ p)$

フェルマーの小定理より、 $a^{p-1} = 1$ つまり、 $a^{p-1}$ を何度かけても1を掛け算するので答えは変わらない $a^{b} = a^{b/p-1} * a^{b \% (p-1)} = a^{p-1} * a^{p-1} * \cdots * a^{p-1} * a^{b \% (p-1)} = a^{b \% (p-1)}$