洛谷 P1446 [HNOI2008]Cards 解题报告

P1446 [HNOI2008]Cards

题目描述

小春现在很清闲,面对书桌上的(N)张牌,他决定给每张染色,目前小春只有(3)种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.

进一步,小春要求染出(S_r)张红色,(S_b)张蓝色,(S_g)张绿色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了(M)种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种.

Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以(P)的余数((P)为质数).

输入输出格式

输入格式：

第一行输入 (5) 个整数：(S_r,S_b,S_g,m,p(mle 60,m+1<p<100))。(n=S_r+S_b+S_g)。接下来 (m) 行，每行描述一种洗牌法，每行有 (n) 个用空格隔开的整数 (X_1X_2dots X_n)，恰为 (1) 到 (n) 的一个排列，表示使用这种洗牌法，第 (i) 位变为原来的 (X_i) 位的牌。输入数据保证任意多次洗牌都可用这 (m) 种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

(100\%)数据满足 (max{S_r,S_b,S_g}le 20)。

输出格式：

不同染法除以(P)的余数

其实这个题的(DP)做法应该就是官方正解了，思维难度并不高。

很显然是变换构成了一个群

考虑(polya)定理

[frac{1}{|G|}sum_{pi in G}m^{w(pi)} ]

然后因为每个循环节同色，我们可以直接求循环节然后(dp)

注意单位元不给，要自己加上

还有一种比较神奇的做法，发现这个题还给了除群外的一个性质，然后可以得到一个结论，仅单位元有不动点，然后(Burnside)直接组合算就可以了，答案就是

[frac{(a+b+c)!}{a!b!c!(m+1)} ]

然后我并不会证，比较严谨的描述如下，如果谁可以给出证明，烦请私信我一下啦

设(G={pi_1,pi_2,dots,pi_p})是目标集([1,n])上的置换群，且(forall t=sum pi_k,pi_k in G)，定义(sum)为置换的连接操作，且(k)可重，(exists t in G)，求证仅(G)的单位元存在不动点。

Code:

#include <cstdio>
const int N=201;
#define mul(a,b) (1ll*(a)*(b)%mod)
int a,b,c,m,mod,fac[N];
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d);k>>=1;}return f;}
int main()
{
    scanf("%d%d%d%d%d",&a,&b,&c,&m,&mod);
    for(int x,i=1;i<=m;i++)
        for(int j=1;j<=a+b+c;j++)
            scanf("%d",&x);
    fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=mul(fac[i-1],i);
    int ans=mul(fac[a+b+c],mul(qp(fac[a],mod-2),mul(qp(fac[b],mod-2),mul(qp(fac[c],mod-2),qp(m+1,mod-2)))));
    printf("%d
",ans);
    return 0;
}

2018.12.21