HN Training 2015 Round9 Homework（Gauss消元+数学期望）

发表于 |
字数统计: 384字 | 阅读时长 ≈ 2min

328-HN Training 2015 R9 2-328-HN Training 2015 R9 2-

这题感觉比较奥妙重重，标解给了一个麻烦的状压dp，但是好像直接将每个位置的期望值代进去算行列式的值就行了。

具体原理大概是因为各个位置都是相互独立的随机变量，那么他们的期望可加也可乘，那么就可以直接将行列式求期望值的式子展开成各个位置的期望再求行列式了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 15
using namespace std;
const double eps=1e-9;
int n,L[N][N],R[N][N];
double C[N][N];
double Gauss()
{
	int i,j,k,x,y,t=0,MR;double a,ans=1;
	for(x=1,y=1,MR=1;x<=n&&y<=n;x++,y++,MR=x)
	{
		for(i=x+1;i<=n;i++)if(fabs(C[i][y])>fabs(C[MR][y]))MR=i;
		if(MR!=x)for(t++,i=1;i<=n;i++)swap(C[x][i],C[MR][i]);
		if(fabs(C[x][y])<eps)return 0;
		for(i=x+1;i<=n;i++)
		{
			if(fabs(C[i][y])<eps)continue;
			a=C[i][y]/C[x][y];
			for(j=y;j<=n;j++)C[i][j]=C[i][j]-C[x][j]*a;
		}
		ans*=C[x][x];
	}
	return t&1?-ans:ans;
}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)scanf("%d",&L[i][j]);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)scanf("%d",&R[i][j]);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)C[i][j]=0.5*(R[i][j]+L[i][j]);
	printf("%.0lf",floor(Gauss()));
}