−目次
AtCoder Beginner Contest 156 D,E,F問題メモ
コンテスト前にペヤング獄激辛を食べて臨んではいけないということを今日学びました。
D - Bouquet
問題
- N 本の異なる種類の花から1本以上を選んで花束を作る
- ただし、全体が a 本または b 本の花束を作ってはいけない
- 花束の作り方の通り数を mod109+7 で求めよ
- 2≤N≤109
- 1≤a,b≤2×105
解法
a,b 本を作ってはいけない制約を気にしないで考えると、N 本の各花を使うか使わないかなので、1本も使わない1ケースを除いて 2N−1 通り。
使う花が a 本と決まっている場合は、N 本から a 本の選び方は NCa 通り。
よって、2N−1−NCa−NCb が答え。
で、組み合わせの計算はmod上での逆数を事前計算してやれば、N!×a!−1×(N−a)!−1 でできる。楽勝♪
……制約を見ると、N≤109 なので、N! が時間内に計算できないですね。
ただ、それにもかかわらず a,b≤2×105 の謎の上限があるので、ここがポイントっぽい。
NCa=N!a!(N−a)!=N(N−1)(N−2)...(N−a+1)a! なので、こうすれば分子も分母も O(a) で求められる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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 回の移動後の各部屋にいる人数としてあり得る組み合わせの数を、mod109+7 で求めよ
- 3≤N≤2×105
- 2≤K≤109
解法
具体的な移動でなく、移動後にあり得る部屋の状態を考える。
まず、部屋 x→y と y→z という2回の移動は、最終的には x→z という1回の移動と変わらない。
逆に言うと、x→z という移動は、x→?→?→...→z といくらでも水増しできるので、k(k≤K)回の移動で達成できる組み合わせは、K 回でも達成できる。
いずれかの移動で移動先(x→y の y)となった部屋は、他の移動で移動元(x)になるのは無駄なので、そういう移動が発生しないような k 回の移動を考える。
すると、1回移動元となった部屋にはもう人がいなくなり新たに入ることも無いので、移動元となる部屋は全て別々の k 個の部屋である。
k 個の部屋の選び方が NCk 、移動先の選び方が N−kHk なので、これを掛け合わせた数が k 回の移動の通り数。
後は、k を 0~K まで動かして総和を取ればよい。
ただし、K≥N−1 の場合は、このような場合分けせずとも十分な回数シャッフルされるので、NHN で求められる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
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 の数列 {d0,d1,...,dK−1} を無限に繰り返した数列 D がある
- 以下の Q 個のクエリに答えよ
- i 個目のクエリは Ni,Xi,Mi の3つの整数によって表される
- まず、長さ Ni の数列 A を作る
- 初項は a0=Xi
- ai=ai−1+di−1 (i≥1)
- 全ての項を Mi で割った余りに置き換え、A′ とする
- A′i<A′i+1 となっている箇所の数を出力する
- 1≤K,Q≤5000
- 0≤di,Xi≤109
- 2≤Ni,Mi≤109
解法
制約的に1クエリ O(K) だよね、ということを念頭に考察を進める。
作るべき数列 A は、D の累積和を取って、先頭に0を追加し、長さ Ni に切り取って、各項に Xi を加えた数に等しい。
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個
クエリを表す変数 Ni,Xi,Mi=n,x,m とする。
問われているのは A′ が前の項より増えているかだが、 基本的には A が(広義)単調増加のためそれに従うものの、 m で割った余りなので、A を順に見ていって m の倍数を超えた箇所で減る可能性がある。 ただ必ず減るわけでは無く、di と m の関係性によるので一概には言えない。
ここで、di および x をあらかじめ modm で置き換えても、できる 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>B′i+1 となる箇所は、B′ の末尾の項を m で割った商(切り捨て)の数だけ存在することになる。
全体 n−1 からそれを引けば、B′i≤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'が前の項と同じ箇所
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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))) |