【题目大意】
有n道题，第i道题有ai个选项。一个人把所有的正确答案填到了后面一题上（特殊的，当i=n的时候填到1上），问他期望做对几道题？
【思路】
沙茶题……显然每道题的期望是独立的。
对于某道题，它做对的概率等于当前题目和下一题答案是一样的概率。考虑选项数较小的那一个，它和另一题答案相同的概率=1/另外一道题的选项。
所以dp[i]=1/max(a[i],a[i+1])
over~
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int MAXN=10000000+50; 5 int a[MAXN]; 6 double ans; 7 int n,A,B,C; 8 9 void init() 10 { 11 scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1); 12 for (int i=2;i<=n;i++) a[i]=((ll)a[i-1]*A+B)%100000001; 13 for (int i=1;i<=n;i++) a[i]=a[i]%C+1; 14 } 15 16 void solve() 17 { 18 ans=0; 19 for (int i=1;i<=n;i++) 20 { 21 double x=(double)a[i]*1.0,y=(double)a[i%n+1]*1.0; 22 ans+=1.0/max(x,y); 23 } 24 printf("%.3f\n",ans); 25 } 26 27 int main() 28 { 29 init(); 30 solve(); 31 return 0; 32 }
原文：http://www.cnblogs.com/iiyiyi/p/5925825.html