51nod 1850 카드 추첨 대회(12성 연합 시험 모형 테스트) ["동적"(다항식)DP]

제목 전송문

제목 분석:

만약에 i번째 개인의 수입만 요구한다면 그가 선택한 카드를 열거한 다음에 O(n2)DP가 그의 순위가 k일 확률을 계산하면 된다.한 사람을 구하는 것은 O(n3)이고, n사람을 구하는 것은 O(n4)이다.이 폭력을 휘두르고 보니 63점이나 돼서 도망갔어요.
O(n3)의 방법: 하나의 권한 A에 대해 분명히 그 값보다 큰 값만 순위에 영향을 미친다.그래서 우리는 모든 A값을 함께 정렬하고 Ai의 기대 순위를 어떻게 구하는지 고려한다.만약에 서로 다른 A를 다른 사람이 선택한다면 이것은 매우 쉬운DP이다. 그러나 현재Ai의 앞에는Aj가 같은 사람의 선택일 수 있다. 이것은 비교적 까다롭다. 우리는 앞의 공헌을 제거해야 한다.
만약에 값 A가 n 개인 중의 기대 순위를 하나의 생성 함수로 간주한다면 A보다 큰 수는 A의 순위를 증가시킬 수 있다.i pi는 i번째 개인의 선택이 A보다 클 확률로 F(x) = ∏i = 1 n(p i x +(1 - 6 p i) F (x) =\prod{i=1}^n\large(p_ix+(1-p_i)\large) F(x)=i=1∏n​(pi​x+(1−pi​))
제i개인의 선택Ai가 그의 수익에 기여한 바를 통계하려면 이때의 다항식을 제i개인의 식을 제외하면 Ai가 다른 n-1명에 대한 기대 순위를 얻을 수 있다. Ai를 선택할 확률을 타고 대가를 제외하고 ans[i]에 추가하면 된다.(이곳에서 i의 다항식을 제외하면 위의 문제를 완벽하게 해결할 수 있다)
권한 값이 변동할 때 F(x) F(x) F(x)는 한 항목만 변동할 수 있고 변동된 항목은 모두 한 항목이므로 O(n)에서 한 번의 제법과 곱셈을 할 수 있다.(사실 이곳은 DP와 유사하다)
구체적으로 코드를 쓸 때 다항식을 n-1항에 유지하고 Ai의 공헌을 구할 때 i의 다항식을 제거하고 i-1의 다항식을 곱할 수 있다.
Code:

#include
#include
#include
#define LL long long
#define maxn 205
using namespace std;
const int mod = 1e9+7;
inline int ksm(int a,int b){
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) s=1ll*s*a%mod;
	return s;
}
const int inv100 = ksm(100,mod-2);
int n,m[maxn],cnt,v[maxn];
int ans[maxn],ps[maxn];
struct node{
	int A,G,P,id;
	bool operator < (const node &t)const{return A>t.A;}
}a[maxn*maxn];
int f[maxn];
void Div(int p){
	int inv=ksm(1-p,mod-2);//        
	for(int i=0;i<n;i++) f[i]=(f[i]-1ll*f[i-1]*p%mod)*inv%mod;
}
void Mul(int p){
	for(int i=n-1;i>=0;i--) f[i]=(1ll*f[i]*(1-p)+1ll*f[i-1]*p)%mod;
}
int main()
{
	//freopen("H.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&m[i]);
		int s=0;
		for(int j=1;j<=m[i];j++){
			a[++cnt].id=i;
			scanf("%d%d%d",&a[cnt].A,&a[cnt].G,&a[cnt].P);
			a[cnt].G=1ll*(100-a[cnt].G)*inv100%mod;
			s+=a[cnt].P;
		}
		for(int j=0;j<m[i];j++) a[cnt-j].P=1ll*a[cnt-j].P*ksm(s,mod-2)%mod;
	}
	for(int i=0;i<n;i++) scanf("%d",&v[i]);
	sort(a+1,a+1+cnt);
	f[0]=1;
	for(int i=1;i<=cnt;i++){
		if(a[i].id!=a[i-1].id){
			Div(ps[a[i].id]);//         
			Mul(ps[a[i-1].id]);
		}
		for(int j=0;j<n;j++)
			ans[a[i].id]=(ans[a[i].id]+1ll*f[j]*v[j]%mod*a[i].P%mod*a[i].G)%mod;
		ps[a[i].id]=(ps[a[i].id]+a[i].P)%mod;
	}
	for(int i=1;i<=n;i++) printf("%d
",(ans[i]+mod)%mod);
}