けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CPSCO2019 Session3 F - Flexible Permutation (600 点設定)

このセットの writer をしていました

問題概要

 1, 2, \dots, N を並び替えてできる数列  P_{1}, P_{2}, \dots, P_{N} N! 通りあるが、そのうち以下の条件を満たすものが何通りあるかを、1000000007 で割ったあまりを求めよ。

  •  P_{i} \gt i を満たすような  i がちょうど  A
  •  P_{i} \lt i を満たすような  i がちょうど  B
  •  P_{i} = i を満たすような  i がちょうど  N - A - B

制約

  •  1 \le N \le 300

 

解法 (1): 挿入 DP (O(N3))

まずは想定解法から。順列の数え上げは

 1, 2, \dots, i の順列に対して、 i+1 を上手に追加することで  1, 2, \dots, i+1 の順列を作る」

という考え方がよくとられる。たとえば「3, 2, 5, 4, 1」という順列に 6 を加えるとき、以下のように 6 通りの方法がある。

  • 3, 2, 5, 4, 1, 6 (末尾に追加)
  • 6, 2, 5, 4, 1, 3 (1 番目の要素と swap)
  • 3, 6, 5, 4, 1, 2 (2 番目の要素と swap)
  • 3, 2, 6, 4, 1, 5 (3 番目の要素と swap)
  • 3, 2, 5, 6, 1, 4 (4 番目の要素と swap)
  • 3, 2, 5, 4, 6, 1 (5 番目の要素と swap)

このような操作を各「 1, 2, \dots, i の順列」に対して実施することで、 1, 2, \dots, i+1 の順列」をすべて生成することができる。

これを踏まえて次のような DP をする。

  •  {\rm dp} \lbrack i \rbrack \lbrack a \rbrack \lbrack b \rbrack =  1, 2, \dots, i の順列のうち、 P_{i} \gt i を満たすものが  a 個で、 P_{i} \lt i を満たすものが  b 個となる場合の数

このとき、遷移は次のように考えられる。

  • 末尾に追加するとき: a, b は変化なし
  •  P_{i} \gt i を満たす  P_{i} ( a 箇所) と swap するとき: b が増加
  •  P_{i} \lt i を満たす  P_{i} ( b 箇所) と swap するとき: a が増加
  •  P_{i} = i を満たす  P_{i} ( i - a - b 箇所) を swap するとき: a, b がともに増加

それぞれ式に表すと次のようになる。

 {\rm dp}\lbrack i+1 \rbrack \lbrack a \rbrack \lbrack b \rbrack +=  {\rm dp} \lbrack i \rbrack \lbrack a \rbrack \lbrack b \rbrack
 {\rm dp} \lbrack i+1 \rbrack \lbrack a \rbrack \lbrack b+1 \rbrack +=  {\rm dp} \lbrack i \rbrack \lbrack a \rbrack \lbrack b \rbrack \times a
 {\rm dp} \lbrack i+1 \rbrack \lbrack a+1 \rbrack \lbrack b \rbrack +=  {\rm dp} \lbrack i \rbrack \lbrack a \rbrack \lbrack b \rbrack \times b
 {\rm dp} \lbrack i+1 \rbrack \lbrack a+1 \rbrack \lbrack b+1 \rbrack +=  {\rm dp} \lbrack i \rbrack \lbrack a \rbrack \lbrack b \rbrack \times (i-a-b)

計算量は  O(N^{3})

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
using namespace std;

const int MOD = 1000000007;
const int MAX = 310;
long long dp[MAX][MAX][MAX];

void add(long long &a, long long b, long long c) {
    a += b * c % MOD;
    a %= MOD;
}

