【BZOJ】【1004】【HNOI2008】Cards

时间:2023-03-10 06:23:38
【BZOJ】【1004】【HNOI2008】Cards

Burnside/Polya+背包DP


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

  题解:http://m.blog.****.net/blog/njlcazl_11109/8316340

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

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

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

  最后除以m+1即可

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

 /**************************************************************
Problem: 1004
User: Tunix
Language: C++
Result: Accepted
Time:104 ms
Memory:1708 kb
****************************************************************/ //BZOJ 1004
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/
int n,m,p,R,G,B;
int f[N][N],c[N];
int dp[N][][]; int Pow(int a,int b,int P){
int r=;
for(;b;b>>=,a=a*a%P)
if (b&) r=r*a%P;
return r;
}
bool vis[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("1004.in","r",stdin);
freopen("1004.out","w",stdout);
#endif
R=getint(); B=getint(); G=getint(); m=getint(); p=getint();
n=R+G+B;
int sum=,cnt=,num;
F(i,,n) sum=(sum*i)%p;
F(i,,R) sum=(sum*Pow(i,p-,p))%p;
F(i,,G) sum=(sum*Pow(i,p-,p))%p;
F(i,,B) sum=(sum*Pow(i,p-,p))%p;
F(i,,m) F(j,,n) f[i][j]=getint();
F(i,,m){
memset(vis,,sizeof vis);
memset(dp,,sizeof dp);
memset(c,,sizeof c);
cnt=;
F(j,,n) if (!vis[j]){
int tmp=j,num=;
while(!vis[tmp]){
vis[tmp]=;
tmp=f[i][tmp];
num++;
}
c[++cnt]=num;
}
// printf("cnt=%d\n",cnt);
// F(i,1,cnt) printf("%d ",c[i]); puts("");
dp[][][]=;
F(j,,cnt) F(r,,R) F(g,,G) F(b,,B){
if (r>=c[j]) (dp[r][g][b]+=dp[r-c[j]][g][b])%=p;
if (g>=c[j]) (dp[r][g][b]+=dp[r][g-c[j]][b])%=p;
if (b>=c[j]) (dp[r][g][b]+=dp[r][g][b-c[j]])%=p;
// printf("dp[%d][%d][%d]=%d\n",r,g,b,dp[r][g][b]);
}
sum=(sum+dp[R][G][B])%p;
}
sum=(sum*Pow(m+,p-,p))%p;
printf("%d\n",sum);
return ;
}

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

2

HINT

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

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

Source

[Submit][Status][Discuss]