2010-1164

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：有m种变换ai->bi表示可以把一个ai变成bi。问你n个0到n-1的数组成的序列中有多少种可以通过若干次变换变成0到n-1的排列。其中ai!=aj, bi!=bj。
解法：如果把一个变换看成图中一条边，那么整个图就是每个点入度和出度最多都是1的图。很容易发现每个点要么在一个环里面，要么在一条链上（一个点也算一条链）。对每个部分独立计算最后用乘法原理得到最终结果即可。
{{{
#!cpp
#include <cstdio>
#include <cstring>

typedef long long LL;

const int MAXN = 200;
const LL MOD = 1000000007LL;

int n, m;
int c[201][201];
int e[MAXN];
bool deg[MAXN], used[MAXN];

void init() {
    c[0][0] = 1;
    for (int i = 1; i <= 200; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            (c[i][j] >= MOD) && (c[i][j] -= MOD);
        }
    }
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; cases++) {
        scanf("%d%d", &n, &m);
        memset(e, -1, sizeof(e));
        memset(deg, 0, sizeof(deg));
        memset(used, 0, sizeof(used));
        for (int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            e[x] = y;
            deg[y] = true;
        }
        LL res = 1LL;
        int tot = n;
        for (int i = 0; i < n; i++) {
            if (!deg[i]) {
                int count = 1;
                used[i] = true;
                for (int j = i; e[j] != -1; j = e[j], used[j] = true, count++);
                for (int j = 1; j < count; j++) {
                    res = res * (count + 1) % MOD;
                }
                res = res * c[tot][count] % MOD;
                tot -= count;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                int count = 1;
                used[i] = true;
                for (int j = i; e[j] != i; j = e[j], used[j] = true, count++);
                for (int j = 0; j < count; j++) {
                    res = res * count % MOD;
                }
                res = res * c[tot][count] % MOD;
                tot -= count;
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}
}}}

题意：有m种变换ai->bi表示可以把一个ai变成bi。问你n个0到n-1的数组成的序列中有多少种可以通过若干次变换变成0到n-1的排列。其中ai!=aj, bi!=bj。

解法：如果把一个变换看成图中一条边，那么整个图就是每个点入度和出度最多都是1的图。很容易发现每个点要么在一个环里面，要么在一条链上（一个点也算一条链）。对每个部分独立计算最后用乘法原理得到最终结果即可。

#include <cstdio>
#include <cstring>
typedef long long LL;
const int MAXN = 200;
const LL MOD = 1000000007LL;
int n, m;
int c[201][201];
int e[MAXN];
bool deg[MAXN], used[MAXN];
void init() {
    c[0][0] = 1;
    for (int i = 1; i <= 200; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            (c[i][j] >= MOD) && (c[i][j] -= MOD);
        }
    }
}
int main() {
    init();
    int T;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; cases++) {
        scanf("%d%d", &n, &m);
        memset(e, -1, sizeof(e));
        memset(deg, 0, sizeof(deg));
        memset(used, 0, sizeof(used));
        for (int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            e[x] = y;
            deg[y] = true;
        }
        LL res = 1LL;
        int tot = n;
        for (int i = 0; i < n; i++) {
            if (!deg[i]) {
                int count = 1;
                used[i] = true;
                for (int j = i; e[j] != -1; j = e[j], used[j] = true, count++);
                for (int j = 1; j < count; j++) {
                    res = res * (count + 1) % MOD;
                }
                res = res * c[tot][count] % MOD;
                tot -= count;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                int count = 1;
                used[i] = true;
                for (int j = i; e[j] != i; j = e[j], used[j] = true, count++);
                for (int j = 0; j < count; j++) {
                    res = res * count % MOD;
                }
                res = res * c[tot][count] % MOD;
                tot -= count;
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}