51nod 1850 抽卡大赛 (十二省联考模测) DP

O(n4)O(n^4)O(n4)的DP很好想,但是过不了.来看看O(n3)O(n^3)O(n3)的把. Freopen的博客

CODE

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 205;

const int mod = 1e9 + 7;

int n, tot, m[MAXN], v[MAXN], a[MAXN][MAXN], g[MAXN][MAXN], p[MAXN][MAXN], P[MAXN], sump[MAXN];

struct node {

	int i, j;

	inline bool operator <(const node &o)const { return a[i][j] > a[o.i][o.j]; }

}Q[MAXN*MAXN];

inline int qmul(int a, int b) {

	int res = 1;

	while(b) {

		if(b&1) res = 1ll * res * a % mod;

		a = 1ll * a * a % mod; b >>= 1;

	}

	return res;

}

int ans[MAXN], pol[MAXN], tmp[MAXN];

inline void Div(int P) {

	if(!P) return;

	int invp = qmul(P, mod-2);

	for(int i = n; ~i; --i)

		tmp[i] = 1ll * (pol[i+1] - 1ll * tmp[i+1] * (1-P) % mod) % mod * invp % mod;

	for(int i = 0; i <= n; ++i) pol[i] = tmp[i];

}

inline void Mul(int P) {

	for(int i = 0; i <= n; ++i)

		tmp[i] = ((i ? 1ll * pol[i-1] * P % mod : 0) + 1ll * pol[i] * (1-P) % mod) % mod;

	for(int i = 0; i <= n; ++i) pol[i] = tmp[i];

}

int main () {

	scanf("%d", &n);

	int inv100 = qmul(100, mod-2);

	for(int i = 1; i <= n; ++i) {

		scanf("%d", &m[i]);

		for(int j = 1; j <= m[i]; ++j) {

			scanf("%d%d%d", &a[i][j], &g[i][j], &p[i][j]), P[i] += p[i][j];

			Q[++tot] = (node){ i, j };

		}

		P[i] = qmul(P[i], mod-2);

		for(int j = 1; j <= m[i]; ++j)

			g[i][j] = 1ll * (100 - g[i][j]) * inv100 % mod,

			p[i][j] = 1ll * p[i][j] * P[i] % mod;

	}

	for(int i = 0; i < n; ++i) scanf("%d", &v[i]);

	sort(Q + 1, Q + tot + 1);

	pol[0] = 1;

	for(int i = 1; i <= tot; ++i) {

		Div(sump[Q[i].i]);

		for(int j = 0; j < n; ++j)

			ans[Q[i].i] = (ans[Q[i].i] + 1ll * pol[j] * v[j] % mod * g[Q[i].i][Q[i].j] % mod * p[Q[i].i][Q[i].j] % mod) % mod;

		sump[Q[i].i] = (sump[Q[i].i] + p[Q[i].i][Q[i].j]) % mod;

		Mul(sump[Q[i].i]);

	}

	for(int i = 1; i <= n; ++i) printf("%d\n", (ans[i] + mod) % mod);

}