long long solve(long long N, long long A, long long B) {
    memset(dp, 0, sizeof(dp)); // (1...n) の並び替えのうち、a 個が P_i > i で b 個が P_i < i なもの
    dp[0][0][0] = 1;
    for (int n = 0; n <= N; ++n) {
        for (int a = 0; a <= n; ++a) {
            for (int b = 0; a + b <= n; ++b) {
                // i+1 を i+1 番目に
                add(dp[n+1][a][b], dp[n][a][b], 1);
                
                // i+1 を a 族と swap
                add(dp[n+1][a][b+1], dp[n][a][b], a);
                
                // i+1 を b 族と swap
                add(dp[n+1][a+1][b], dp[n][a][b], b);
                
                // i+1 を c 族と swap
                add(dp[n+1][a+1][b+1], dp[n][a][b], n - a - b);
            }
        }
    }
    return dp[N][A][B];
}

int main() {
    long long N, A, B;
    cin >> N >> A >> B;
    cout << solve(N, A, B) << endl;
}

 

解法 (2):箱根駅伝 DP (O(N3))

順列の数え上げといえば、箱根駅伝のような DP をする方法も代表的。

まず、 P_{i} = i となる箇所は  N - A - B 箇所であることがわかっているので、それらをあらかじめ決め打つことにする。決め打つ方法は  {}_{N}{\rm C}_{N-A-B} 通りある。

これをあとで掛けることにすると、次の問題に帰着される。


 1, 2, \dots, A+B の順列  P のうち、以下の条件を満たすものの個数を求めよ。

  •  P_{i} \gt i を満たす  i A
  •  P_{i} \lt i を満たす  i B

ここから先は、箱根駅伝 DP をする。

drken1215.hatenablog.com

まず順列を「左側が  N 個」「右側が  N 個」という要素の並んだマッチングとみなすことにする。そして、「左側の  n 個」と「右側の  n 個」だけを考えた状態を考えて、次のように DP を定義する。

  •  {\rm dp}\lbrack n \rbrack \lbrack a \rbrack \lbrack b \rbrack := 左側の [tex: n 個の要素と、右側の  n 個の要素の間で、すでにマッチングが  a+b 本成立していて、そのうち左側から右側へと下がっている辺が  a 本あり、左側から右側へと上がっている辺が  b 本あるような場合の数

そうすると、DP 遷移は次のようになる。

  •  {\rm dp}\lbrack n+1 \rbrack \lbrack a+1 \rbrack \lbrack b+1 \rbrack +=  {\rm dp}\lbrack n \rbrack \lbrack a \rbrack \lbrack b \rbrack \times (n-a-b)^{2}
    • 左側の頂点  n+1 も、右側の頂点  n+1 も、自分より上側の頂点とマッチングする場合)
  •  {\rm dp}\lbrack n+1 \rbrack \lbrack a+1 \rbrack \lbrack b \rbrack +=  {\rm dp}\lbrack n \rbrack \lbrack a \rbrack \lbrack b \rbrack \times (n-a-b)
    • 右側の頂点  n+1 のみが、自分より上側の左側頂点とマッチングする場合
  •  {\rm dp}\lbrack n+1 \rbrack \lbrack a \rbrack \lbrack b+1 \rbrack +=  {\rm dp}\lbrack n \rbrack \lbrack a \rbrack \lbrack b \rbrack \times (n-a-b)
    • 左側の頂点  n+1 のみが、自分より上側の右側頂点とマッチングする場合
  •  {\rm dp}\lbrack n+1 \rbrack \lbrack a \rbrack \lbrack b \rbrack +=  {\rm dp}\lbrack n \rbrack \lbrack a \rbrack \lbrack b \rbrack \times (n-a-b)
    • 新たなマッチングを形成しない場合

この場合も計算量は  O(N^{3}) となる。

 

解法 (3):撹乱順列に対する漸化式の応用 (O(N2))

解法 (2) で考えた次の問題を考える。


 1, 2, \dots, A+B の順列  P のうち、以下の条件を満たすものの個数を求めよ。

  •  P_{i} \gt i を満たす  i A
  •  P_{i} \lt i を満たす  i B

この問題は「撹乱順列」の応用と言える。撹乱順列のうち、「= でないところ」の左右へのズレの個数まで指定したものを数え上げよ、というわけだ。でも撹乱順列の個数を求める漸化式解法はよく知られている。今回の問題にそれを応用できそうだ。

