コンテンツにスキップ

SamCoding Round 9 (Div. 4) G - No Cheating

サイト
SamCoding
コンテスト
SamCoding Round 9 (Div. 4)
問題
G - No Cheating(常設版)

nn 個の椅子に kk 人の生徒を、どの 2 人も隣り合わないように座らせる方法の数を 109+710^9 + 7 で割った余りで求める問題です。どの椅子に人が座るかだけを区別します。クエリが qq 個あり、それぞれで次の 2 種類のどちらかが与えられます(1≤q≤1051 \le q \le 10^5、3≤n≤1063 \le n \le 10^6、0≤k≤n0 \le k \le n)。

  • t=1t = 1:椅子が 11 列に並んでいる。椅子 ii と隣り合うのは椅子 i−1,i+1i - 1, i + 1 だけ。
  • t=2t = 2:椅子が円形に並んでいる。上に加えて、椅子 11 と椅子 nn も隣り合う。

k=0k = 0 のときは 11 通り、k=1k = 1 のときはどちらの場合も nn 通りなので、以下では k≥2k \ge 2 とします。

空いている椅子 n−kn - k 個を先に並べると、その間と両端に n−k+1n - k + 1 個の隙間ができます。生徒が隣り合わないのは、生徒を異なる隙間に 1 人ずつ入れるときなので、答えは隙間から kk 個を選ぶ方法の数

(n−k+1k)\binom{n - k + 1}{k}

です。n−k+1<kn - k + 1 < k、つまり 2k−1>n2k - 1 > n のときは 00 です。

1 列の場合の数え方では、椅子 11 と椅子 nn の両方に座る並べ方も数えてしまっているので、それを引きます。

椅子 11 と椅子 nn の両方に座るとき、椅子 22 と椅子 n−1n - 1 は空いていなければなりません。残りの k−2k - 2 人は、椅子 33 から n−2n - 2 までの n−4n - 4 個の椅子に 1 列の場合と同じ条件で座るので、((n−4)−(k−2)+1k−2)=(n−k−1k−2)\binom{(n - 4) - (k - 2) + 1}{k - 2} = \binom{n - k - 1}{k - 2} 通りです。よって答えは

(n−k+1k)−(n−k−1k−2)\binom{n - k + 1}{k} - \binom{n - k - 1}{k - 2}

です。円形では kk 人の間に空いた椅子が kk 個以上必要なので、2k>n2k > n のときは 00 です。

二項係数は、10610^6 程度までの階乗とその逆元を前計算しておけば O(1)O(1) で求まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/combinatorics.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint1000000007;
using C = Combination<mint>;
void solve() {
LL(t, n, k);
if (k <= 1) {
if (k == 0)
print(1);
else
print(n);
return;
}
if (t == 1) {
if (k + k - 1 <= n) {
print(C::C(n - k + 1, k));
} else {
print(0);
}
} else {
if (2 * k <= n) {
print(C::C(n - k + 1, k) - C::C(n - k - 1, k - 2));
} else {
print(0);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(q);
rep(q)
solve();
}

Combination<mint> は階乗とその逆元の表を使って二項係数を求めるクラスで、C::C(n, r) が (nr)\binom{n}{r} です。

使用ライブラリ:cpp_include@4b58304