yukicoder : No.1408 Nice Dice Game

数学問題。
https://yukicoder.me/problems/no/1408

問題

1～aの目が出るサイコロが(N+1)個、1～bの目が出るサイコロがN個ある。
前者のi個目のサイコロの目をX[i]、同様に後者をY[i]とする。

以下の条件を満たすと1/(b*(b-a))ポイントが得られるとき、各(a,b)の対に対する得られるポイントの期待値を求めよ。

• i-j≡X[i]-X[j] (mod a)を満たす
• Y[i]の少なくとも1個はaを超える。

解法

前者を満たす出目は、X[0]の分a通り。後者はb^N-a^N通り。
よって求める値は。
詳細はEditorialに譲るとして、変形するととなる。
あとはi=1000位まで計算しよう。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	double ret=0;
	for(i=1;i<=1000;i++) ret+=pow(i,-(N+2));
	_P("%.12lf\n",ret);
}

まとめ

ここら辺覚えてもAtCoderやTopCoderで使うことあるのかな。