このセットの writer をしていました
問題概要
を並び替えてできる数列
は
通りあるが、そのうち以下の条件を満たすものが何通りあるかを、1000000007 で割ったあまりを求めよ。
を満たすような
がちょうど
個
を満たすような
個
を満たすような
個
制約
解法 (1)： 挿入 DP (O(N3))
まずは想定解法から。順列の数え上げは
「 の順列に対して、
を上手に追加することで
の順列を作る」
という考え方がよくとられる。たとえば「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)
このような操作を各「 の順列」に対して実施することで、
の順列」をすべて生成することができる。
これを踏まえて次のような DP をする。
=
の順列のうち、
個で、
個となる場合の数
このとき、遷移は次のように考えられる。
- 末尾に追加するとき：
は変化なし
(
箇所) を swap するとき：
それぞれ式に表すと次のようになる。
+=
+=
+=
+=
計算量は 。
#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 をする方法も代表的。
まず、 となる箇所は
箇所であることがわかっているので、それらをあらかじめ決め打つことにする。決め打つ方法は
通りある。
これをあとで掛けることにすると、次の問題に帰着される。
の順列
のうち、以下の条件を満たすものの個数を求めよ。
ここから先は、箱根駅伝 DP をする。
まず順列を「左側が 個」「右側が
個」という要素の並んだマッチングとみなすことにする。そして、「左側の
個」と「右側の
個」だけを考えた状態を考えて、次のように DP を定義する。
個の要素と、右側の
個の要素の間で、すでにマッチングが
本成立していて、そのうち左側から右側へと下がっている辺が
そうすると、DP 遷移は次のようになる。
+=
- 左側の頂点
も、右側の頂点
- 左側の頂点
+=
- 右側の頂点
- 右側の頂点
+=
- 左側の頂点
- 左側の頂点
+=
- 新たなマッチングを形成しない場合
この場合も計算量は となる。
解法 (3)：撹乱順列に対する漸化式の応用 (O(N2))
解法 (2) で考えた次の問題を考える。
の順列
のうち、以下の条件を満たすものの個数を求めよ。
この問題は「撹乱順列」の応用と言える。撹乱順列のうち、「= でないところ」の左右へのズレの個数まで指定したものを数え上げよ、というわけだ。でも撹乱順列の個数を求める漸化式解法はよく知られている。今回の問題にそれを応用できそうだ。
:=
の撹乱順列のうち、
個であるようなものの個数
とする。集める DP で考えることにする。そして、、
として、
の様相で場合分けする。
であるとき
このとき、 を除いた
個の順列の場合に帰着される。
の選び方が
通りあることから、次のようになる。
+=
であるとき
この場合は、以下の場合と一対一に対応することが示せる。
の順列のうち
と、
- その
具体的には、 個の順列において
を削除して代わりに
とすれば、上記の条件を満たす
個の順列に帰着される。逆も同様。よって、
+=
となる。
であるとき
この場合は、以下の場合と一対一に対応することが示せる。
箇所あるようなもの
- そうなっていない
箇所のうちから 1 つ
具体的には、 個の順列において
を削除して代わりに
とすれば、上記の条件を満たす
個の順列に帰着される。今回は、
であるにもかかわらず
であることから、
個の順列 (上記) と
個の順列とで、
を満たす
の個数が 1 ずれることに注意。逆も同様。よって、
+=
となる。
コード
以上の解法によって、計算量は に落ちる！！！
#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))
撹乱順列の数え上げには、漸化式を用いる解法とともに、包除原理を適用する解法もある。とすれば今回の問題にもそのような解法もありそうだ。
アルメリアさんの記事に詳しい解説がある！
