コンテンツにスキップ

組合せ

タグ「組合せ」の記事 2 件

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

SamCoding Round 7 (Div. 2) D - Perfect Number

各桁の和が 1010 になる正の整数を「完全数」と呼びます(19,28,37,…19, 28, 37, \ldots)。小さい方から kk 番目の完全数を求める問題です(1≤k≤1051 \le k \le 10^5)。

完全数を小さい順にすべて列挙し、kk 番目を出力します。

m=r+1m = r + 1 桁の完全数は、1010 個の玉と rr 本の仕切りを一列に並べたものと対応させられます。仕切りで区切られた r+1r + 1 個の区間に入っている玉の個数を、上の桁から順に並べたものが各桁の数字です。

たとえば r=2r = 2 で、1212 マスの列のうち位置 3,73, 7(00 始まり)に仕切りを置くと、各区間の玉の個数は 3,3,43, 3, 4 なので 334334 を表します。

ただし、次の 2 つに注意します。

  • 最上位の桁は 11 以上: 位置 00 に仕切りを置かなければよいので、仕切りの位置は 1,…,9+r1, \ldots, 9 + r から選びます。
  • 各桁は 99 以下: 区間に玉が 1010 個入る並べ方は数字として不正なので除きます。

桁数が少ないほど小さいので、r=1,2,…r = 1, 2, \ldots の順に列挙します。桁数が同じなら、仕切りの位置を辞書順に並べたものが数の小さい順と一致します。仕切りの位置が前にあるほど、上の桁が小さくなるからです。

r+1r + 1 桁の完全数は (9+rr)−1\binom{9 + r}{r} - 1 個あり、1111 桁(r=10r = 10)までで 184745184745 個になります。10510^5 個を超えるので、r≤10r \le 10 まで列挙すれば十分です。

Python
from itertools import combinations
ans = []
for r in range(1, 11):
for c in combinations(range(1, 10 + r), r=r):
t = 0
l = []
for x in c:
l.append(x - t)
t = x + 1
l.append(10 + r - t)
if 10 in l:
continue
ans.append(int("".join(map(str, l))))
K = int(input())
print(ans[K - 1])

combinations で仕切りの位置 c を辞書順に列挙しています。t は直前の仕切りの次の位置で、x - t が仕切りの間にある玉の個数、つまりその桁の数字です。最後の区間は列の長さ 10 + r までの玉の個数です。

桁に 10 があるものを除き、残りを数にして ans に入れていきます。