【SGU】476 Coach's Trouble

题意：有3*n个人，分成n组，每组三个人。给出k个三元组，这三个人不可组队，问最后可以组队的总方案数。

当k=0时，有(C[3*n][3]*C[3*n-3][3]*……*C[3][3])/n!种方案，展开以后可以得到dp[n]=(3*n)!/n!/6^n。

显然可以写成递推式：dp[n]=dp[n-1]*(3*n-1)*(3*n-2)/2。

那么容斥一下，答案=总方案数-至少含一个禁止组合的+至少含两个禁止组合的-……

二进制暴力TLE了。DFS的话会有很多剪枝，当前几个已经出现冲突，自然不会再往后面搜了。

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Solution {
 5     static int group[][] = new int[25][3];
 6     static int cnt[] = new int[25];
 7     static boolean vis[] = new boolean[3001];
 8     static int n, k, depth;
 9 
10     static void Init() {
11         int i;
12         for (i = 0; i < 25; i++)
13             cnt[i] = 0;
14         for (i = 0; i < 3001; i++)
15             vis[i] = false;
16     }
17 
18     static void DFS(int index, int now) {
19         if (now == depth) {
20             if (depth % 2 == 1)
21                 cnt[depth]++;
22             else
23                 cnt[depth]--;
24         } else {
25             int i;
26             for (i = index; i < k; i++) {
27                 if (vis[group[i][0]] == false && vis[group[i][1]] == false
28                         && vis[group[i][2]] == false) {
29                     vis[group[i][0]] = vis[group[i][1]] = vis[group[i][2]] = true;
30                     DFS(i + 1, now + 1);
31                     vis[group[i][0]] = vis[group[i][1]] = vis[group[i][2]] = false;
32                 }
33             }
34         }
35     }
36 
37     public static void main(String[] args) {
38         Scanner in = new Scanner(System.in);
39         int i, j;
40         BigInteger dp[] = new BigInteger[1001];
41         BigInteger res;
42         dp[0] = dp[1] = BigInteger.ONE;
43         for (i = 2; i < 1001; i++)
44             dp[i] = dp[i - 1].multiply(BigInteger.valueOf(3 * i - 1))
45                     .multiply(BigInteger.valueOf(3 * i - 2))
46                     .divide(BigInteger.valueOf(2));
47         while (in.hasNext()) {
48             Init();
49             n = in.nextInt();
50             k = in.nextInt();
51             for (i = 0; i < k; i++) {
52                 for (j = 0; j < 3; j++)
53                     group[i][j] = in.nextInt();
54             }
55             for (depth = 1; depth <= k; depth++)
56                 DFS(0, 0);
57             res = BigInteger.ZERO;
58             for (i = 1; i <= k; i++) {
59                 if (cnt[i] != 0)
60                     res = res
61                             .add(dp[n - i].multiply(BigInteger.valueOf(cnt[i])));
62             }
63             System.out.println(dp[n].subtract(res));
64         }
65     }
66 }