vfleaking的博客

Description

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

第一行输入五个整数:Sr,Sb,Sg,M,P(M<=60,M+1

<100). 
N=Sr+Sb+Sg.接下来M行,每行描述一种洗牌法,每行有N个用空格隔开的整数X1X2...Xn. 
恰为1到N的一个排列,表示使用这种洗牌法,第I位变成原来的Xi位的牌. 
输入数据保证任意多次洗牌都可以用M种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到 
原状态. 
20%的数据保证Sr+Sb+Sg<=20 
100%的数据保证Max(Sr,Sb,Sg)<=20

Input

第一行输入五个整数:Sr,Sb,Sg,M,P(M<=60,M+1

<100).N=Sr+Sb+Sg. 
接下来M行,每行描述一种洗牌法,每行有N个用空格隔开的整数X1X2...Xn. 
恰为1到N的一个排列,表示使用这种洗牌法,第I位变成原来的Xi位的牌. 
输入数据保证任意多次洗牌都可以用M种洗牌法中的一种代替,且对每种洗牌法 
都存在一种洗牌法使得能回到原状态. 
20%的数据保证Sr+Sb+Sg<=20 
100%的数据保证Max(Sr,Sb,Sg)<=20

Output

不同染法除以P的余数 

Sample Input

1 1 1 2 7
2 3 1
3 1 2

Sample Output

2

Hint

有2 种本质上不同的染色法RGB 和RBG，使用洗牌法231 一次可得GBR 和BGR，使用洗牌法312 一次 
可得BRG 和GRB。 

 我做这道题的时候，不知道什么是Polya和Burnside，于是学了N多数学知识……学完发现原来这题只是一道基础题……

 我来上一堂数学课吧。

【群】给定一个集合G={a,b,c,…}和集合G上的二元运算*，并满足：

1.封闭性：对于所有的a,b∈G，存在一个c∈G，使得a*b=c

2.结合律：对于所有的a,b,c∈G，满足(a*b)*c=a*(b*c)

3.单位元：存在e∈G，对于所有的a∈G，满足a*e=e*a=a

4.逆元：对于所有a∈G，存在b∈G，a*b=b*a=e，记作

则称集合G在运算“*”之下是一个群，记作(G,*)。一般a*b简写成ab。

呃……简单来说群就是集合加运算符。比如(有理数集,+)就是一个群，念作有理数加法群。

不懂可以问维基，似乎说得挺清楚：http://en.wikipedia.org/wiki/Group_(mathematics)

【置换】n个元素1,2,…,n之间的一个置换为

表示1被1到n中某个数a1取代，2被1到n中某个数a2取代……n被1到n中某个数an取代。（a1、a2、a3…an互不相同）

举个例子：

这是一个置换。1 2 3 4 5经过置换后变成2 5 4 3 1。而9 0 1 4 5经过置换后变成0 5 4 1 9。

