[题目描述]
有 n 个同学坐成一列, 按从前往后的顺序传 n 本课本, 其中第 i 个同学会从 n-i+1 本课本中选一本并把剩下的课本传给后面的一位同学. 已知每本课本都有独一无二的新旧程度, 第 i(i<n) 个同学在挑选课本的时候满足如下过程:
1. 如果只剩下一本书, 则一定拿走, 否则转步骤 2
2. 从剩下的书中抽出最新的一本
3. 以 ai 的概率选择这本书并结束选择, 1-ai 的概率将这本书传给后面的同学并回到过程 1
现在最后一位同学想知道传到他手上的书的新旧程度在所有 n 本书中排名的期望是多少. 注意: 本题的所有分数均在 mod 1e9+7 意义下, 即如果一个分数可以表示成 x/y 的形式, 则在本题中以 x*(y^(1e9+5)) (mod 1e9+7) 的形式给出, 同时如果你要输出一个分数 x/y, 你也应输出 x*(y^(1e9+5)) (mod 1e9+7).
[输入格式]
第一行一个正整数 n
接下来 n-1 个整数 ai 表示概率
[输出格式]
一个整数表示最后一位同学拿到的书的新旧程度在所有 n 本书中排名的期望.
[样例]
book1.in | book1.out |
3 666666672 500000004 | 277777782 |
大样例见下发文件 book2.in/out,book3.in/out
[样例解释]
sample1:
666666672=2/3(mod1e9+7),500000004=1/2(mod1e9+7) 表示第一个同学有 2/3 的概率拿最新的书, 否则将会有 (1-2/3)*2/3 = 2/9 的概率拿第二新的书, 否则有 1/9 的概率拿第三新的书. 当第一位同学拿完书时, 第二位同学等概率取剩下两本. 故最后一位同学拿到的书新旧程度的期望为 1/3*2+1/3*3+1/9*1
+1/9*3+1/18*1+1/18*2=41/18=277777782(mod 1e9+7)
[数据范围及约定]
对于 100% 的数据 n300,0ai<1000000007
性质 1:ai=0 或 1 性质 2:ai=500000004
编号 | n | 其它 | 编号 | n | 其它 |
1 | 2 | 无 | 11 | 20 | 无 |
2 | 7 | 12 | 300 | 性质 1 | |
3 | 8 | 13 | 250 | 性质 2 | |
4 | 9 | 14 | 300 | ||
5 | 10 | 15 | 40 | 无 | |
6 | 16 | 16 | 50 | ||
7 | 17 | 17 | 100 | ||
8 | 18 | 18 | 150 | ||
9 | 19 | 19 | 250 | ||
10 | 20 | 20 | 300
|
考虑枚举最后剩那本书, 然后我们就只需要考虑其他书对于这本书的相对位置.
- #include <bits/stdc++.h>
- using namespace std;
- #define MOD 1000000007
- int f[310][310], g[310][310], t[310][310];
- int n, a[310];
- inline void Add(int &x, int y) {
- x += y;
- if(x>= MOD) x -= MOD;
- }
- inline void init() {
- for(int i = 1; i < n; ++ i) {
- for(int j = 0; j <= n - i; ++ j) {
- int now = 1;
- for(int k = 1; k <= j; ++ k) {
- Add(g[i][j], 1ll * now * a[i] % MOD);
- now = 1ll * now * (MOD + 1 - a[i]) % MOD;
- }
- t[i][j] = 1ll * now * a[i] % MOD;
- }
- }
- }
- int main() {
- scanf("%d", &n);
- for(int i = 1; i < n; ++ i) {
- scanf("%d", &a[i]);
- }
- init();
- int Ans = 0;
- for(int k = 1; k <= n; ++ k) {
- memset(f, 0, sizeof(f));
- f[1][n - k] = 1;
- for(int i = 1; i < n; ++ i) {
- for(int j = 0; j <= n - i; ++ j) if(f[i][j]) {
- if(j) Add(f[i + 1][j - 1], 1ll * f[i][j] * g[i][j] % MOD);
- Add(f[i + 1][j], 1ll * f[i][j] * (2 * MOD + 1 - g[i][j] - t[i][j]) % MOD);
- }
- }
- Add(Ans, 1ll * f[n][0] * (n - k + 1) % MOD);
- }
- printf("%d\n", Ans);
- }
来源: http://www.bubuko.com/infodetail-2754993.html