なんか最近CF Div2回ミスが多すぎる…。
http://codeforces.com/contest/621/problem/C
問題
N人の人が円周上に並んでいる。
各人L[i]~R[i]の間のいずれかの整数を等確率でランダムに選択する。
i番の人の数値と(i+1)番の選んだ数値の積が素数Pの倍数である場合、2人に1000ずつポイントが入る。
全員の総ポイントの期待値を求めよ。
解法
Pは素数なので、i番と(i+1)番のどちらかがPの倍数を取れば、2人で合計2000pt得られる。
i番の人がPの倍数を取る確率をF(i)とすると、各iに対し1-(1-F[i])*(1-F[i+1])の確率で2000pt得られることになる。
後は上記数式を各iに対して合算するだけ。
int N; ll P; int L[101010],R[101010]; double H[301010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>P; FOR(i,N) { cin>>L[i]>>R[i]; H[i+N]=H[i]=(R[i]/P-(L[i]-1)/P)*1.0/(R[i]-L[i]+1); } double ret=0; FOR(i,N) ret+=1-(1-H[i])*(1-H[i+1]); _P("%.12lf\n",ret*2000); }
まとめ
Bの方が一瞬迷って難しい気が?