关键词：
51nod 1850 抽卡大赛(期望)
题目大意
51Nod为了活跃比赛前的气氛，组织了场抽卡比赛。这场比赛共 n个人参加，主办方根据非欧血统鉴定器，得到了一些数据。每个人抽卡有 Mi 种可能，得到的卡能力值为 Aij 代价为 Gij 的可能性为 Pij ，所谓代价指的是玩家需要将一轮比赛后所得的点头盾的 Gij% 交给主办方。每轮比赛每个人都随机抽取卡片，待全部人抽取完毕后进行排名（按照A从大到小排），排在第 i 位的人有 Vi 的点头盾收入。现在主办方想知道一轮比赛后每个人的期望收入。
数据范围
第一行一个正整数 n
接下来 n 个部分
每个部分第一行为正整数 Mi，接下来 Mi 行有三个整数 Aij Gij Pij
接下来一行 n 个整数，分别为 Vi
设 ∑Pij=Qi，则第 i 个人抽到第 j 张卡的概率为 Pij/Qi
1<=n,Mi<=200，1<=Aij<=1000000000，保证 Aij 互不相同，0<=Gij<=100，1<=Pij<=1000，1<=Vi<=1000
解题思路
没见过的思路
首先很好有一个 (Theta(n^4)) 的做法，想知道第 i 个人的期望，假设他抽到的是第 j 个，能力值为 A，可以直接 (Theta(n^2)) 的 dp 得出他排在第 k 名的概率
也有另一种表示方法 (prod p_ix+(1-p_i))，其中 (p_i) 表示第 i 个人的能力值比 (A) 大的概率
即使这样也还是暴力的，但我们发现枚举 i，j 的顺序不会有任何影响，所以我们将所有卡按能力值排序，从低到高枚举，不难发现每次只有一个二项式发生变化，也就是我们暴力除法在乘法即可，因为多项式只有两项，所以可以 (Theta(n)) 的从一个转移到另一个
代码
const int P = 1e9+7;
const int N = 205;
ll fpw(ll x, ll mi)
ll res = 1;
for (; mi; mi >>= 1, x = x * x % P)
if (mi & 1) res = res * x % P;
return res;
struct node
ll a, g, p, num;
bool operator < (const node &i) const
return a < i.a;
a[N][N], all[N * N];
ll sum[N], m[N], cnt;
ll inv[N], f[N * N], g[N * N], Inv = fpw(100, P - 2);
ll v[N], p[N], ans[N], n;
void Mul(ll a, ll b)
for (int i = 0;i <= n; i++) g[i] = f[i] * b % P;
for (int i = 0;i <= n; i++) g[i + 1] = (g[i + 1] + f[i] * a) % P;
for (int i = 0;i <= n; i++) f[i] = g[i];
void Div(ll a, ll b)
ll Inv = fpw(a, P - 2);
for (int i = n;i >= 0; i--)
ll k = f[i + 1] * Inv % P;
g[i] = k, f[i] = (f[i] - b * k % P + P) % P;
for (int i = 0;i <= n; i++) f[i] = g[i];
int main()
freopen ("hs.in","r",stdin);
// freopen ("hs.out","w",stdout);
read(n);
for (int i = 1;i <= n; i++)
read(m[i]); p[i] = 0;
for (int j = 1;j <= m[i]; j++)
read(a[i][j].a), read(a[i][j].g);
read(a[i][j].p), a[i][j].num = i;
sort(a[i] + 1, a[i] + m[i] + 1);
for (int j = 1;j <= m[i]; j++)
sum[i] = sum[i] + a[i][j].p;
inv[i] = fpw(sum[i], P - 2);
for (int j = 1;j <= m[i]; j++)
a[i][j].p = a[i][j].p * inv[i] % P;
a[i][j].g = 100 - a[i][j].g;
all[++cnt] = a[i][j];
for (int i = 1;i <= n; i++) read(v[i]);
sort(all + 1, all + cnt + 1);
f[0] = 1;
for (int i = 1;i <= n; i++) Mul(p[i] = 1, 0);
for (int i = 1;i <= cnt; i++)
int k = all[i].num;
Div(p[k], (1 - p[k] + P) % P);
for (int j = 1;j <= n; j++)
ans[k] = (ans[k] + all[i].g * Inv % P * v[j] % P * f[j-1] % P * all[i].p) % P;
p[k] = (p[k] - all[i].p + P) % P;
Mul(p[k], (1 - p[k] + P) % P);
for (int i = 1;i <= n; i++) write(ans[i]);
return 0;
51nod1450闯关游戏——期望dp(代码片段)
题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1450期望DP；INF表示这种情况不行，转移时把不行的概率也转移到自身即可；还要按得星概率排个序，先决策概率大的就是最优策略，因为后面的都基于它。代码如下：#include&l... 查看详情
51nod1450闯关游戏——期望dp(代码片段)
题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1450想了半天，不知道不能走的状态（即最后不足m个的状态）怎么办。去吃晚饭的路上想到那种也是转移到f[i][j]自己，因为意义是需要再来一次，状态没有前进。想出那个之... 查看详情
51nod3145概率与期望扔球游戏(代码片段)
...次取出的球是黑球，则令S[i]=1求问在序列S中，期望有多少i(1≤i<n+m 查看详情
51nod.1381硬币游戏（概率与期望）(代码片段)
硬币游戏解题思路这题可以把答案分成两类1是上下都顶着线，就是2r+12是都与先相交，就是2r因为1的情况无穷小，几乎没有，所以舍去答案就是2r#include<cstdio>usingnamespacestd;intmain() intT,n; scanf("%d",&T);... 查看详情
51nod.1381硬币游戏（概率与期望）(代码片段)
硬币游戏解题思路这题可以把答案分成两类1是上下都顶着线，就是2r+12是都与先相交，就是2r因为1的情况无穷小，几乎没有，所以舍去答案就是2r#include<cstdio>usingnamespacestd;intmain() intT,n; scanf("%d",&T);... 查看详情
51nod1632概率与期望b君的连通(代码片段)
...xff0c;B国希望知道在被炸毁之后，剩下联通块的个数的期望是多少？输入第一行输入一个数n 查看详情
luogu1850换教室(期望dp)(代码片段)
题目:P1850换教室大概是期望DPNoip极其友好的一道题目,DP不怎么会的我想到了,大概是自己比较有成就感的题目(我才不会告诉你们,我这个题因为constint挂了)期望的线性性质:和的期望=期望的和.期望(E(x)=sum_iP_i*W_i)那么这个题的期望... 查看详情
51nod1632概率与期望b君的连通(代码片段)
...xff0c;B国希望知道在被炸毁之后，剩下联通块的个数的期望是多少？输入第一行输入一个数n（2<=n<=100000）接下来n-1行，每行两个数x,y表示城市x,y间有一条交通线。(1<=x,y<=n)数据保证其交通系... 查看详情
51nod3145概率与期望扔球游戏(代码片段)
...次取出的球是黑球，则令S[i]=1求问在序列S中，期望有多少i(1≤i<n+m)满足S[i]=0且S[i+1]=1输入一行两个整数n,m，分别表示黑球的个数和白球的个数输出一行，输出期望的最简分数形如p/q数据范围对于30... 查看详情
p1850换教室(代码片段)
传送门期望DP因为课程是按时间顺序的，后面的变化不会影响前面的结果对于每个时间段的课，只有两种选择（换or不换）那么显然DP，而且 好像 转移也很好写...显然设dp[i][j]表示到了第i个时间段，已经提交了j节课的申... 查看详情
51nod1381概率与期望（内含基础知识）硬币游戏(代码片段)
...计算一下抛一次硬币之后，该硬币和直线相交数目的期望。输入第一行给出一个整数T，表示有T组数据(1<=T<=10000)。第2行到T+1行，每行给出一个整数R。(0<R<=10,000,000,000)输出对于每一个数据，在... 查看详情
●51nod1705七星剑
...http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1705题解：期望dp，期望的线性性质 (首先对于第k颗星，一定只会用同一种膜法石去炼化它。) 定义f[k]表示炼化成功第k颗星最小的期望花费。 正向枚举k，然后枚举当前用哪个膜法石i... 查看详情
luogup6633[zjoi2020]抽卡(代码片段)
其实我只是来写一发暴力70pts的DP的说，正解拉格朗日反演，牛顿迭代什么的根本策不懂恭喜彩笔hl666再次因为快速幂忘记返回值调了快一个小时这种关于轮次的求期望类似于[ZJOI2019]麻将的方法，考虑第(i)轮对答案的贡献就是前(i... 查看详情
[题解]数学期望_luogu_p1850_换教室(代码片段)
数学期望dp，题面第一次见很吓人，然而从CCF语翻译成人话就简单多了，开始一般会想到用f[i][j]表示前i个课程申请j次的期望，然而其实会发现转移的时候还和上一次的情况有关（有某概率取上一次某种情况）所以用f[i][j][0/1]记... 查看详情
51nod1240莫比乌斯函数(代码片段)
链接：莫比乌斯函数问题-51Nod http://www.51nod.com/onlineJudge/questionCode.html#!problemId=12401240 莫比乌斯函数 基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注莫比乌斯函数，由德国数... 查看详情
区间dp51nod1021(代码片段)
题目链接：https://www.51nod.com/Challenge/ProblemSubmitDetail.html#!#judgeId=673021代码：参考博客：https://blog.csdn.net/qq_40772692/article/details/80183248#include<iostream>#include<cstring>#include& 查看详情
动态规划51nod1183(代码片段)
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=11831183 编辑距离 基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注编辑距离，又称Levenshtein距离（也叫做EditDistance） 查看详情
「luogu」1850换教室(代码片段)
...代价。求：申请哪几门课程能使Yu在教室之间乱跑的体力期望最小 思路：1.dp[i][j][k]表示到第i个点，已经更改了j次，k=0这个点不更 查看详情