Burnside/Polya+背包DP

---

　　这道题目是等价类计数裸题吧……>_>

　　题解：

　　啊其实重点还是：找出每个置换下的不动点数目

　　这道题比较特殊，牌的数量是限定的，所以只能DP来搞……（dp[R][G][B]表示的是R张红牌，G张绿牌，B张蓝牌在当前这个置换下，有多少种方案是会置换回自身的）

　　恒等置换单独处理一下即可（其实就是总染色数，多重集排列数吧……$\frac{N!}{R!G!B!}$）

　　最后除以m+1即可

P.S.因为是模意义下，所以所有的除法都是乘逆元。。。

1 /************************************************************** 2     Problem: 1004 3     User: Tunix 4     Language: C++ 5     Result: Accepted 6     Time:104 ms 7     Memory:1708 kb 8 ****************************************************************/ 9  10 //BZOJ 100411 #include
      
       12 #include
       
        13 #include
        
         14 #include
         
          15 #include
          
           16 #define rep(i,n) for(int i=0;i
           
            =n;--i)19 #define pb push_back20 using namespace std;21 typedef long long LL;22 inline int getint(){23 int r=1,v=0; char ch=getchar();24 for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1;25 for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch;26 return r*v;27 }28 const int N=110;29 /*******************template********************/30 int n,m,p,R,G,B;31 int f[N][N],c[N];32 int dp[N][30][30];33 34 int Pow(int a,int b,int P){35 int r=1;36 for(;b;b>>=1,a=a*a%P)37 if (b&1) r=r*a%P;38 return r;39 }40 bool vis[N];41 int main(){42 #ifndef ONLINE_JUDGE43 freopen("1004.in","r",stdin);44 freopen("1004.out","w",stdout);45 #endif46 R=getint(); B=getint(); G=getint(); m=getint(); p=getint();47 n=R+G+B;48 int sum=1,cnt=0,num;49 F(i,1,n) sum=(sum*i)%p;50 F(i,1,R) sum=(sum*Pow(i,p-2,p))%p;51 F(i,1,G) sum=(sum*Pow(i,p-2,p))%p;52 F(i,1,B) sum=(sum*Pow(i,p-2,p))%p;53 F(i,1,m) F(j,1,n) f[i][j]=getint();54 F(i,1,m){55 memset(vis,0,sizeof vis);56 memset(dp,0,sizeof dp);57 memset(c,0,sizeof c);58 cnt=0; 59 F(j,1,n) if (!vis[j]){60 int tmp=j,num=0;61 while(!vis[tmp]){62 vis[tmp]=1;63 tmp=f[i][tmp];64 num++;65 }66 c[++cnt]=num;67 }68 // printf("cnt=%d\n",cnt);69 // F(i,1,cnt) printf("%d ",c[i]); puts("");70 dp[0][0][0]=1;71 F(j,1,cnt) F(r,1,R) F(g,1,G) F(b,1,B){72 if (r>=c[j]) (dp[r][g][b]+=dp[r-c[j]][g][b])%=p;73 if (g>=c[j]) (dp[r][g][b]+=dp[r][g-c[j]][b])%=p;74 if (b>=c[j]) (dp[r][g][b]+=dp[r][g][b-c[j]])%=p;75 // printf("dp[%d][%d][%d]=%d\n",r,g,b,dp[r][g][b]);76 }77 sum=(sum+dp[R][G][B])%p;78 }79 sum=(sum*Pow(m+1,p-2,p))%p;80 printf("%d\n",sum);81 return 0;82 }
           
          
         
        
       
      

1004: [HNOI2008]Cards

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 2094  Solved: 1241

[][][]

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

[ ][ ][ ]