【2020牛客NOIP賽前集訓營-普及組】飛行棋

題目

題目連結：https://ac.nowcoder.com/acm/contest/7612/D

思路

顯然要棋子在 \([1,d)\) 和 \([d,n]\) 的時候分開做。

當棋子在 \([1,d)\) 的時候，假設現在在位置 \(p\)，骰子扔到的是 \(x\) 點，那麼棋子可能會變到 \(p-x\) 或 \(x-p\) 的位置。

發現隻有當 \(x\) 恰好等于 \(p\) 的時候才可以結束，否則 \(p\) 将變為依然在 \([1,d)\) 中的另一個位置 \(p'\)。那麼其實等價于在 \(1\sim d-1\) 中一直随機一個數，直到随機到 \(1\) 時停止，求期望次數。

設期望 \(s\) 次扔到點 \(1\)，那麼有

\[s=\frac{d-2}{d-1}(s+1)+\frac{1}{d-1}

\]

代碼

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int Q,n,d;
double f[N],sum[N];

int main()
{
	scanf("%d",&Q);
	while (Q--)
	{
		scanf("%d%d",&n,&d);
		f[0]=sum[0]=1;
		for (int i=1;i<d;i++)
			f[i]=d-1,sum[i]=sum[i-1]+f[i];
		for (int i=d;i<=n;i++)
		{
			f[i]=(sum[i-1]-sum[i-d]+d-1)/d+f[i-d]/d;
			sum[i]=sum[i-1]+f[i];
		}
		printf("%.2lf\n",f[n]);
	}
	return 0;
}