注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

1004: [HNOI2008]Cards  

2012-02-22 23:03:26|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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,记作1004: [HNOI2008]Cards - vfleaking - vfleaking的博客

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

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

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

【置换】n个元素1,2,…,n之间的一个置换为 1004: [HNOI2008]Cards - vfleaking - vfleaking的博客

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

举个例子:

1004: [HNOI2008]Cards - vfleaking - vfleaking的博客

这是一个置换。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

 置换群置换群的元素是置换,运算是置换的连接。例如:

 1004: [HNOI2008]Cards - vfleaking - vfleaking的博客

 置换群的封闭性和逆元会在题目中强调(不然就是不可捉题……),结合律嘛……哎呀……好像是显然耶……,单位元是1004: [HNOI2008]Cards - vfleaking - vfleaking的博客,这家伙叫做恒等置换。

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

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

 

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

 不多说,先上公式:

 1004: [HNOI2008]Cards - vfleaking - vfleaking的博客

 等式左边表示置换群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 = 1i <= 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 = 0i <= nri++)
    {
        for (int j = 0j <= ngj++)
        {
            for (int k = 0k <= 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 = nri >= 0i--)
        {
            for (int j = ngj >= 0j--)
            {
                for (int k = nb; k >= 0k--)
                {
                    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 = 1i <= mi++)
    {
        for (int j = 1j <= n; j++)
            scanf("%d", &x[j]);
        res = res + getsum();
    }
    
    for (int i = 1i <= n; i++)
        x[i] = i;
    res = res + getsum();
    cout << res.shang << endl;
    
    return 0;
}

  评论这张
 
阅读(1864)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017