[SHOI2016] 黑暗前的幻想乡 - 矩阵树定理,容斥

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 20;

const int mod = 1e+9 + 7;

namespace mat {

int a[N][N];

int n,p=1;

void Clear() {

    memset(a,0,sizeof a);

}

int Solve() {

    int ans = 1;

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

        for(int j = i + 1; j < n; j ++)

            while(a[j][i]) {

                int t = a[i][i] / a[j][i];

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

                    a[i][k] = (a[i][k] - t * a[j][k] + mod) % mod;

                swap(a[i], a[j]);

                ans = - ans;

            }

        ans = (ans * a[i][i]) % mod;

    }

    return (ans + mod) % mod;

}

void Make(int p,int q) {

    a[p][q]--;

    a[q][p]--;

    a[p][p]++;

    a[q][q]++;

}

} // namespace mat

int n;

vector <pair<int,int> > v[N];

signed main() {

    ios::sync_with_stdio(false);

    cin>>n;

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

        int t;

        cin>>t;

        for(int j=1;j<=t;j++) {

            int t1,t2;

            cin>>t1>>t2;

            v[i].push_back(make_pair(t1,t2));

        }

    }

    int ans = 0;

    mat::n=n;

    for(int i=0;i<1<<(n-1);i++) {

        int t=__builtin_popcount(i);

        mat::Clear();

        for(int j=1;j<=(n-1);j++) {

            if(i&(1<<(j-1))) {

                for(int k=0;k<v[j].size();k++) {

                    mat::Make(v[j][k].first, v[j][k].second);

                }

            }

        }

        int tmp = mat::Solve();

        ans += ((n-t-1)%2 ? -1 : 1)*tmp;

        ans %= mod;

        ans += mod;

        ans %= mod;

    }

    cout<<ans<<endl;

}
巴特西

[SHOI2016] 黑暗前的幻想乡 - 矩阵树定理,容斥

最新文章

热门文章
