首页 > 其他 > 详细

HNOI2008 Cards

时间:2018-08-18 10:06:15      阅读:166      评论:0      收藏:0      [点我收藏+]

传送门

ovo这其实是一道置换 + DP的题,不过蒟蒻已经快忘了置换怎么做了……

或许这道题使用组合数的方法更容易一些。

我们先考虑一下,满足题目中各种卡牌颜色要求的染色个数一共有多少种,这个很显然,是C(n,sr)*  C(n - sr,sb) * C(n-sr-sb,sg)(后面那项结果就是1其实)

之后,题目中提到,保证任意多次洗牌都可用这 m种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

也就是说,对于一种状态A,有另外m中状态能够由它变来(自然也能由这些状态变回A),而其他的状态则不能从A变来。因为任意多次洗牌都可以用m种之一替代,所以肯定是可以从A这种状态再变出来m种的。

而我们再考虑,如果A能够变成一种状态B,它不属于这m+1种状态之一,但是根据题目描述,它一定是可以变回A,转变成了A,就可以转换为其他状态,这与它原来不在这m+1中状态中是矛盾的。

所以,在这些染色方法中,每m+1中染色方式是被绑定在一起的,是本质相同的,所以计算出来染色总数除以(m+1)即为结果。

先处理出来阶乘和阶乘的逆元就可以了。

 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rep(i,a,n) for(ll i = a;i <= n;i++)
#define per(i,n,a) for(ll i = n;i >= a;i--)
#define enter putchar(‘\n‘)

using namespace std;
const int M = 105;
typedef long long ll;

ll read()
{
    ll ans = 0,op = 1;
    char ch = getchar();
    while(ch < 0 || ch > 9)
    {
        if(ch == -) op = -1;
        ch = getchar();
    }
    while(ch >= 0 && ch <= 9)
    {
        ans *= 10;
        ans += ch - 0;
        ch = getchar();
    }
    return ans * op;
}
ll qpow(ll a,ll b,ll mod)
{
    ll q = 1;
    while(b)
    {
        if(b&1) q *= a,q %= mod;
        a *= a,a %= mod;
        b >>= 1;
    }
    return q % mod;
}
ll m,n,inv[M],sum[M],p,sr,sb,sg;
ll C(ll a,ll b)
{
    return sum[a] * inv[b] * inv[a-b] % p;
}
int main()
{
    inv[0] = 1,sum[0] = 1,inv[1] = 1;
    sr = read(),sb = read(),sg = read(),m = read(),p = read();
    n = sr+sb+sg;
    rep(i,1,p-1) sum[i] = sum[i-1] * i % p;
    inv[p-1] = qpow(sum[p-1],p-2,p);
    per(i,p-1,2) inv[i-1] =  inv[i] * i % p;
    printf("%lld\n",C(n,sr) * C(n-sr,sb) * qpow(m+1,p-2,p) % p);
    return 0;
}

 

 

 

 

 

 

HNOI2008 Cards

原文:https://www.cnblogs.com/captain1/p/9495990.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!