十二省NOI“省选”联考模测(第二场)A抽卡大赛

it2022-05-06  0

/* dp维护整体的概率, 每次相当于回退一格然后重新dp一格 */ #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<queue> #define ll long long #define M 202 #define mmp make_pair using 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


最新回复(0)