SamCoding Round 9 (Div. 4) G - No Cheating
- サイト
- SamCoding
- コンテスト
- SamCoding Round 9 (Div. 4)
- 問題
- G - No Cheating(常設版)
個の椅子に 人の生徒を、どの 2 人も隣り合わないように座らせる方法の数を で割った余りで求める問題です。どの椅子に人が座るかだけを区別します。クエリが 個あり、それぞれで次の 2 種類のどちらかが与えられます(、、)。
- :椅子が 列に並んでいる。椅子 と隣り合うのは椅子 だけ。
- :椅子が円形に並んでいる。上に加えて、椅子 と椅子 も隣り合う。
のときは 通り、 のときはどちらの場合も 通りなので、以下では とします。
1 列の場合
Section titled “1 列の場合”空いている椅子 個を先に並べると、その間と両端に 個の隙間ができます。生徒が隣り合わないのは、生徒を異なる隙間に 1 人ずつ入れるときなので、答えは隙間から 個を選ぶ方法の数
です。、つまり のときは です。
1 列の場合の数え方では、椅子 と椅子 の両方に座る並べ方も数えてしまっているので、それを引きます。
椅子 と椅子 の両方に座るとき、椅子 と椅子 は空いていなければなりません。残りの 人は、椅子 から までの 個の椅子に 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) が です。
使用ライブラリ:cpp_include@4b58304