CodeChef June Challenge 2018: Expected Buildings
CodeChef June Challenge 2018の問題: Expected Buildings (Code: BUILDIT)
問題ページ: https://www.codechef.com/JUNE18A/problems/BUILDIT
問題概要
1つの円があり、円の中心にChefが立っている。
この円を周囲は個の区間に分割され、各区間に1, 2, ..., hと時計回りに番号が付けられている。そこに個の建物が存在し、番目の建物は区間内に含まれている。
また、円の中心に立っているChefの視界範囲はであり、円の周囲の連続した個の区間を一度に見ることができる。
今回、Chefが向く方向をランダムに決定する。
各についてが決められており、視界に(mod )が含まれる確率は()である。
ただし、がでかいため、は最初の個しか与えられず、については係数を用いて以下の式で計算できる。
ランダムな方向を向いた時のChefの視界の範囲に含まれる建物の数の期待値をmodulo 163577857で求めなさい。
制約
解法
累積和を高速に計算して解いた。
は大きい数だが、が小さいことを考えて、期待値の計算を
ではなく、
(ただし、とする)
で計算することを考える。
また、累積和を用いると、
期待値は で計算できることが分かる。
(ただし、とする)
あとはこの各を求めればよい。
の漸化式はの漸化式から計算でき、
という漸化式が導ける。
この漸化式は線形漸化式であるため、行列を用いた繰り返し二乗法が利用できる。
しかし、を計算するのにとなるため、今回の制約上間に合わない。
そこで、繰り返し二乗法よりも高速にを計算できるKitamasa法を用いる。
これにより、をで計算できる。
前まとめたKitamasa法メモっぽいの。
smijake3.hatenablog.com
実装
計算量は。
提出コード(PyPy2): https://www.codechef.com/viewsolution/18731995
MOD = 163577857 N = int(raw_input()) H = int(raw_input()) X = int(raw_input()) K = int(raw_input()) P = map(int, raw_input().split()) A = map(int, raw_input().split()) C = map(int, raw_input().split()) # 累積和: S_1, ..., S_K S = [0]*(K+1) for i in xrange(K): S[i+1] = S[i] + A[i] # 累積和の漸化式の係数 D = [0]*(K+1) D[0] = 1 for i in xrange(K): D[i] += C[i] D[i+1] -= C[i] D[i] %= MOD D[-1] %= MOD D = D[::-1] # C(n, *) -> C(n+1, *) を計算 def nxt(C): C1 = [0]*(K+1) C1[0] = C[K] * D[0] % MOD for i in xrange(1, K+1): C1[i] = (C[i-1] + C[K] * D[i]) % MOD return C1 # C(n, *) -> C(2n, *) を計算 def dbl(C): Ci = C[:] C1 = [0]*(K+1) for j in xrange(K+1): for i in xrange(K+1): C1[i] += C[j] * Ci[i] Ci = nxt(Ci) for i in xrange(K+1): C1[i] %= MOD return C1 # Kitamasa法でS_kを計算するための係数c_iを計算 def calc(k): bits = [] while k > K: bits.append(k & 1) k >>= 1 C = [0]*(K+1) C[k] = 1 for b in reversed(bits): C = dbl(C) if b: C = nxt(C) return C # S_kを計算 def get(k): C = calc(k) res = 0 for i in xrange(K+1): res += S[i] * C[i] return res % MOD # 累積和から期待値を計算 ans = 0 su = get(H) for p in P: if X <= p: ans += get(p) - get(p-X) else: ans += get(p) + (su - get(H - (X-p))) print(ans * pow(su, MOD-2, MOD) % MOD)