ながめも

競技プログラミングについて

トップ > ABC > AtCoder Beginner Contest 172 ABC172 E - NEQ 解説

AtCoder Beginner Contest 172 ABC172 E - NEQ 解説

ABC 数え上げ 包除原理

E - NEQ

問題へのリンク

問題文

1以上 M以下の整数からなる長さ Nの数列 Aと Bの組であって、以下の条件をすべて満たすものの個数を求めよ。

  • 1 \le i \le Nなる任意の iについて A_i \neq B_i
  • 1 \le i \lt j \le Nなる任意の (i, j)について A_i \neq A_jかつ B_i \neq B_j

制約

  • 1 \le N \le M \le 5 \times 10^{5}

解説

まず、対称性から、数列 Aを固定して考えます。わかりやすいように \{1,2,...,N\}で考えます。 問題分の条件を言い換えると、

  • 一個も同じところがない

ということなので、この余事象は

  • 少なくとも一個同じところがある

となります。この数え上げは、包除原理を用いるとできます。

包除原理を考えると、少なくとも K個同じところがあるという事象の数え上げができればよいことがわかります。 これは、まず同じになるところを N箇所から K箇所選んで、他はなんでもいいという場合の数なので

{}_N C_K \times {}_{M-K} P_{N-K}（ = f(K)とおく）になります。

全事象は {({}_M P_{N})}^{2}なので、求める答えは

{ \displaystyle {({}_M P_{N})}^{2} - {}_M P_{N}\sum _{K = 1}^{N}{{(-1)}^{(K-1)}f(K)} }

実装

int main() {
    ll n, m;
    cin >> n >> m;
    mint ans = C.Perm(m,n) * C.Perm(m,n);
    //少なくとも一個重なっている個数
    mint sub = 0;
    /*calc*/
    // 何個重なっているかで場合わけ
    // ある配列 1,2,3,...Nについて考察
    //同じになる場所の個数 nCk
    //残りn-k個の選び方 m-k個の数の集合から選んで並べる m-kPn-k
    for(int k = 1; k <= n; k++){
        mint tmp = C.Comb(n,k) * C.Perm(m-k,n-k);;
        if(k&1)sub += tmp;
        else sub -= tmp;
    }
    // 対称性よりかけ算すればよい
    sub *= C.Perm(m, n);
    ans -= sub;
    cout << ans << endl;
}