不懂可以问维基，似乎说得挺清楚：http://en.wikipedia.org/wiki/Permutation

 【置换群】置换群的元素是置换，运算是置换的连接。例如：

 

 置换群的封闭性和逆元会在题目中强调（不然就是不可捉题……），结合律嘛……哎呀……好像是显然耶……，单位元是，这家伙叫做恒等置换。

 【循环】呃……这里的循环不是for啊，while啊那两个老家伙……呃……我语文不好……说不清楚定义……我就说我的理解吧……

 想象一个N个节点的图，对于一个置换s，如果第i个元素经过置换后变为了第j个元素，那么就把第i号点和第j号点相连。发现了什么？形成了许多环对不对！那就叫循环。一个置换可以表示成若干个不相交的循环。比如：可以用循环表示成：(125)(34)，就是刚才所说图中，1、2、5号点成一个环，3、4成一个环。表示一个循环时，(345) ≠ (435)，但(345) = (453)（这个能理解吧……）。刚才所说的那个置换，既可以表示成(125)(34)，也可以表示成(34)(125)。

 

 好，现在Burnside引理闪亮登场……这个引理的中文名叫伯恩赛德引理。

 不多说，先上公式：

 

 等式左边表示置换群G在有限集合X作用下等价类的数目（如本题中的本质不同的方案数），等式右边是指(sum(经g的狂风骤雨般变幻后，X中仍旧不改变的元素的个数) (g∈G) ) ÷ G中元素的个数。好吧……这句话有点绕……我们记X中经过G[i]的作用后仍旧为没有变化的元素个数为d(i)，比如X中若有元素（红，红，蓝），那么置换(12)(3)想把它变个样子，是不可能的，因为红与红交换仍然是红和红，miss了……而（红，蓝，黄）则瞬间被置换(123)秒杀成（蓝，黄，红）……变得不成样子了。那么置换群G在有限集合X作用下等价类的数目等于d(1),d(2),d(3)...d(n)的平均数。（n为G中元素的个数）啊啊啊啊啊……我也不知道我说清楚没……没看懂的见谅……

 那么，对于本题，洗牌法就是咱们的置换，依据题目的特殊条件（题目中强调了群的封闭性和逆元，衡阳八中坑爹，题目不打全……），我们可以把所有洗牌法构成一个置换群，然后用上面的公式来求解。

 好像有公式就万能了耶……这道题就可以水过了耶……

 其实咱们忽略的一个挺烦人的函数：d(i)。咱们是要求G中所有置换的d值的平均值，但是d怎么求呢？

 答案就是……DP……具体见http://hi.baidu.com/aekdycoin/blog/item/4f66126149ba5b4febf8f8bd.html吧……

 AekdyCoin说要用乘法逆元……我表示我完全没有用诶……我定义了一个struct叫tempint，记录商和余数，然后各种YY……详见代码……

 代码：（小心观看！）

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int x[100];
vector<int> v;
int nr, nb, ng, m, p;
int n;

struct tempint
{
    int shang;
    int ys;
    
    tempint()
    {
        shang = 0;
        ys = 0;
    }
    
    tempint(int mshang, int mys)
    {
        shang = mshang;
        ys = mys;
    }
    
    inline tempint operator+(tempint ti)
    {
        tempint res;
        res.ys = ys + ti.ys;
        res. shang = (shang + ti.shang + res.ys / (m + 1)) % p;
        res.ys %= m + 1;
        
        return res;
    }
};

tempint f[30][30][30];
tempint getsum()
{
    v.clear();
    bool book[100] = {false};
    
    for (int i = 1; i <= n; i++)
    {
        if (!book[i])
        {
            book[i] = true;
            
            if (i == x[i])
                v.push_back(1);
            else
            {
                int sum = 1;
                int index = x[i];
                
                while (index != i)
                {
                    sum++;
                    book[index] = true;
                    
                    index = x[index];
                }
                v.push_back(sum);
            }
        }
    }
    
    for (int i = 0; i <= nr; i++)
    {
        for (int j = 0; j <= ng; j++)
        {
            for (int k = 0; k <= nb; k++)
                f[i][j][k] = tempint();
        }
    }
    f[0][0][0] = tempint(0, 1);
    for (vector<int>::iterator l = v.begin(); l != v.end(); l++)
    {
        for (int i = nr; i >= 0; i--)
        {
            for (int j = ng; j >= 0; j--)
            {
                for (int k = nb; k >= 0; k--)
                {
                    if (i >= *l)
                        f[i][j][k] = f[i][j][k] + f[i - *l][j][k];
                    if (j >= *l)
                        f[i][j][k] = f[i][j][k] + f[i][j - *l][k];
                    if (k >= *l)
                        f[i][j][k] = f[i][j][k] + f[i][j][k - *l];
                }
            }
        }
    }
    return f[nr][ng][nb];
}

int main()
{
    freopen("1004.in", "r", stdin);
    freopen("1004.out", "w", stdout);
    
    cin >> nr >> nb >> ng >> m >> p;
    n = nr + nb + ng;
    
    tempint res;
    
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
            scanf("%d", &x[j]);
        res = res + getsum();
    }
    
    for (int i = 1; i <= n; i++)
        x[i] = i;
    res = res + getsum();
    cout << res.shang << endl;
    
    return 0;
}