BZOJ4894 天赋 【矩阵树定理】

题目链接

BZOJ4894

题解

双倍经验P5297
题解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 305,maxm = 100005,INF = 1000000000,P = 1000000007;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
	return out * flag;
}
int qpow(int a,int b){
	int ans = 1;
	for (; b; b >>= 1,a = 1ll * a * a % P)
		if (b & 1) ans = 1ll * ans * a % P;
	return ans;
}
int inv(int x){return qpow(x,P - 2);}
int A[maxn][maxn],n,m;
int gause(){
	int rev = 1;
	for (int i = 2; i <= n; i++){
		int j = i;
		for (int k = i + 1; k <= n; k++)
			if (abs(A[k][i]) > abs(A[j][i]))
				j = k;
		if (j != i){
			for (int k = i; k <= n; k++) swap(A[i][k],A[j][k]);
			rev = -rev;
		}
		for (j = i + 1; j <= n; j++){
			int t = 1ll * A[j][i] * inv(A[i][i]) % P;
			for (int k = i; k <= n; k++){
				A[j][k] = ((A[j][k] - 1ll * A[i][k] * t % P) % P + P) % P;
			}
		}
	}
	int re = 1;
	for (int i = 2; i <= n; i++)
		re = 1ll * re * A[i][i] % P;
	re = (1ll * re * rev % P + P) % P;
	return re;
}
char s[maxn];
int main(){
	n = read();
	REP(i,n){
		scanf("%s",s + 1);
		REP(j,n) if (s[j] - '0' > 0)
			A[i][j] = -1,A[j][j]++;
	}
	printf("%d
",gause());
	return 0;
}