mathtrain.jp

  •  {\rm dp}\lbrack n \rbrack \lbrack r \rbrack :=  1, 2, \dots, n の撹乱順列のうち、 P_{i} \gt i を満たす  i r 個であるようなものの個数

とする。集める DP で考えることにする。そして、 P_{a} = N P_{N} = b として、 a, b の様相で場合分けする。

 
 a = b であるとき
このとき、 a, n を除いた  n-2 個の順列の場合に帰着される。 a の選び方が  n-1 通りあることから、次のようになる。

 {\rm dp}\lbrack n \rbrack \lbrack r \rbrack +=  {\rm dp}\lbrack n-2 \rbrack \lbrack r-1 \rbrack \times (n-1)

 
 a \lt b であるとき
この場合は、以下の場合と一対一に対応することが示せる。

  •  1, 2, \dots, n-1 の順列のうち
  •  P_{i} \lt i となる箇所が  r 箇所あるようなもの  P' と、
  • その  r 箇所のうちから 1 つ  i を選ぶ方法のペア  (P', i)

具体的には、 n 個の順列において  n を削除して代わりに  P_{a} = b とすれば、上記の条件を満たす  n-1 個の順列に帰着される。逆も同様。よって、

 {\rm dp}\lbrack n \rbrack \lbrack r \rbrack +=  {\rm dp}\lbrack n-1 \rbrack \lbrack r \rbrack \times r

となる。

 
 a \gt b であるとき
この場合は、以下の場合と一対一に対応することが示せる。

  •  1, 2, \dots, n-1 の順列のうち
  •  P_{i} \lt i となる箇所が  r-1 箇所あるようなもの  P' と、
  • そうなっていない  n-r 箇所のうちから 1 つ  i を選ぶ方法のペア  (P', i)

具体的には、 n 個の順列において  n を削除して代わりに  P_{a} = b とすれば、上記の条件を満たす  n-1 個の順列に帰着される。今回は、 a \gt b であるにもかかわらず  a \lt N であることから、 n-1 個の順列 (上記) と  n 個の順列とで、 P_{i} \gt i を満たす  i の個数が 1 ずれることに注意。逆も同様。よって、

 {\rm dp}\lbrack n \rbrack \lbrack r \rbrack +=  {\rm dp}\lbrack n-1 \rbrack \lbrack r-1 \rbrack \times (n-r)

となる。

コード

以上の解法によって、計算量は  O(N^{2}) に落ちる!!!

#include <bits/stdc++.h>
using namespace std;

// modint
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {
        if (n == 0) return 1;
        if (n < 0) return modpow(modinv(r), -n);
        auto t = modpow(r, n / 2);
        t = t * t;
        if (n & 1) t = t * r;
        return t;
    }
    friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};

const int MOD = 1000000007;
//const int MOD = 998244353;
using mint = Fp<MOD>;

// Binomial coefficient
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    BiCoef<mint> bc(N+1);
    vector<vector<mint>> dp(A+B+1, vector<mint>(A+B+1, 0));
    dp[0][0] = 1;
    for (int n = 1; n <= A+B; ++n) {
        for (int r = 0; r <= A+B; ++r) {
            if (n >= 2 && r >= 1) dp[n][r] += dp[n-2][r-1] * (n-1);
            dp[n][r] += dp[n-1][r] * r;
            if (r >= 1) dp[n][r] += dp[n-1][r-1] * (n-r);
        }
    }
    cout << dp[A+B][A] * bc.com(N, N-A-B) << endl;
}

 

解法 (4):撹乱順列に対する包除原理の応用 (O(N2))

撹乱順列の数え上げには、漸化式を用いる解法とともに、包除原理を適用する解法もある。とすれば今回の問題にもそのような解法もありそうだ。

アルメリアさんの記事に詳しい解説がある!

betrue12.hateblo.jp