【HNOI2008】Cards

题意

??有$n$张牌，可以染成红，蓝，绿三种颜色，并且每种颜色的牌的数目有规定，分别为$s_r，s_b，s_g$（保证$s_r+s_b+s_g=n$）
??同时有$m+1$个置换（$m$洗牌方法+不洗牌），两种染色方案不同当且仅当这两方案不能通过$m+1$个置换变成一样
??问染色方案模$p$的余数
$n≤60，m＜p≤100，max${ $s_r，s_b，s_g$}$≤20，p为质数$

解法

??很容易得到$Ans=\dfrac{总方案数}{重复度}$
??总方案数很容易求，$Tot=C_{n}^{s_r}*C_{n-s_r}^{s_b}*C_{n-s_r-s_b}^{s_g}$
??至于求重复度，考虑到每一种方案都可以通过$m$种置换变成$m$种方案，加上自己就是$m+1$种，所以直接乘以$m+1$的逆元即可

复杂度

O（$n+logp$）

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Rint register int
#define Lint long long int
using namespace std;
int n,sr,sb,sg,m,p;
int fac[100],ans;
int pow(int x)
{int ret=1,k=p-2;while( k ){if( k&1 )   ret=ret*x%p;x=x*x%p,k/=2;}return ret;
}
int C(int n,int m)
{return fac[n]*pow( fac[m] )%p*pow( fac[n-m] )%p;
}
int main()
{scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p);n=sr+sb+sg,fac[0]=1;for(int i=1;i<=n;i++)   fac[i]=fac[i-1]*i%p;ans=C( n,sr )*C( n-sr,sb )%p*C( n-sr-sb,sg )%p*pow( m+1 )%p;printf("%d\n",ans%p);return 0;
}