【HN Training 2015 Round9】HOMEWORK

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

【HN Training 2015 Round9】HOMEWORK

img

img

“我感觉这道题在骗我。”

——Sparrow大神

标程给出了很傻神的做法，然而有一种很简单的做法。

众所周知（而我之前就不知道！），期望具有线性性。以下性质很有用：

记$E$为期望。

对于两个随机变量$x,y$，有$E[x+y]=E[x]+E[y]$ 。

对于两个无关的随机变量$x,y$，有$E[xy]=E[x]E[y]$。

于是这道题就做完了……显然矩阵里的元素都是两两无关的，而行列式的计算过程中只有加法和乘法，所以行列式的期望就是期望的行列式，高斯消元$O(n^3)$解决。

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
41
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#define db double
using namespace std;

int N,L[10][10],R[10][10];
db Mat[10][10];

int Gauss(){
	db ret=1.0;
	int x,y,i,j,id,sign=0;db t;
	for(x=y=1;x<=N&&y<=N;x++,y++){
		for(i=x,id=-1;i<=N;i++)if(Mat[i][y]!=0){id=i;break;}
		if(id==-1)return 0;
		if(x!=id){
			sign^=1;
			for(i=y;i<=N;i++)swap(Mat[x][i],Mat[id][i]);
		}
		for(i=x+1;i<=N;i++){
			t=Mat[i][y]/Mat[x][y];
			for(j=y;j<=N;j++)Mat[i][j]-=Mat[x][j]*t;
		}
	}
	for(i=1;i<=N;i++)ret=ret*Mat[i][i];
	if(sign)ret=-ret;
	return floor(ret);
}

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++)Mat[i][j]=1.0*(L[i][j]+R[i][j])/2.0;
	printf("%d\n",Gauss());
}