2018.09.19 atcoder Card Game for Three(组合数学)
2024-09-17 08:37:16
传送门
简单组合数学想优化想了半天啊233。
我们只需考虑翻开n张A,b张B,c张C且最后一张为A的选法数。
显然还剩下m+k−b−cm+k-b-cm+k−b−c张牌没有选。
这样的话无论前n+b+cn+b+cn+b+c张牌怎么选,方案数会乘上一个3m+k−b−c3^{m+k-b-c}3m+k−b−c。
继续讨论。
我们应该从前n+b+c−1n+b+c-1n+b+c−1中选出n−1n-1n−1个A(因为最后一个一定是A)。
剩下的要么是B要么是C。
我们不妨令b+c=i。
那么有:
ans=∑(i=0m+k3m+k−i(n+i−1n−1)∑[b+c=i],b≤m,c≤k)(ib)ans=\sum( _{i=0} ^{m+k} 3^{m+k-i}\binom {n+i-1} {n-1}\sum _{[b+c=i],b\le m,c\le k}) \binom {i} {b}ans=∑(i=0m+k3m+k−i(n−1n+i−1)∑[b+c=i],b≤m,c≤k)(bi)
然后发现前面的一坨都不能优化。
只能在最后一部分做文章。
所以如何优化?
发现我们从i变到i+1的过程相当于杨辉三角向下移动一行的情况。
因此讨论一下边界分情况转移就行了。
代码:
#include<bits/stdc++.h>
#define N 300005
#define mod 1000000007
#define ll long long
using namespace std;
ll up,n,m,k;
ll ans=0,fac[N*3],ifac[N*3],mul[N*3];
inline ll calc(int a,int b){return fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
inline ll ksm(ll x,int p){
ll ret=1;
while(p){
if(p&1)ret=ret*x%mod;
x=x*x%mod,p>>=1;
}
return ret;
}
int main(){
cin>>n>>m>>k,up=n+m+k,fac[0]=mul[0]=ifac[1]=ifac[0]=1;
for(ll i=2;i<=up;++i)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod;
for(ll i=1;i<=up;++i)mul[i]=mul[i-1]*3%mod,(ifac[i]*=ifac[i-1])%=mod,fac[i]=fac[i-1]*i%mod;
if(m<k)m^=k,k^=m,m^=k;
for(ll i=0,j=1;i<=m+k;++i){
(ans+=calc(n-1+i,n-1)*mul[m+k-i]%mod*j%mod)%=mod;
if(i<k)(j<<=1)%=mod;
else if(i>=m)(j+=j-calc(i,k)-calc(i,i-m))%=mod;
else (j+=j-calc(i,k))%=mod;
}
cout<<(ans+mod)%mod;
return 0;
}
最新文章
- 摘:JavaScript性能优化小知识总结
- js方法之间的调用之——传参方法
- APNS IOS PHP 苹果推送
- C# 数组,ArrayList与List对象的区别
- 【bzoj1003】[ZJOI2006]物流运输
- 对于requirejs AMD模块加载的理解
- UILabel的各种属性与方法的使用
- CentOS搭建GIT服务器【二】-HTTP源码访问及smart http协议
- DOM不同的结点类型
- WPF中当鼠标移到按钮上时,按钮的背景图片消失的问题
- java中 this 的三种用法
- web程序员标准环境之DreamWeaver【推荐】
- poj2029 Get Many Persimmon Trees
- 为什么PPIO要设计支付代理节点?
- supervisor学习
- LoadRunner脚本参数化之设置条件与运行结果说明
- linux vue uwsgi nginx 部署路飞学城 安装 vue
- 数列分块入门九题(二):LOJ6280~6282
- flask设置cookie,设置session,模拟用户认证、模拟管理后台admin、模拟用户logout
- 走进异步编程的世界--async/await项目使用实战