Codeforces #258 Div.2 E Devu and Flowers
大致题意:
从n个盒子里面取出s多花。每一个盒子里面的花都同样,而且每一个盒子里面花的多数为f[i],求取法总数。
解题思路:
我们知道假设n个盒子里面花的数量无限,那么取法总数为:C(s+n-1, n-1) = C(s+n-1, s)。
能够将问题抽象成:x1+x2+...+xn = s, 当中0<=xi <= f[i]。求满足条件的解的个数。
两种方法能够解决问题:
方法一:这个问题的解能够等价于:mul = (1+x+x^2+...+x^f[1])*(1+x+x^2+...+x^f[2])*...*(1+x+x^2+...+x^f[n])中x^s项的系数。而 (1+x+x^2+...+x^f[i]) = (1-x^(1+f[i]))/(1-x),那么mul = (1-x^(1+f[1]))*(1-x^(1+f[2]))*...*(1-x^(1+f[n]))*(1-x)^(-n)。
对于 (1-x^(1+f[1]))*(1-x^(1+f[2]))*...*(1-x^(1+f[n]))这部分的系数。因为n非常小,直接暴力(2^n)枚举计算各项的系数。
对于(1-x)^(-n)的系数,(1-x)^(-n) = (1/(1-x))^n, 而1/(1-x) = 1 + x + x^2 + ... + x^n + ...,无穷级数。那么(1-x)^(-n) = (1+x+x^2+...+x^m+...)^n,要求这个式子x^s项的系数,就相当于从n个盒子(花的数量无限)里面去s朵花,求取法总数。于是(1-x)^(-n)中x^s项的系数为:C(s+n-1, n-1)。
知道这两部分的系数以后问题就迎刃而解了。
方法二:容斥原理。
设A1 = {x1 >= f[1]+1}, A2 = {x2 >= f[2]+1}, ..., An = {xn >= f[n]+1}, 全集S = (n+s-1, s)。那么问题的解集为:全集减去不符合条件的解集(某个Ai为真)。 不符合条件的解集能够用容斥原理来解决。即:。
暴力枚举(2^n)Ai的状态,假设Ai为真,则s -= (f[i]+1)。那么这样的状态下,解的为题相当于从n个盒子里面取s(减去该状态下全部f[i]+1以后的值)朵花,盒子花的数目没有限制,解的个数为C(s+n-1, n-1)。
最新文章
- Android java判断字符串包含某个字符段(或替换)
- ASP.NET四则运算--工厂模式
- vs2015编译mysql c++ connector
- vgrant使用简易教程
- SQL 序列-DML-DML-数据类型-用户管理、权限-事务-视图
- 数学模块_math
- How to Pronounce T + Dark L
- share pool 管理机制
- python3转变exe的方法
- php 框架选择
- 【小程序】返回顶部wx.pageScrollTo和scroll-view的对比
- const char * 转换为char*
- js中的同步与异步的问题
- [LOJ6145][2017 山东三轮集训 Day7]Easy
- pc、移动端H5网站 QQ在线客服、群链接代码【我和qq客服的那些事儿】
- GM TECH2 Scanner Clone
- app分享代码
- ORA-21561: OID generation failed
- linux命令之文本查看
- [agc004d]salvage robot
热门文章
- Linux学习-Ubuntu 18.04-安装图文教程
- 使用 swoole_process 实现 PHP 进程池
- jquery中$.get()提交和$.post()提交有区别
- FOJ1205 小鼠迷宫问题 (BFD+递推)
- vs2010和qt4.8.4配置
- bootstrap结合google code prettify的问题
- c#+ArcGIS Engine-获取矢量图层的空间参考
- 减少UIViewController切换的耦合
- ZOJ 2588 Burning Bridges(求桥的数量,邻接表)
- sqlserver bulk insert