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

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

フォルシアゆるふわ競プロオンサイト #3 B - Median Permutation locked

後ろから見たらわかった

問題へのリンク

問題概要

 1, 2, \dots, N の順列  p_{1}, \dots, p_{N} であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。

  • 任意の  N 以下の奇数  i に対して、 p_{1}, \dots, p_{i} のメディアンは  p_{i} である

制約

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

考えたこと

簡単のため、 N を奇数として考えてみる。このとき、まず最後尾の値が一意に決まってしまうことに注意しよう。

たとえば  N = 5 であったならば、最後の要素はかならず 3 になる。よって残りの  1, 2, 4, 5 を並び替える問題になる。ここで注意したいことは、

  • 最後から 2 番目の要素としてどれを選んだとしても、残りの 3 つの数の並べる場合の数は変わらない

ということだ。よって、最後から 2 番目の要素は 4 通りの場合が考えられる。このとき残りの 3 つの要素について、同様に最後尾の値が決まることになる。

...これを繰り返すと結局

  • 最後から 2 番目を選ぶ方法:4 通り
  • 最後から 4 番目を選ぶ方法:2 通り

となって、答えは 8 通りとなる。一般に  N が奇数のときは

  •  (N-1)(N-3) \dots 通り

となることがわかった。 N が偶数のときも、考え方はほとんど同様だ。結局、最後尾にどれを選んでも、残りを条件を満たすように並べる場合の数は等しいので、

  •  N \times (N-1 のときの場合の数)

となる。

#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;
}