P1446 [HNOI2008]Cards
斯德哥尔摩
2018-07-29 20:59:00
[P1446 [HNOI2008]Cards](https://www.luogu.org/problemnew/show/P1446)
输入数据保证任意多次洗牌都可用这$m$种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。
所以每一种置换都是几个大小非1轮换的乘积。（若有1的话，那么就不能同时达到两个条件了，这是显然的）
所以没有一个置换（除原置换外）有不动点。
于是根据$Burnside$引理，答案可以这么算：
$$Ans=\frac{(red+blue+green)!}{red!*blue!*green!*(m+1)}$$
然后就是求个逆元即可。
注意到$p\in prime$，于是直接费马小定理即可。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 100
using namespace std;
long long red,blue,green,n,m,p,ans;
long long fact[MAXN],inv[MAXN];
inline long long read(){
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
long long mexp(long long a,long long b,long long c){
long long s=1;
while(b){
if(b&1)s=s*a%c;
a=a*a%c;
b>>=1;
}
return s;
}
void work(){
ans=fact[n]*inv[red]%p*inv[blue]%p*inv[green]%p*mexp(m+1,p-2,p)%p;
printf("%lld\n",ans);
}
void init(){
red=read();blue=read();green=read();m=read();p=read();
n=red+blue+green;
fact[0]=1;
for(int i=1;i<=n;i++){
fact[i]=fact[i-1]*i%p;
inv[i]=mexp(fact[i],p-2,p);
}
}
int main(){
init();
work();
return 0;
}
```
$Update\text{于}2019.3.23$：
据说这个公式只考虑了单位置换下的不动点数，很容易被卡掉。
$hack$数据长这个样：
```cpp
2 1 0 1 7
3 2 1
```
然后上面那个程序光荣$GG$。。。
怎么办呢？
考虑每一个循环，他们内部的位置的染色必须是相同的，所以单独考虑每个循环染那种颜色，可以通过一个类似背包的过程实现。
设$dp[red][blue][green]$表示三种颜色分别用了多少的方案数。
具体的状态转移方程见代码。
然后把每个置换的不动点数求和再乘上总置换数$(m+1)$的逆元即可。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 70
using namespace std;
int red,blue,green,n,m,num,size[MAXN];
long long p,ans,v[MAXN],dp[MAXN][MAXN][MAXN];
bool vis[MAXN];
inline long long read(){
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
long long mexp(long long a,long long b,long long c){
long long s=1;
while(b){
if(b&1)s=s*a%c;
a=a*a%c;
b>>=1;
}
return s;
}
long long solve(){
memset(vis,false,sizeof(vis));
memset(dp,0,sizeof(dp));
num=0;
for(int i=1;i<=n;i++)if(!vis[i]){
int x=i,len=0;
while(!vis[x]){
len++;
vis[x]=true;
x=v[x];
}
size[++num]=len;
}
dp[0][0][0]=1;
for(int x=1;x<=num;x++)
for(int i=red;i>=0;i--)
for(int j=blue;j>=0;j--)
for(int k=green;k>=0;k--){
if(i>=size[x])dp[i][j][k]=(dp[i][j][k]+dp[i-size[x]][j][k])%p;
if(j>=size[x])dp[i][j][k]=(dp[i][j][k]+dp[i][j-size[x]][k])%p;
if(k>=size[x])dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-size[x]])%p;
}
return dp[red][blue][green];
}
void work(){
red=read();blue=read();green=read();m=read();p=read();
n=red+blue+green;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)v[j]=read();
ans=(ans+solve())%p;
}
for(int i=1;i<=n;i++)v[i]=i;
ans=(ans+solve())%p;
printf("%lld\n",ans*mexp(m+1,p-2,p)%p);
}
int main(){
work();
return 0;
}
```