Cayley

BZOJ 4766 文艺计算姬

Posted on

完全二分图的生成树计数问题。

这里是作为找规律的题目出现的……
对于这张图的一边 n 个节点,另一边 m 个节点。 其结果为

$$n^{m-1} \times m^{n-1}$$

因为数据非常大,为 1e18 ,long long 也会爆炸
用到了快速乘,快速幂

题意:
计算完全二分图的生成树数量

思路:
公式已给。证明无。
……

AC Code

#include <cstdio>

using namespace std;
typedef unsigned long long ull;

ull fastMul(ull a, ull b, ull mod)
{
    ull ret = 0;
    for (; a; a >>= 1, b = (b + b) % mod)
        if (a & 1)
            ret = (ret + b) % mod;
    return ret;
}

ull fastPow(ull x, ull a, ull mod)
{
    ull ret = 1;
    for (; a; a >>= 1, x = fastMul(x, x, mod))
        if (a & 1)
            ret = fastMul(ret, x, mod);
    return ret;
}
int main()
{
    ull n, m, p;
    scanf("%lld %lld %lld", &n, &m, &p);
    printf("%lld\n", fastMul(fastPow(n, m - 1, p), fastPow(m, n - 1, p), p));
    return 0;
}
Cayley

BZOJ 1430 小猴打架

Posted on

在搜最小生成树计数的题目的时候不小心发现了一个有趣的东西

51nod 1601

完全图的最小生成树计数问题……题解说需要01字典树,不是很会,先放一放
然后就找到了这个资料 Prüfer编码与Cayley公式

简单说完全图的生成树数量为 \( n^{n-2} \)
这个运用矩阵树也可以计算的

题意:
n只猴子打架,两只猴子打架后就会成为好朋友,就不会打架,朋友关系可传递,问打架的序列方案数。

思路:
n个点的生成树数量为 \( n^{n-2} \) ,顺序为 (n-1)!

AC Code

#include <cstdio>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
const int mod = 9999991;
int n;
long long ans = 1;
int main()
{
    scanf("%d", &n);
    range(i, 1, n - 2) ans = ans * n % mod;
    range(i, 1, n - 1) ans = ans * i % mod;
    printf("%lld", ans);
    return 0;
}

Matrix-Tree

BZOJ 4031 小Z的房间

Posted on

矩阵树定理第二题,用于有取模处理的运算。
中间一直超时,还一位bzoj会卡宏定义……真是石乐志

题意:
给你一个n×m矩阵,矩阵中的' . '表示成一个房间,' * ‘ 表示柱子,在相邻的房间中可以连边,要求每个房间都相连,求方案数。

思路:
算是比较裸的矩阵树定理应用了,对每一个点,标号,再对相邻都是点的格子建边。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

typedef long long ll;
const int maxn = 105;
const int mod = 1e9;

ll c[maxn][maxn];
char mat[maxn][maxn];
int G[maxn][maxn];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

ll getDet(ll a[][maxn], int n)
{
    range(i, 1, n) range(j, 1, n) a[i][j] = (a[i][j] + mod) % mod;
    ll ret = 1;
    range(i, 1, n - 1)
    {
        range(j, i + 1, n - 1) while (a[j][i])
        {
            ll t = a[i][i] / a[j][i];
            range(k, i, n - 1) a[i][k] = (a[i][k] - a[j][k] * t % mod + mod) % mod;
            range(k, i, n - 1) swap(a[i][k], a[j][k]);
            ret = -ret;
        }
        if (a[i][i] == 0)
            return 0;
        ret = ret * a[i][i] % mod;
    }
    return (ret + mod) % mod;
}

int main()
{
    int n, m, num = 0;
    scanf("%d %d", &n, &m);
    each(i, n) scanf("%s", mat[i]);
    each(i, n) each(j, m) if (mat[i][j] == '.') G[i][j] = ++num;
    each(i, n) each(j, m) if (G[i][j])
    {
        int u = G[i][j];
        each(k, 4)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x < 0 || x >= n || y < 0 || y >= m || mat[x][y] != '.')
                continue;
            int v = G[x][y];
            c[u][u]++, c[u][v]--;
        }
    }
    printf("%lld\n", getDet(c, num));
    return 0;
}
Maths

SPOJ 104 Highways

Posted on

早上在学最小生成树计数。
最小生成树算法基于 Matrix-Tree 定理,Matrix-Tree定理是被广泛应用与求生成树计数中。
其具体流程为构造基尔霍夫矩阵,再对其求 n-1 阶行列式即可。

  • 基尔霍夫矩阵 为 其度数矩阵D[G] - 邻接矩阵A[G]
  • 度数矩阵D[G] 满足,当 i≠ j 时,dij=0;当i=j时,dij等于vi的度数。
  • 邻接矩阵A[G] 满足,如果vi、vj之间有边直接相连,则aij=1,否则为0。

不得不说SPOJ的数据之强,一个小问题找了我大半天才找着,SPOJ倒是我想做验证模板的不二之选。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define ll long long

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 105;

ll c[maxn][maxn];
ll degree[maxn];

inline bool scan_d(int& num)
{
    char in;
    in = getchar();
    if (in == EOF)
        return false;
    while (in < '0' || in > '9')
        in = getchar();
    num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9')
        num *= 10, num += in - '0';
    return true;
}

ll getDet(ll a[][maxn], int n)
{
    ll ret = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++)
            while (a[j][i]) {
                ll t = a[i][i] / a[j][i];
                for (int k = i; k <= n; k++)
                    a[i][k] = (a[i][k] - a[j][k] * t);
                for (int k = i; k <= n; k++)
                    swap(a[i][k], a[j][k]);
                ret = -ret;
            }
        if (a[i][i] == 0)
            return 0;
        ret = ret * a[i][i];
    }
    return ret < 0 ? -ret : ret;
}

int main()
{
    int T, u, v, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        memset(c, 0, sizeof c);
        memset(degree, 0, sizeof degree);
        while (m--) {
            scan_d(u);
            scan_d(v);
            c[u][v] = c[v][u] = -1;
            degree[u]++, degree[v]++;
        }
        for (int i = 1; i <= n; i++)
            c[i][i] = degree[i]; //因为不存在自环呀
        printf("%lld\n", getDet(c, n - 1));
    }
    return 0;
}