This page looks best with JavaScript enabled

ABC172 E - NEQ

 ·   ·  ☕ 4 min read  ·  ✍️ reud · 👀... views

激ムズだった。

E - NEQ

これむずい。

何がむずいってこれを解く人は包除原理っていうけどこれの挑戦レベルは包除原理を利用して〜のとこまで考察いかなくない・・・?

内容は

条件を満たす数列A.Bの組み合わせの数を求めよというもの。

条件は2つ

①: 1 <= i <= N なる 任意のiについて $A_i \neq B_i$
②: 1 <= i < j <= N なる任意の(i,j)について $A_i \neq B_j$ かつ $A_i \neq B_j$

ここで②の条件に着目すると、ここは

②: $i \neq j$なら $A_i \neq A_j$かつ$B_i \neq B_j$

と読める。

すなわち、数列A(かつB)において、数列内の要素が同数列内の要素が重複することは無い。

この事を念頭に置けばこれから考える数列は全て条件②は達成できる。(よって考慮しなくてよくなる。)

後は条件①を満たす数列について考える。

そのままでは難しそうなので裏を取ってみると、

1 <= i <= N なる どれかしらのiについて、一個以上 $A_i = B_i$

と読める。

↑の場合の数は①の余事象となるので↑さえ求めることが出来れば、全体の場合の数から引けば答えとなる。

1 <= i <= N なる iについて、s個 $A_i = B_i$

①の余事象をZと呼びます。

このように言い換えてみる
f(s) = <1 <= i <= N なる iについて、s個以上 $A_i = B_i$ となる場合の数列(A,B)の集合>

そうすると $Z = |f(1) \cup f(2) \cup f(3) \cup … \cup f(N)|$

と言える。

さらにn個以上と書いてあるので積集合にも強い。任意の$ i < j$において $f(i) \cap f(j) = f(j)$が成立する。・・・➂(これ結構感動したのにあまり語られていない)

で、$|f(1) \cup f(2) \cup f(3) \cup … \cup f(N)|$これを求めるのに包除原理を利用する。(やっと出てきた。。。)

包除原理の2通りの証明 | 高校数学の美しい物語

読んだほうが早い。

➂を考慮すると包除原理により

$$
Z = |f(0)| - |f(1)| + |f(2)| - …
$$

と書ける!

後はf(s)をちゃんと式に直すと、

$$f(s) = {}_NC_s * {}_MP_s * ({}_M-sP_N-s)$$

(うまくmathjaxが仕事しなかった。。。)

となります。

これでf(s)が求められました。

後は求めるだけ!やったねたえちゃん!やっとコーディング出来るよ!

コンビネーションライブラリを持っておくと良いぞ!

➂のルールのおかげで複数AND条件ある時はf(x)のxが一番大きいものだけ考慮すれば良いのでかなり見通しがよくなった。

提出 #14834104 - AtCoder Beginner Contest 172

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

const int mod = 1e9+7;

template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

long long combination(int n, int k){
    static const int maxi = 1e6+1;
    static vector<ll> fac(maxi,0),finv(maxi,0),inv(maxi,0);
    static const int mod = 1e9+7;
    // キャッシュされてない場合
    if (fac[0]==0) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < maxi; i++){
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = mod - inv[mod%i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

long long permutation(int n, int k) {
    static const int maxi = 1e6+1;
    static vector<ll> fac(maxi,0),finv(maxi,0),inv(maxi,0);
    static const int mod = 1e9+7;
    // キャッシュされてない場合
    if (fac[0]==0) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < maxi; i++){
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = mod - inv[mod%i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[n - k] % mod;
}

void solve() {
    int N,M;
    cin >> N >> M;
    ModInt<mod> ans(permutation(M,N));
    ans *= ans;
    FOR(i,1,N+1) {
        ModInt<mod> c(combination(N,i)),p1(permutation(M,i)),p2(permutation(M-i,N-i));
        if(i%2 == 0) ans += (c * p1 * p2 * p2);
        else  ans -= (c * p1 * p2 * p2);
    }

    cout << (ans).x << endl;

}

int main() {
    solve();
    return 0;
}

Share on

reud
WRITTEN BY
reud
Stundent