背结论 : 度-邻

CODE1

O(n3logn)O(n^3logn)O(n3logn)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<class T>inline void read(T &num) {

    register char ch; register int flg = 1;

    while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;

    for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar());

    num *= flg;

}

const int MAXN = 85;

const int mod = 1e9;

int n, m, tot, id[10][10];

int a[MAXN][MAXN], d[MAXN][MAXN], g[MAXN][MAXN];

char s[10];

inline void link(int u, int v) {

    ++d[u][u], ++d[v][v];

    ++g[u][v], ++g[v][u];

}

inline int Gauss(int N) { //高斯消元成上三角

    int ans = 1;

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

        for(int k = i+1; k <= N; ++k)

            while(a[k][i]) { //这里有一个log

                int d = a[i][i] / a[k][i];

                for(int j = i; j <= N; ++j)

                    a[i][j] = ((a[i][j] - 1ll * d * a[k][j] % mod) % mod + mod) % mod;

                swap(a[i], a[k]), ans = -ans; //注意每交换两行都要取反

            }

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

    }

    return ans;

}

int main() {

    read(n), read(m);

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

        scanf("%s", s+1);

        for(int j = 1; j <= m; ++j)

            if(s[j] != '*') {

                id[i][j] = ++tot;

                if(id[i-1][j]) link(tot, id[i-1][j]);

                if(id[i][j-1]) link(tot, id[i][j-1]);

            }

    }

    for(int i = 1; i < tot; ++i)

        for(int j = 1; j < tot; ++j)

            a[i][j] = d[i][j] - g[i][j];

    printf("%d\n", (Gauss(tot-1) + mod) % mod);

}

CODE2

O(n3+n2logn)→O(n3)O(n^3+n^2logn)\to O(n^3)O(n3+n2logn)→O(n3)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<class T>inline void read(T &num) {

    register char ch; register int flg = 1;

    while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;

    for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar());

    num *= flg;

}

const int MAXN = 85;

const int mod = 1e9;

int n, m, tot, id[10][10];

int a[MAXN][MAXN], d[MAXN][MAXN], g[MAXN][MAXN];

char s[10];

inline void link(int u, int v) {

    ++d[u][u], ++d[v][v];

    ++g[u][v], ++g[v][u];

}

inline void kill(int a, int b, int &ii, int &ik, int &ki, int &kk, int &sign) {

    ii = 1, ik = 0;

    ki = 0, kk = 1;

    sign = 1;

    while(b) {

        (ii -= a/b * ki) %= mod;

        (ik -= a/b * kk) %= mod;

        a -= a/b * b;

        swap(a, b);

        swap(ii, ki);

        swap(ik, kk);

        sign = -sign;

    }

}

inline int Gauss(int N) {

    int ans = 1, ii, ik, ki, kk, sign;

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

        for(int k = i+1; k <= N; ++k) if(a[k][i]) {

            kill(a[i][i], a[k][i], ii, ik, ki, kk, sign); //先把系数算出来

            ans *= sign;

            for(int j = i; j <= N; ++j) {

                int _aij = (1ll * a[i][j] * ii + 1ll * a[k][j] * ik) % mod;

                int _akj = (1ll * a[i][j] * ki + 1ll * a[k][j] * kk) % mod;

                a[i][j] = _aij, a[k][j] = _akj;

            }

        }

        ans = 1ll * ans * a[i][i] % mod;

    }

    return ans;

}

int main() {

    read(n), read(m);

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

        scanf("%s", s+1);

        for(int j = 1; j <= m; ++j)

            if(s[j] != '*') {

                id[i][j] = ++tot;

                if(id[i-1][j]) link(tot, id[i-1][j]);

                if(id[i][j-1]) link(tot, id[i][j-1]);

            }

    }

    for(int i = 1; i < tot; ++i)

        for(int j = 1; j < tot; ++j)

            a[i][j] = d[i][j] - g[i][j];

    printf("%d\n", (Gauss(tot-1) + mod) % mod);

}

巴特西

BZOJ 4031: [HEOI2015]小Z的房间 (矩阵树定理板题)

CODE1

CODE2

最新文章

热门文章

巴特西

BZOJ 4031: [HEOI2015]小Z的房间 (矩阵树定理 板题)

CODE1

CODE2

最新文章

热门文章

BZOJ 4031: [HEOI2015]小Z的房间 (矩阵树定理板题)