M_sea

洛谷4455 [CQOI2018]社交网络
LuoguBZOJ分析有向图上的$\texttt{Matrix_Tree}$定理的板子。这题以$1$为根,所以只能...
扫描右侧二维码阅读全文
28
2019/01

洛谷4455 [CQOI2018]社交网络

Luogu

BZOJ

分析

有向图上的$\texttt{Matrix_Tree}$定理的板子。

这题以$1$为根,所以只能删去第一行和第一列。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=250+10;
const int MOD=10007;

int n,m;
int a[N][N];

inline int calc() {
    int ans=1;
    for (re int i=2;i<=n;++i) {
        for (re int j=i+1;j<=n;++j)
            while (a[j][i]) {
                int t=a[i][i]/a[j][i];
                for (re int k=i;k<=n;++k) {
                    a[i][k]=(a[i][k]-a[j][k]*t%MOD+MOD)%MOD;
                    swap(a[i][k],a[j][k]);
                }
                ans=MOD-ans;
            }
        ans=ans*a[i][i]%MOD;
    }
    return (ans+MOD)%MOD;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        ++a[u][u],--a[v][u];
    }
    printf("%d\n",calc());
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 29 PM

发表评论