[HNOI2008]Cards （polya定理+乘法逆元，費馬小定理）

1004: [HNOI2008]Cards

Time Limit: 10 Sec   Memory Limit: 162 MB

Submit: 2429   Solved: 1423

[ Submit][ Status][ Discuss]

Description

小春現在很清閑,面對書桌上的N張牌,他決定給每張染色,目前小春隻有3種顔色:紅色,藍色,綠色.他詢問Sun有多少種染色方案,Sun很快就給出了答案.進一步,小春要求染出Sr張紅色,Sb張藍色,Sg張絕色.他又詢問有多少種方案,Sun想了一下,又給出了正确答案. 最後小春發明了M種不同的洗牌法,這裡他又問Sun有多少種不同的染色方案.兩種染色方法相同當且僅當其中一種可以通過任意的洗牌法(即可以使用多種洗牌法,而每種方法可以使用多次)洗成另一種.Sun發現這個問題有點難度,決定交給你,答案可能很大,隻要求出答案除以P的餘數(P為質數).

Input

第一行輸入 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種洗牌法中的一種代替，且對每種

洗牌法，都存在一種洗牌法使得能回到原狀态。

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。

100%資料滿足 Max{Sr,Sb,Sg}<=20。

Source

[ Submit][ Status][ Discuss] 

HOME   Back

解析：這道題用到的定理就是burnside定理與polya定理，這兩個定理自己去看（http://wenku.baidu.com/view/bf92a95f804d2b160b4ec0be.html），這裡不再細述，我就簡要說一下做法。

第一步：polya定理求解方案數L

      其中，|G|代表置換個數（這裡要加一個置換：1 2 。。。 n，是以|G|=m+1)，D(ai)表示在置換aj下不變的元素的個數。

       下面簡要說一下如何求解D(ai)：

        1.對于置換ai，求解其循環數s[0]以及每個循環的長度s[i]。

          比如：1 2 3 4  

                     2 3 1 4  

          有兩個循環（1,2,3）（4）。

         2.用f[i][j][k]表示對于前 x 個循環，使用 i 個sr，j個sb，k個sg能夠得到的不同方案數，則：

                f[i][j][k]=f[i-s[x]][j][k]+f[i][j-s[x]][k]+f[i][j][k-s[x]] (每個循環内的顔色相同)

            D(ai)=f[sr][sb][sg]；

第二步：乘法逆元取模

 根據費馬小定理，若p未知數，那麼a^(p-1)%p=1。

L%p=(D(a1)%p+..+D(a|G|)%p) * (|G|)^(-1) %p

       =(D(a1)%p+..+D(a|G|)%p) * (|G|)^(-1) *(|G|)^(p-1) %p

       =(D(a1)%p+..+D(a|G|)%p) * (|G|)^(p-2) %p

其他的自己看代碼就能懂了，有疑問的在提吧。

代碼：

#include<cstdio>
#include<cstring>
#define ms(a) memset(a,0,sizeof(a)) 
using namespace std;

const int maxn1=20;
const int maxn2=60;
int sr,sb,sg,m,p,sum;
int a[maxn2+10],s[maxn2+10];
bool used[maxn2+10];
int f[maxn1+10][maxn1+10][maxn1+10];

void circle()
{
  int i,j;
  ms(used),ms(s);
  for(i=1;i<=sum;i++)if(!used[i])
    {
      s[++s[0]]=1,used[i]=1,j=a[i];
      while(!used[j])used[j]=1,j=a[j],s[s[0]]++;
	}
}

int dp()
{
  ms(f);
  int x,i,j,k;
  f[0][0][0]=1;
  for(x=1;x<=s[0];x++)
    for(i=sr;i>=0;i--)
      for(j=sb;j>=0;j--)
        for(k=sg;k>=0;k--)
          {
            if(i>=s[x])f[i][j][k]+=f[i-s[x]][j][k];
            if(j>=s[x])f[i][j][k]+=f[i][j-s[x]][k];
            if(k>=s[x])f[i][j][k]+=f[i][j][k-s[x]];
            f[i][j][k]%=p;
		  }
  return f[sr][sb][sg];
}

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

int main()
{
  //freopen("1.in","r",stdin);
  int i,ans;
  scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p);
  sum=sr+sb+sg;
  for(i=1;i<=sum;i++)a[i]=i;
  circle(),ans=dp();
  for(i=1;i<=m;i++)
    {
      for(i=1;i<=sum;i++)scanf("%d",&a[i]);
      circle(),ans=(ans+dp())%p;
	}
  ans=ans*pow_mod(m+1,p-2)%p;
  printf("%d\n",ans);
  return 0;
}