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;
}