颜色限制的Burnside引理应用。

以为要用大数所以用java写了。

###Code

UESTC 1153
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;

public class Main {

    static int gcd(int a, int b) {
        if(b == 0)  return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) throws Exception{
        BigInteger f[] = new BigInteger[1005], ans;
        int a[] = new int[110], b[] = new int[110], total;
        Scanner cin = new Scanner(System.in);
        int t, n;
        f[0] = BigInteger.ONE;
        for(int i = 1; i <= 1000; i++)             
          f[i] = f[i - 1].multiply(BigInteger.valueOf(i));         
          t = cin.nextInt();         
          while(t -- > 0) {
            ans = BigInteger.valueOf(0);
            total = 0;
            n = cin.nextInt();
            for(int i = 0; i < n; i ++) {
                a[i] = cin.nextInt();
                total += a[i];
            }
            for(int i = 1; i <= total; i ++) {
                int flag = 1;
                int k = total / gcd(i, total);
                int nn = 0;
                for(int j = 0; j < n; j ++) {
                    b[j] = a[j];
                }
                for(int j = 0; j < n; j ++) {
                    if(b[j] % k == 0) {
                        b[j] /= k;
                        nn += b[j];
                    }
                    else {
                        flag = 0;
                        break;
                    }
                }
                BigInteger sum = BigInteger.ONE;
                if(flag == 1) {
                    //System.out.println(i);
                    for(int j = 0; j < n; j ++) {
                        sum = sum.multiply(f[nn]);
                        sum = sum.divide(f[b[j]]);
                        sum = sum.divide(f[nn - b[j]]);
                        //System.out.println(sum);
                        nn -= b[j];
                    }
                    ans = ans.add(sum);
                }
            }
            ans = ans.divide(BigInteger.valueOf(total));
            System.out.println(ans);
        }
    }
}