锐客网

  1. 首页 > it技术 > >

【组合计数】ARC061F Card Game for Three

数论

题意：
有三堆卡牌，牌数分别为N,M,K
每张牌有一个字母（’a’、’b’、’c’）表示下一个拿哪一堆。
现在要求第一堆首先拿完。求方案数。
分析：
首先，这道题有很多角度可以入手。但最简单的方法是，根据拿的牌的类型计算。
如果第一堆拿完，则拿的顺序中必然有n个a，且b的数量比m小，c的数量比k小。
但是最后一个必须限定为a，所以这部分拿了的方案数应为 Cn?1n?1+iC n ? 1 + i n ? 1 (i表示多拿的b和c的总和)
然后还要从这i个中选哪些是b，哪些是c，所以还要乘上 ∑0≤x 所以有如下式子：
Ans=∑i 然后这就可以拿所谓的部分分了。
【【组合计数】ARC061F Card Game for Three】接下来一般来说都会想怎么改进式子，然而。。。这道题的方法是，直接枚举前半部分(即i的大小)，想办法快速转移后半部分。
后半部分可以分三种情况讨论(设 k≤mk ≤ m ):
注：下面x表示的是拿c的个数
1、 ∑x≤ix=0Cxi(i 2、 ∑x 3、 ∑x 考虑优化转移。在第一种情况下，i变为i+1，只需要把总和乘2即可。
在第二种情况下，i变为i+1，把总和乘以2再减去 CkiC i k
在第三种情况下，i变为i+1，把总和乘以2再减去 Cki+CmiC i k + C i m
用杨辉三角的性质来解释就很容易了。

#include #include #include #include #define SF scanf #define PF printf #define MAXN 900010 #define MOD 1000000007 using namespace std; typedef long long ll; ll inv[MAXN],fac[MAXN],pow3[MAXN]; ll fsp(ll x,int y){ ll res=1; while(y){ if(y&1) res=res*x%MOD; x=x*x%MOD; y>>=1; } return res; } ll C(int x,int y){ return fac[x]*inv[y]%MOD*inv[x-y]%MOD; } int main(){ int n,m,k; SF("%d%d%d",&n,&m,&k); pow3[0]=1; fac[0]=1; for(int i=1; i<=n+m+k; i++){ pow3[i]=pow3[i-1]*3ll%MOD; fac[i]=fac[i-1]*i%MOD; } inv[n+m+k]=fsp(fac[n+m+k],MOD-2); for(int i=n+m+k; i>0; i--) inv[i-1]=inv[i]*i%MOD; n--; if(m

    推荐阅读


    上一篇：Android|Android 补间动画（动画列表,平移，旋转，缩放，渐变，动画集合）

    下一篇：Android属性动画特性