BZOJ5297 [Cqoi2018]社交网络【矩阵树定理】

题目链接

题解

最近这玩意这么那么火

这题要用到有向图的矩阵树定理

主对角线上对应入度

剩余位置如果有边则为\(-1\)，不然为\(0\)

\(M_{i,i}\)即为以\(i\)为根的有向图生成树个数

#include<algorithm>

#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 = 255,maxm = 100005,INF = 1000000000,P = 10007;

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 = a * a % P)

		if (b & 1) ans = 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 = A[j][i] * inv(A[i][i]) % P;

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

				A[j][k] = ((A[j][k] - A[i][k] * t % P) % P + P) % P;

			}

		}

	}

	int re = 1;

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

		re = re * A[i][i] % P;

	re = (re * rev % P + P) % P;

	return re;

}

int main(){

	n = read(); m = read();

	int a,b;

	while (m--){

		a = read(); b = read();

		if (a == b) continue;

		A[b][a] = -1;

		A[a][a]++;

	}

	printf("%d\n",gause());

	return 0;

}

巴特西

BZOJ5297 [Cqoi2018]社交网络【矩阵树定理】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ5297 [Cqoi2018]社交网络 【矩阵树定理】

题目链接

题解

最新文章

热门文章

BZOJ5297 [Cqoi2018]社交网络【矩阵树定理】