有n道单选题，每道题备选项有(a_i)个，每个选项成为答案概率相等，当把n道单选题按编号1～n顺时针连成一个环，选的答案都是正确的，但是答案都顺时针向下移动一个，此时能选对答案的题目个数的期望，2≤n≤10000000, 0≤A,B,C,a1≤100000000。
解
数据范围已经告诉我们只能用(O(n))，于是设(f[n])表示前n题做对的期望，不难有
[if(a_n>a_{n-1})f[n]=f[n-1]+frac{a_{n-1}}{a_n} imes frac{1}{a_{n-1}}=f[n-1]+frac{1}{a_n}
]
[if(a_nleq a_{n-1})f[n]=f[n-1]+frac{1}{a_{n-1}}
]
于是以此递推即可,注意最后接上环。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
int a[10000001];
double dp[10000001];
int main(){
int i,n,A,B,C;
scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);
for (i=2;i<=n;i++)
a[i] = ((long long)a[i-1] * A + B) % 100000001;
for (i=1;i<=n;i++)
a[i] = a[i] % C + 1;
if(a[n]>a[1])dp[1]=(double)1/a[n];
else dp[1]=(double)1/a[1];
for(i=2;i<=n;++i)
if(a[i-1]>a[i])dp[i]=dp[i-1]+(double)1/a[i-1];
else dp[i]=dp[i-1]+(double)1/a[i];printf("%.3lf",dp[n]);
return 0;
}