【BZOJ】【1004】【HNOI2008】Cards

Burnside/Polya+背包DP

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

　　题解：http://m.blog.csdn.net/blog/njlcazl_11109/8316340

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

　　这道题比较特殊，牌的数量是限定的，所以只能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 1004
11 #include<cstdio>
12 #include<cstring>
13 #include<cstdlib>
14 #include<iostream>
15 #include<algorithm>
16 #define rep(i,n) for(int i=0;i<n;++i)
17 #define F(i,j,n) for(int i=j;i<=n;++i)
18 #define D(i,j,n) for(int i=j;i>=n;--i)
19 #define pb push_back
20 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_JUDGE
43     freopen("1004.in","r",stdin);
44     freopen("1004.out","w",stdout);
45 #endif
46     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
",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
",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
",sum);
81     return 0;
82 }

View Code

1004: [HNOI2008]Cards

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2094 Solved: 1241
[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

HINT

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

100%数据满足 Max{Sr,Sb,Sg}<=20。

Source

[Submit][Status][Discuss]