HNOI2008 Cards

标签：数学 置换

---

题目描述

小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.
进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绿色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种.
Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).

输入输出格式

输入格式：
第一行输入 5 个整数：Sr,Sb,Sg,m,p(m<=60,m+1< p <100)。n=Sr+Sb+Sg。接下来 m 行，每行描述一种洗牌法，每行有 n 个用空格隔开的整数 X1X2…Xn，恰为 1 到 n 的一个排列，表示使用这种洗牌法，第 i位变为原来的 Xi位的牌。输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。
输出格式：
不同染法除以P的余数

输入输出样例

输入样例：
1 1 1 2 7
2 3 1
3 1 2
输出样例：
2

题解

对于这道题就不能用polya定理了（所以我就不知道怎么做了…）因为存在颜色数量的限制，不过对于题目这句话:数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。
因此它是满足置换群的性质的,因此我们可以用Burnside引理嘛，那么如何找不动点呢？其实就是每个循环节染相同颜色那么它肯定是一个不动点撒（由Burnside引理推polya定理也可以这么来推）因此我们可以dfs找出每种洗牌法的循环节及其长度,然后对于每种循环节染相同颜色。于是问题转换成把一些物品放到一些背包，直接DP即可了。

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N 100
#define ll long long
using namespace std;

int sr, sb, sg, p, n, m, cnt = 0;
int to[N], g[N];
ll f[N][N][N], ans = 0;
bool vis[N];

ll calc()
{
    memset(vis, false, sizeof(vis));
    memset(g, 0, sizeof(g));
    memset(f, 0, sizeof(f));
    cnt = 0; f[0][0][0] = 1;
    for(int i = 1; i <= n; i ++)
        if(!vis[i])
        {
            int x = i; cnt ++;
            while(!vis[x]) vis[x] = true, g[cnt] ++, x = to[x];
        }
    for(int i = 1; i <= cnt; i ++)
        for(int j = sr; j >= 0; j --)
            for(int k = sb; k >= 0; k --)
                for(int l = sg; l >= 0; l --)
                {
                    if(j >= g[i]) f[j][k][l] += f[j - g[i]][k][l], f[j][k][l] %= p;
                    if(k >= g[i]) f[j][k][l] += f[j][k - g[i]][l], f[j][k][l] %= p;
                    if(l >= g[i]) f[j][k][l] += f[j][k][l - g[i]], f[j][k][l] %= p;
                }
    return f[sr][sb][sg] % p;            
}

ll pow_mul(ll a, ll b, ll p)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

int main()
{
    scanf("%d%d%d%d%d", &sr, &sb, &sg, &m, &p);
    n = sr + sb + sg;
    for(int i = 1; i <= n; i ++) to[i] = i;
    ans = (ans + calc()) % p;
    for(int i = 1; i <= m; i ++)
    {
        for(int j = 1; j <= n; j ++) scanf("%d", &to[j]);
        ans = (ans + calc()) % p;
    }
    ans = ans * pow_mul(m + 1, p - 2, p) % p;
    printf("%lld", ans);
    return 0;
}

心得

区分polya定理和Burnsi适用范围,不过二者基本上都要找到循环节，所以如何优秀的找出循环节是解决这一类问题的关键。