AtCoder Beginner Contest 156 D,E,F問題メモ
コンテスト前にペヤング獄激辛を食べて臨んではいけないということを今日学びました。
D - Bouquet
問題
- $N$ 本の異なる種類の花から1本以上を選んで花束を作る
- ただし、全体が $a$ 本または $b$ 本の花束を作ってはいけない
- 花束の作り方の通り数を $\mod 10^9+7$ で求めよ
- $2 \le N \le 10^9$
- $1 \le a,b \le 2 \times 10^5$
解法
$a,b$ 本を作ってはいけない制約を気にしないで考えると、$N$ 本の各花を使うか使わないかなので、1本も使わない1ケースを除いて $2^N-1$ 通り。
使う花が $a$ 本と決まっている場合は、$N$ 本から $a$ 本の選び方は ${}_NC_a$ 通り。
よって、$2^N-1-{}_NC_a-{}_NC_b$ が答え。
で、組み合わせの計算はmod上での逆数を事前計算してやれば、$N! \times a!^{-1} \times (N-a)!^{-1}$ でできる。楽勝♪
……制約を見ると、$N \le 10^9$ なので、$N!$ が時間内に計算できないですね。
ただ、それにもかかわらず $a,b \le 2 \times 10^5$ の謎の上限があるので、ここがポイントっぽい。
${}_NC_a = \dfrac{N!}{a!(N-a)!} = \dfrac{N(N-1)(N-2)...(N-a+1)}{a!}$ なので、こうすれば分子も分母も $O(a)$ で求められる。
def prepare(n, MOD):
# n! の計算
f = 1
for m in range(1, n + 1):
f *= m
f %= MOD
fn = f
# n!^-1 の計算
inv = pow(f, MOD - 2, MOD)
# n!^-1 - 1!^-1 の計算
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return fn, invs
def ncr(n, r, invs, MOD):
ret = invs[r]
for i in range(n, n - r, -1):
ret = ret * i % MOD
return ret
n, a, b = list(map(int, input().split()))
MOD = 10 ** 9 + 7
fn, invs = prepare(max(a, b), MOD)
ans = pow(2, n, MOD)
ans = (ans - ncr(n, a, invs, MOD) - ncr(n, b, invs, MOD) - 1) % MOD
print(ans)
E - Roaming
問題
- $N$ 個の部屋があり、各部屋同士は好きに行き来できる
- ある1人が部屋から別の部屋に移動することを、「1回の移動」とする
- はじめ、各部屋に1人ずついる
- $K$ 回の移動後の各部屋にいる人数としてあり得る組み合わせの数を、$\mod{10^9+7}$ で求めよ
- $3 \le N \le 2 \times 10^5$
- $2 \le K \le 10^9$
解法
具体的な移動でなく、移動後にあり得る部屋の状態を考える。
まず、部屋 $x→y$ と $y→z$ という2回の移動は、最終的には $x→z$ という1回の移動と変わらない。
逆に言うと、$x→z$ という移動は、$x→?→?→...→z$ といくらでも水増しできるので、$k$（$k \le K$）回の移動で達成できる組み合わせは、$K$ 回でも達成できる。
いずれかの移動で移動先（$x→y$ の $y$）となった部屋は、他の移動で移動元（$x$）になるのは無駄なので、そういう移動が発生しないような $k$ 回の移動を考える。
すると、1回移動元となった部屋にはもう人がいなくなり新たに入ることも無いので、移動元となる部屋は全て別々の $k$ 個の部屋である。
$k$ 個の部屋の選び方が ${}_NC_k$ 、移動先の選び方が ${}_{N-k}H_k$ なので、これを掛け合わせた数が $k$ 回の移動の通り数。
後は、$k$ を $0～K$ まで動かして総和を取ればよい。
ただし、$K \ge N-1$ の場合は、このような場合分けせずとも十分な回数シャッフルされるので、${}_NH_N$ で求められる。
def prepare(n, MOD):
# 1! - n! の計算
f = 1
factorials = [1] # 0!の分
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
# n!^-1 の計算
inv = pow(f, MOD - 2, MOD)
# n!^-1 - 1!^-1 の計算
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
def solve(n, k):
MOD = 10 ** 9 + 7
facts, invs = prepare(2 * n, MOD)
if k >= n - 1:
return facts[2 * n - 1] * invs[n - 1] * invs[n] % MOD
ans = 0
for z in range(k + 1):
tmp = facts[n] * invs[z] * invs[n - z] % MOD
tmp = tmp * facts[n - 1] * invs[z] * invs[n - z - 1] % MOD
ans = (ans + tmp) % MOD
return ans
n, k = list(map(int, input().split()))
print(solve(n, k))
F - Modularness
問題
- 長さ $K$ の数列 $\{d_0,d_1,...,d_{K-1}\}$ を無限に繰り返した数列 $D$ がある
- 以下の $Q$ 個のクエリに答えよ
- $i$ 個目のクエリは $N_i,X_i,M_i$ の3つの整数によって表される
- まず、長さ $N_i$ の数列 $A$ を作る
- 初項は $a_0=X_i$
- $a_i = a_{i-1}+d_{i-1}$ （$i \ge 1$）
- 全ての項を $M_i$ で割った余りに置き換え、$A'$ とする
- $A'_i \lt A'_{i+1}$ となっている箇所の数を出力する
- $1 \le K, Q \le 5000$
- $0 \le d_i,X_i \le 10^9$
- $2 \le N_i,M_i \le 10^9$
解法
制約的に1クエリ $O(K)$ だよね、ということを念頭に考察を進める。
作るべき数列 $A$ は、$D$ の累積和を取って、先頭に0を追加し、長さ $N_i$ に切り取って、各項に $X_i$ を加えた数に等しい。
D 3 1 4 ( 3 1 4 3 1 4 ...) 累積和 0 3 4 8 (11 12 16 19 20 24 ...) n, x, m = 8, 3, 3 累積和 0 3 4 8 11 12 16 19 + x v v v v v v v v A 3 6 7 11 14 15 19 22 % m A' 0 0 1 2 2 0 1 1 増加 x o o x x o x → 3個
クエリを表す変数 $N_i,X_i,M_i=n,x,m$ とする。
問われているのは $A'$ が前の項より増えているかだが、 基本的には $A$ が（広義）単調増加のためそれに従うものの、 $m$ で割った余りなので、$A$ を順に見ていって $m$ の倍数を超えた箇所で減る可能性がある。 ただ必ず減るわけでは無く、$d_i$ と $m$ の関係性によるので一概には言えない。
ここで、$d_i$ および $x$ をあらかじめ $\mod m$ で置き換えても、できる $A'$ は変わらない。（元と比較して $A$ に足されなくなる数は全て $m$ の倍数のため）
このように作った数列 $D,A,A'$ に対応する数列を、それぞれ $E,B,B'$ とする。
n, x, m = 8, 3, 3 D 3 1 4 3 1 4 3 1 4 ... E 0 1 1 0 1 1 0 1 1 ... ※D mod m 累積和 0 0 1 2 2 3 4 4 + x%m v v v v v v v v B 0 0 1 2 2 3 4 4 % m B' 0 0 1 2 2 0 1 1 A'と一致＝クエリとしての答えも一致
こうしておくと、各隣接項の差は必ず $m$ 未満なので、$B$ が $m$ の倍数を超過した箇所で商はかならず1だけ増加して、余りはかならず減少する。
m = 3 超過 B 0 0 1 2 2 → 3 4 4 B//m 0 0 0 0 0 1 1 1 1増加 B' 0 0 1 2 2 0 1 1 減少
よって、$B'_i \gt B'_{i+1}$ となる箇所は、$B'$ の末尾の項を $m$ で割った商（切り捨て）の数だけ存在することになる。
全体 $n-1$ からそれを引けば、$B'_i \le B'_{i+1}$ となっている箇所の個数が求まる。
しかし、求めるのは真に大きい場合なので、$B'_i = B'_{i+1}$ となっているものがまだ残っている。
これは、$E$ に0が含まれている箇所がそのようになるので、$n-1$ からその個数を引けばよい。
E 0 1 1 0 1 1 0 1 1 ...
* * * E=0の箇所
累積和 0 0 1 2 2 3 4 4
+ x%m v v v v v v v v ↑
B 0 0 1 2 2 3 4 4 一致
% m ↓
B' 0 0 1 2 2 0 1 1
* * * B'が前の項と同じ箇所
import sys
from itertools import accumulate
def solve(n, x, m):
eee = [d % m for d in ddd]
acc = list(accumulate(eee))
zero = [int(e == 0) for e in eee]
zero_acc = list(accumulate(zero))
loop, rem = divmod(n - 1, k)
tot = x % m + acc[-1] * loop
tot_zero = zero_acc[-1] * loop
if rem > 0:
tot += acc[rem - 1]
tot_zero += zero_acc[rem - 1]
dame = tot // m
return n - 1 - dame - tot_zero
k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
n, x, m = map(int, line.split())
buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))
