素直にやるなら $k \times (k回で勝負が決する確率)$ の合計で表せる。
しかし、勝負をして必ずどちらかが勝つならいいが、引き分けという結果があるせいで理論上は無限回でも勝負ができてしまうため、上記では上手くいかない。
そんな時、一度引き分けは設定に無いものと考えて、こう考えることができる。
勝者をAと仮定する。Bも同様に計算すればよい。
Bの勝利数をkとすると、$0 \le k \le N-1$ である。$N-1+k$ 回までにAが $N-1$ 勝、Bが$k$ 勝した後、$N+k$ 回目にAが勝ち、ゲームが終わる。
よって確率は、${}_{N+k-1}C_{k}(\frac{A}{A+B})^{N-1}(\frac{B}{A+B})^k \times \frac{A}{A+B}$
期待値はこれに $N+k$ をかけたものである。
これを $k=0..N-1$ まで計算すればよい。
def prepare(n, MOD):
facts = [1]
t = 1
for i in range(1, n + 1):
t = t * i % MOD
facts.append(t)
invs = [1] * (n + 1)
t = pow(t, MOD - 2, MOD)
invs[n] = t
for i in range(n, 1, -1):
t = t * i % MOD
invs[i - 1] = t
return facts, invs
n, a, b, c = list(map(int, input().split()))
MOD = 10 ** 9 + 7
facts, invs = prepare(2 * n, MOD)
inv_ab = pow(a + b, MOD - 2, MOD)
a_ab = a * inv_ab % MOD
b_ab = b * inv_ab % MOD
win_a = 0
win_b = 0
exp_a = 1
exp_b = 1
for k in range(n):
coef = facts[n + k] * invs[k] * invs[n - 1] % MOD
win_a = (win_a + coef * exp_b) % MOD
win_b = (win_b + coef * exp_a) % MOD
exp_a = exp_a * a_ab % MOD
exp_b = exp_b * b_ab % MOD
win_a = win_a * exp_a % MOD
win_b = win_b * exp_b % MOD
print((win_a + win_b) * 100 * inv_ab % MOD)
なるべく大きいスコアをたくさんの辺に与えたい。$c_i$ の中で小さい整数をどう処理するかが鍵となる。
$c_i$ の中で一番小さな整数をある頂点に書き込むと、それに接続する辺のスコアは必ずその値となる。 次数の大きな頂点に書き込むと非効率だが、どこに書こうと最低1箇所はその最小値のスコアの辺はできてしまう。
1つの辺にしか接続していない葉頂点に一番小さな整数を書き込むようにすると、最小値となる辺数を1本と最低限にできる。
その辺のもう一方の端点は何でもよいため、一度最小値を書き込んだ頂点は木から外して考えることができる。
よって再帰的に「どれでもいいので葉頂点の1つに最小値を書き込み、木から外す」ことを繰り返すと、最大値を達成できる。
import sys
n = int(input())
lines = sys.stdin.readlines()
links = [set() for _ in [0] * n]
for line in lines[:n - 1]:
a, b = list(map(int, line.split()))
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
ccc = list(map(int, lines[-1].split()))
ccc.sort(reverse=True)
ans = [-1] * n
ans_sum = 0
leaves = {i for i, l in enumerate(links) if len(l) == 1}
while leaves:
v = leaves.pop()
c = ccc.pop()
ans[v] = c
if not ccc:
break
ans_sum += c
for u in links[v]:
lu = links[u]
lu.remove(v)
if len(lu) == 1:
leaves.add(u)
print(ans_sum)
print(*ans)
等差数列の積とか、いかにも数学ネタで扱いそうな内容なのでググる。
すると、Yahoo知恵袋 Wikipediaに答えが見つかる。
$\displaystyle ((\frac{x}{d}) \times (\frac{x}{d}+1) \times (\frac{x}{d}+2) \times ... \times (\frac{x}{d}+(n-1))) \times d^n$ の形に変形できる。
よって、公差1の場合（つまり階乗）とその逆数だけ事前計算しておけば、後はその結果を使うだけで $O(1)$ なり $O(\log{何か})$ あたりで答えが出せる。
小数が出てくるのは困るが（別に小数のまま計算しても答えは出るのだが、事前計算ができない）、 modの世界では $d$ の逆数が定義できれば、$d$ で割る代わりに $d^{-1}$ をかけることで、整数のまま扱える。 定義できる条件は $d$ と $M(=10^6+3)$が互いに素であることなので、制約より必ず定義できる。
ただし、コーナーケースとして、以下のケースを除いておく。
また、$n$ の制約が $10^9$ なので大きすぎて事前計算に時間がかかりすぎるような気もするが、実は大きすぎても項の中に $10^6+3$ の倍数が必ず含まれてしまうので0になる。
具体的に何項目かは $x,d$ の値によるが、最大でも $10^6+2$ 項の中には含まれる。 これは、$kd \mod{M}$ が、$d$ と $M$ が互いに素であれば $k=0～M-1$ まで全て異なった値を取るため、 その中の最低1つには $x$ を足すと $M$ の倍数になる値が含まれるためである。
実際には、$M - xd^{-1}$ 項目の次で $M$ の倍数になるので、$n_i$ がそれより大きいと0を出力する。
以上の例外に当てはまらなければ、
$\displaystyle \frac{(xd^{-1}+n-1)!}{(xd^{-1}-1)!} \times d^n \mod{M}$ で答えが出せる。
import sys
def prepare(n, MOD):
facts = [1]
t = 1
for i in range(1, n + 1):
t = t * i % MOD
facts.append(t)
invs = [1] * (n + 1)
t = pow(t, MOD - 2, MOD)
invs[n] = t
for i in range(n, 1, -1):
t = t * i % MOD
invs[i - 1] = t
return facts, invs
MOD = 1000003
facts, factinvs = prepare(MOD - 1, MOD)
q = int(input())
ans = []
for line in sys.stdin:
x, d, n = map(int, line.split())
if x == 0:
ans.append(0)
continue
if d == 0:
ans.append(pow(x, n, MOD))
continue
invd = pow(d, MOD - 2, MOD)
xd = x * invd % MOD
limit = MOD - xd
if n > limit:
ans.append(0)
continue
r = xd + n - 1
l = xd - 1
dn = pow(d, n, MOD)
ans.append(facts[r] * factinvs[l] * dn % MOD)
print('\n'.join(map(str, ans)))