【题意】有n道题，第i道题有ai个选项。把第i道题的正确答案填到第i+1道题上（n填到1），问期望做对几道题。n<=10^7。

【算法】期望DP

【题解】正确答案的随机分布不受某道题填到后面是否正确影响，因此每道题对的期望都是独立的。

从排列的角度分析，对每道题有a[i-1]个选择和a[i]个选项，共a[i-1]*a[i]种排列，其中只有min(a[i-1],ai)种排列使这道题正确，所以

$$E(i)=\frac{Min(a[i-1],a[i])}{a[i-1]*a[i]}=\frac{1}{Max(a[i-1],a[i])}$$

然后根据期望的线性相加。

复杂度O(n)。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int n,a[maxn];

int main()

{

    int A,B,C;

    scanf("%d%d%d%d%d",&n,&A,&B,&C,&a[]);

    for (int i=;i<=n;i++) a[i] = ((long long)a[i-] * A + B) % ;

    for (int i=;i<=n;i++) a[i] = a[i] % C + ;

    a[]=a[n];

    double ans=;

    for(int i=;i<=n;i++)ans+=1.0/max(a[i],a[i-]);

    printf("%.3lf",ans);

    return ;

} 

如果实在纠结前面题对和后面题对有一题重合，考虑期望可以线性相加，所以实际上是可以拆出来计算的。

最新文章

1. [Android Pro] 常用的android工具类和库
2. ThinkPHP 3.2.3 使用 PHPExcel 处理 Excel 表格
3. Use getopt() &amp; getopt_long() to Parse Arguments
4. Visual Studio Enterprise 2015下载 Update3
5. (String)将一个String里面的单词反转
6. JSP、HTML标签
7. C# 代码页获取input的值
8. 嵌入式开发板iTOP4412学习开发板
9. java面试每日一题12
10. using System.Collections.Generic;
11. Outlook接收qq的邮件
12. 【JS】Beginner9:Arrays
13. AQuery简介：jQuery for Android
14. OSPF 原理
15. URLWRITE视图重写技术
16. Java中面向字符的输入流
17. 20164301 Exp2 后门原理与实践
18. [Scala] [Coursera]
19. VMMAP的简单使用
20. Alpha版本事后诸葛亮

热门文章

1. lintcode-201-线段树的构造
2. C关键字volatile总结
3. sphinx配置 + php
4. elasticsearch6 学习之基础CURD
5. word批量转pdf文件快捷方法。
6. 【bzoj4709】[Jsoi2011]柠檬 斜率优化
7. CIR,CBS,EBS,PIR,PBS 名词解释 令牌桶应用
8. 【刷题】BZOJ 1468 Tree
9. hdu1693 Eat the Trees 【插头dp】
10. SQLite中的自增关键字：AUTO_INCREMENT、INTEGER PRIMARY KEY与AUTOINCREMENT