博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
十二省NOI“省选”联考模测(第二场)A抽卡大赛
阅读量:4583 次
发布时间:2019-06-09

本文共 2407 字,大约阅读时间需要 8 分钟。

/*dp维护整体的概率, 每次相当于回退一格然后重新dp一格 */#include
#include
#include
#include
#include
#define ll long long #define M 202#define mmp make_pairusing namespace std;int read(){ int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f;}const int mod = 1000000007;int poww(int a, int b){ int ans = 1, tmp = a; for(; b; b >>= 1, tmp = 1ll * tmp * tmp % mod) if(b & 1) ans = 1ll * ans * tmp % mod; return ans;}void add(int &x, int y){ x += y; x -= x >= mod ? mod : 0; x += x < 0 ? mod : 0;}struct Note{ int a, g, p; bool operator < (const Note &b) const { return this->a < b.a; }}note[M][M], sta[M * M];int m[M], q[M], n, v[M], tp;int f[M], g[M], d[M], ans[M];void work(int x){ if(x == 0) { for(int i = 0; i <= n; i++) g[i] = g[i + 1]; return; } int y = (1 + mod - x), invx = poww(x, mod - 2); memset(d, 0, sizeof(d)); for(int i = 0; i <= n; i++) { d[i] = 1ll * g[i] * invx % mod; add(g[i + 1], -1ll * d[i] * y % mod); } for(int i = 0; i <= n; i++) g[i] = d[i]; }int main(){ n = read(); int inv = poww(100 ,mod - 2); for(int i = 1; i <= n; i++) { m[i] = read(); for(int j = 1; j <= m[i]; j++) { note[i][j].a = read(), note[i][j].g = 1ll * (100 - read()) * inv % mod, note[i][j].p = read(); add(q[i], note[i][j].p); sta[++tp] = (Note) {note[i][j].a, i, j}; } int inv = poww(q[i], mod - 2); for(int j = 1; j <= m[i]; j++) note[i][j].p = 1ll * note[i][j].p * inv % mod; } sort(sta + 1, sta + tp + 1); for(int i = 1; i <= n; i++) v[i] = read(); g[n] = 1; for(int now = 1; now <= tp; now++) { int i = sta[now].g, j = sta[now].p; work(f[i]); for(int a = 0; a <= n; a++) add(ans[i], 1ll * note[i][j].p * v[a + 1] % mod * g[a] % mod * note[i][j].g % mod); add(f[i], note[i][j].p); for(int a = n; a >= 0; a--) { g[a] = 1ll * g[a] * f[i] % mod; if(a) add(g[a], 1ll * (1 + mod - f[i]) * g[a - 1] % mod); } } for(int i = 1; i <= n; i++) cout << ans[i] << "\n"; return 0;}

转载于:https://www.cnblogs.com/luoyibujue/p/10596490.html

你可能感兴趣的文章
xcode 快捷键
查看>>
三十五.MySQL读写分离 MySQL多实例 、MySQL性能调优
查看>>
[LeetCode] 256. Paint House_Easy tag: Dynamic Programming
查看>>
Java基础——面向对象编程一:封装
查看>>
python ==> Django.view(登录,注册,个人页)
查看>>
在maven中没有的jar包如何处理?
查看>>
多线程与UI操作
查看>>
python 打印三角行,金字塔等
查看>>
CSS3 3D下拉折叠菜单
查看>>
判断DOM元素是否出现再浏览器窗口中
查看>>
vue小技巧--window变量
查看>>
pyqt重写键盘事件+获取信号发送对象
查看>>
Spark源码剖析 - SparkContext的初始化(六)_创建和启动DAGScheduler
查看>>
Python 使用Opencv实现图像特征检测与匹配
查看>>
50金句
查看>>
JavaScript------事件
查看>>
SQL锁表语句 (转摘)
查看>>
python--递归、二分查找算法
查看>>
mysql5.7 user表没有password字段,如何重置root密码
查看>>
【转】SVN 与 GIT 详细对比
查看>>