1004: [HNOI2008]Cards
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1057 Solved: 613
[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種洗牌法中的一種代替，且對每種
洗牌法，都存在一種洗牌法使得能回到原狀態。
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。
置換群：可以看成本題所有的g[i]數列+不洗牌數列
置換性質：任意的置換都能由置換中的置換湊出（如果置換群U中存在：A.順時針旋轉90°，那麼B：順時針旋轉180°也在U中）
等價情況：2種情況被認為是同構的，或者只計算一遍的。
根據burnside定理：
一個置換群的等價計數=∑置換i（置換後等價情況數）/置換總數
根據Polya定理：
一個情況是置換等價情況，當且僅當每個循環節的內部兩兩相同 於是得到C(i)=k^m{k} m(k)為循環節長度
本題轉化為在k個循環節中填入若干顏色，使3種顏色對應相等
那麼背包各種Dp……
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXN (60+10)
#define MAXN (100+10)
int g[MAXN],sr,sb,sg,m,F,n;
int exgcd(int a,int b,int&x,int &y)
{
if (!b) {x=1,y=0;return a;}
int g=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-(a/b)*y;
return g;
}
int inv(int a)
{
int x,y;
int g=exgcd(a,F,x,y);
return g==1?(x+F)%F:-1;
}
int st[MAXN],size=0,sum[MAXN]={0},id[MAXN]={0};
bool b[MAXN];
int f[MAXN/3][MAXN/3][MAXN/3];
int C()
{
size=0;memset(b,0,sizeof(b));memset(id,0,sizeof(id));
For(i,n)
if (!b[i])
{
int ans=0;
while (!b[g[i]]) i=g[i],b[i]=1,ans++;
//i=g[i];
st[++size]=ans;sum[size]=sum[size-1]+st[size];id[sum[size]]=size;
}
// For(i,size) cout<<st[i]<<' ';puts("");
memset(f,0,sizeof(f));f[0][0][0]=1;
Rep(i,sr+1) Rep(j,sb+1) Rep(k,sg+1)
if (id[i+j+k])
{
int v=st[id[i+j+k]];
if (i-v>=0) f[i][j][k]=(f[i][j][k]+f[i-v][j][k])%F;
if (j-v>=0) f[i][j][k]=(f[i][j][k]+f[i][j-v][k])%F;
if (k-v>=0) f[i][j][k]=(f[i][j][k]+f[i][j][k-v])%F;
}
return f[sr][sb][sg];
}
int main()
{
// freopen("bzoj1004.in","r",stdin);
scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&F);n=sr+sb+sg;
int ans=0;
For(i,m)
{
For(j,n) scanf("%d",&g[j]);
ans=(ans+C())%F;
}
For(j,n) g[j]=j;
ans=(ans+C())%F;
ans=ans*inv(m+1)%F;
cout<<ans<<endl;
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXN (60+10)
#define MAXN (100+10)
int g[MAXN],sr,sb,sg,m,F,n;
int exgcd(int a,int b,int&x,int &y)
{
if (!b) {x=1,y=0;return a;}
int g=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-(a/b)*y;
return g;
}
int inv(int a)
{
int x,y;
int g=exgcd(a,F,x,y);
return g==1?(x+F)%F:-1;
}
int st[MAXN],size=0,sum[MAXN]={0},id[MAXN]={0};
bool b[MAXN];
int f[MAXN/3][MAXN/3][MAXN/3];
int C()
{
size=0;memset(b,0,sizeof(b));memset(id,0,sizeof(id));
For(i,n)
if (!b[i])
{
int ans=0;
while (!b[g[i]]) i=g[i],b[i]=1,ans++;
//i=g[i];
st[++size]=ans;sum[size]=sum[size-1]+st[size];id[sum[size]]=size;
}
// For(i,size) cout<<st[i]<<' ';puts("");
memset(f,0,sizeof(f));f[0][0][0]=1;
Rep(i,sr+1) Rep(j,sb+1) Rep(k,sg+1)
if (id[i+j+k])
{
int v=st[id[i+j+k]];
if (i-v>=0) f[i][j][k]=(f[i][j][k]+f[i-v][j][k])%F;
if (j-v>=0) f[i][j][k]=(f[i][j][k]+f[i][j-v][k])%F;
if (k-v>=0) f[i][j][k]=(f[i][j][k]+f[i][j][k-v])%F;
}
return f[sr][sb][sg];
}
int main()
{
// freopen("bzoj1004.in","r",stdin);
scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&F);n=sr+sb+sg;
int ans=0;
For(i,m)
{
For(j,n) scanf("%d",&g[j]);
ans=(ans+C())%F;
}
For(j,n) g[j]=j;
ans=(ans+C())%F;
ans=ans*inv(m+1)%F;
cout<<ans<<endl;
return 0;
}
