後ろから見たらわかった
問題概要
の順列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。
- 任意の 以下の奇数 に対して、 のメディアンは である
制約
考えたこと
簡単のため、 を奇数として考えてみる。このとき、まず最後尾の値が一意に決まってしまうことに注意しよう。
たとえば であったならば、最後の要素はかならず 3 になる。よって残りの を並び替える問題になる。ここで注意したいことは、
- 最後から 2 番目の要素としてどれを選んだとしても、残りの 3 つの数の並べる場合の数は変わらない
ということだ。よって、最後から 2 番目の要素は 4 通りの場合が考えられる。このとき残りの 3 つの要素について、同様に最後尾の値が決まることになる。
...これを繰り返すと結局
- 最後から 2 番目を選ぶ方法:4 通り
- 最後から 4 番目を選ぶ方法:2 通り
となって、答えは 8 通りとなる。一般に が奇数のときは
- 通り
となることがわかった。 が偶数のときも、考え方はほとんど同様だ。結局、最後尾にどれを選んでも、残りを条件を満たすように並べる場合の数は等しいので、
となる。
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; int main() { long long N; cin >> N; long long res = 1; if (N % 2 == 0) res = N, --N; for (long long n = N-1; n >= 1; n -= 2) res = (res * n) % MOD; cout << res << endl; }