ゆらのふなびと

競プロ, Python, C++

Codeforces Round #341 (Div. 2) C - Wet Shark and Flowers

これはね……数学の問題。

問題

n体のサメが丸い机の周りに座っている。i番目のサメと(i+1)%N番目のサメは隣りあっているものとする。

サメiは数s_iを閉区間[l_i, r_i]に含まれる整数から等確率で選ぶ。任意の隣りあうサメi, jに対し、s_i * s_jがpで割り切れるならば、Wet Sharkはサメi, jにそれぞれ1000ドルを与える。

このとき、Wet Sharkがサメたちに与える金額の合計の期待値を求めよ。

制約

3 <= n <= 100000

2 <= p <= 10**9

1 <= l_i <= r_i <= 10**9

解法

もしすべてのs_iに対して全探索などしようものなら、最悪(10*9)100000となり間に合うはずもない。そのため、数式を導出して計算量を落とすことを考える。

便宜上、以下では j = (i + 1) % n とする。(iとjは隣り合うサメの番号を示す)

あるs_i * s_j(j = (i+1)%n)がpで割り切れるとき、Wet Sharkは合計で2000ドル払うことになる。よって以下の等式が成り立つ。

(求める期待値) = 2000 *  \sum_{i=0}^{N}(s_i * s_jがpで割り切れる確率)

さらに、右辺の括弧内について以下が成り立つ。

(s_i * s_jがpで割り切れる確率)

= (s_iまたはs_jがpで割り切れる確率)*1

= 1 - (s_iがpで割り切れない かつ s_jがpで割り切れない確率)

= 1 - (s_iがpで割り切れない確率) * (s_jがpで割り切れない確率)

よって題意の期待値を求めるには、各iについて、「s_iがpで割り切れない確率」が求まればよい。*2


「s_iがpで割り切れない確率」について、以下が成り立つ。

(s_iがpで割り切れない確率)

= ([l_i, r_i]に含まれpで割り切れないの整数の個数) / ([l_i, r_i]に含まれる整数の個数)

= (n_i - a_i) / n_i

ただしn_iは[l_i, r_i]に含まれる整数の個数、a_iは[l_i, r_i]に含まれpで割り切れる数の個数である。

n_iは以下の式で簡単に求まる。

n_i = l_i + r_i - 1

ではa_iはどうか。これは[l_i, r_1] = [1, r_i] - [1, l_i - 1] と分割して考えると簡単である。区間1, mに含まれpで割り切れる整数の個数はfloor(m/p)であるから、a_iは以下の式で求まる。

a_i = floor( r_i / p ) - floor( (l_i - 1) / p )


まとめると以下のようになる。ただしt_iは「s_iがpで割り切れない確率」を表す。

(求める期待値) = 2000 *  \sum_{i=0}^{N} (1 - t_i * t_j)

ただし、

 j = (i + 1) \% n

 t_i = (n_i - a_i) / n_i

 n_i = l_i + r_i - 1

 a_i = floor( r_i / p ) - floor( (l_i - 1) / p )

各t_iの計算はO(1)、ループはO(n)であるから計算時間は間に合う。


以下の実装ではj = (i+1) % n とする代わりにlとrのリストの末尾にl[0], r[0]を追加して、ループをちょうどNまで回すようにしています。

N, p = map(int, input().split())
l = [0 for i in range(N+1)]
r = [0 for i in range(N+1)]
for i in range(N):
    lx, rx = map(int, input().split())
    l[i] = lx; r[i] = rx
l[N] = l[0]; r[N] = r[0]

a1 = r[0] // p - (l[0] - 1) // p
n1 = r[0] - l[0] + 1
t1 = (n1-a1) / n1
ans = 0
for i in range(1, N+1):
    a2 = r[i] // p - (l[i] - 1) // p
    n2 = r[i] - l[i] + 1
    t2 = (n2-a2) / n2
    
    ans += 1 - t1 * t2
    
    t1 = t2

print(2000 * ans)    

*1:上式からこの式へのイコールはpが素数であるため成り立つ

*2:「あれ? s_jがpで割り切れない確率は??」と思った人→ここで確認だが、j = (i+1) % N なので、i = 0..n-1について「s_iがpで割り切れない確率」を求めればOK。