解題區/解題區 - Zerojudge

b685. 高中組第五題-課堂抽籤

contents

  1. 1. Problem
  2. 2. Sample Output
  3. 3. Solution

Problem

$N$ 個人抽籤決定跟誰同一組，請問在某些籤已經決定好的情況下，求恰好分成 $M$ 組的抽籤方法數。

轉換成 $N$ 個節點，恰好形成 $M$ 個環的方法數。

## Sample Input ##

1
2
3
4
5
2
5 1
2 3 1 5 4
5 2
2 3 1 5 4

Sample Output

1
2
0
1

Solution

在此特別感謝 lwc (Wei Chen Liao) 提供思路。

手動暴力打表後，上網蒐到 A125714 Alfred Moessner’s factorial triangle. 恰好是這個數列的答案。

由於每一個人的籤不重複，若把他抽到的籤當作指向出去的邊，那麼保證這一個點恰好一個出邊和一個入邊。當所有籤抽滿後，圖看起來是好幾個環。

遞迴定義 dp[i][j] 表示有 $i$ 個節點和 $j$ 個環。考慮新加入得點要抽到哪一個籤，加入到 $j$ 個環的情況，則是把某一個環的某一個位置打開加入，或者自身形成一個環，最後得到 dp[i][j] = dp[i-1][j-1] + (i-1)*dp[i-1][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1024;
const long long MOD = 1000007;
long long dp[MAXN][MAXN];
int A[MAXN], used[MAXN];
int main() {
    dp[0][0] = dp[1][1] = 1;
    for (int i = 2; i < MAXN; i++) {
        for (int j = 1; j <= i; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (i-1))%MOD;
    }
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        int a = n, b = 0;
        memset(used, 0, sizeof(used));
        for (int i = 1; i <= n; i++) {
            if (used[i])
                continue;
            int x = i, cnt = 0;
            while (x && used[x] == 0)
                used[x] = 1, x = A[x], cnt++;
            a -= cnt-1;
            if (x == i)	m--;
            if (x == 0)	b++;
        }
        if (m < 0)
            puts("0");
        else
            printf("%lld\n", dp[b][m]);
    }
    return 0;
}