注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[Codeforces #258 Div.2]Devu and Flowers  

2014-09-17 17:16:34|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题意:
给你n个Box,每个里面装了f[i]朵花,每个Box里的花被认为是相同的,你需要从中挑出恰好s朵花,问方案数,答案模1e9+7
n<=20,s<=10^14
f[i]<=10^12

这场cf打了一次vp
前面题还都可做,最后被这题卡了
感谢GTY神犇指导
按照惯例题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 25;
const LL MOD = 1e9+7;
LL n,m,data[N];
LL pow(LL a,LL k){
LL re = 1;
for(;k;k/=2,a=(a*a)%MOD)
if(k&1) re=(re*a)%MOD;
return re;
}
LL scan(){LL i;scanf("%I64d",&i);return i;}
LL min(LL a,LL b){return a<b?a:b;}

LL C(LL a,LL b){
if (a<b) return 0;
b = min(b,a-b);
LL up=1,down = 1;
for(LL i=0;i<b;i++){
up = up*(a-i)%MOD;
down = down*(i+1)%MOD;
}return up*pow(down,MOD-2)%MOD;
}
LL lucas(LL a,LL b){return b?C(a%MOD,b%MOD)*lucas(a/MOD,b/MOD)%MOD:1;}
int main(){
int i,j;
n=scan();m = scan();
for(i=1;i<=n;i++)data[i] = scan();
LL ans = 0;
for(i=0;i<(1<<n);i++){//枚举子集
LL flag = 1,sum = m;
for(j=0;j<n;j++)if(i&(1<<j)) sum-=(data[j+1]+1),flag *=-1;//计算个数
if(sum < 0)continue;
ans += flag*lucas(sum+n-1,n-1);
ans %= MOD;
}
printf("%I64d\n",(ans+MOD)%MOD);
return 0;
}

题解:
容斥原理+组合数取模(卢卡斯定理)
枚举状态i表示有i个box拿的花数超过了这个box里的花数(不合法状态)
然后答案就是合法状态方案数-不合法方案状态方案数(容斥原理)
用了插板法,需要注意的是为了表示出不从某个box里选的情况,需要多加1,这样不选就是选一个
  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017