博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
女神(goddess)——组合数学
阅读量:6567 次
发布时间:2019-06-24

本文共 1763 字,大约阅读时间需要 5 分钟。

出自某模拟赛。

题目大意:

对1e9+7取模。

数据范围

 20 % : n<=300
40 % : n<=2,000
50 % : n<=10,000
70 % : n<=1,000,000
100 % : n<=1,000,000,000

题解

方法众多。

然而我太蒟了,2h43min愣是写了一个40pts暴力走人。

开始指着想正解,但是发现想不出来,然后写n^2暴力,结果总是要么漏算要么算重要么取模出错。。。最后才调出来。

 

1.如果比较菜,请尝试打表:

$n^3$暴力显然。然后打表。

$n=1,ans_1=1$
$n=2,ans_2=6$
$n=3,ans_3=24$
$n=4,ans_4=80$
然后,套路的先观察相邻两项的关系。
然后尝试和项数的下标套上关系。
$ans_2=ans_1\times \frac{6}{1}$
$ans_3=ans_2\times \frac{8}{2}$
$ans_4=ans_3\times \frac{10}{3}$
诶,然后发现了规律!!
可以递推。
$f_{n+1}=f_n\times \frac{4+2\times n}{n}$
$f_{n+1}=f_n\times \frac{2\times(n+2)}{n}$
迭代下去得:
$f_{n+1}=f_1 \frac{2^n\times (n+2)!}{2n!}$
$f_{n+1}=\frac{2^{n}\times (n+1)\times(n+2)}{2}$
$f_{n}=\frac{2^{n-1}\times n\times(n+1)}{2}$
即可出结果

 

2.正解:

有点意思的是,i+n-i-1=n-1,k-j+j-1=k-1对于任意的i,j恒成立。

这就是突破口
考虑组合数的意义。
$\sum_{k=1}^n(k\times\sum_{j=1}^k\sum_{i=0}^{n-1}(C_i^{k-j}\times C_{n-i-1}^{j-1})$
$=\sum_{k=1}^n(k\times\sum_{i=0}^{n-1}\sum_{j=1}^k(C_i^{k-j}\times C_{n-i-1}^{j-1})$
j和i换了位置之后,
发现,其实i就是枚举的一个分割点,
然后对于选择的k-1个数,在1~i个数中选择k-j个,
在i+1~n-i-1个数中选择j-1个。
好像和$C_{n-1}^{k-1}$有些关系。
发现,对于$C_{n-1}^{k-1}$中的每个方案。
其实都可以找出0~n-1这n个分界点,然后统计一次。
每个方案被统计了n次。
所以,
原式
$=\sum_{k=1}^nk\times n\times C_{n-1}^{k-1}$
已经可以O(n)递推了。
我们可以用刚才的打表中方法,搞出递推式,然后迭代出来通项公式。
即可O(logn)求解。

 

3.但是这个还不够漂亮!!!

 

这个可是组合数啊!!不是一般的数。

组合数毕竟有实际的意义。
观察这个式子的组合意义。
$\sum_{k=1}^nk\times n\times C_{n-1}^{k-1}$
这个k-1和k,n有点麻烦。
提出来:
$=n\times (\sum_{k=1}^n(k-1)\times C_{n-1}^{k-1})+n\times 2^{n-1}$
第一个括号里面是什么意义?
对于n-1个数的集合中,所有子集的大小的和。
套路地,我们转化研究对象。
考虑每个元素被统计了几次。
就是:$2^{n-1-1}=2^{n-2}$
因为每个数自己必须出现一次,然后其他的数爱出现不出现。
所以,
$=n\times( n\times2^{n-2})+n\times 2^{n-1}$
然后就可以O(logn)计算了。

 

总结:

0.这个式子,我们尝试用数学知识、组合数公式化简,发现不容易化简。然后就要考虑组合数的意义。

1.组合数是一个有意义的数。这样的数学式子的推导,可以通过寻找式子的意义来进行化简。

往往起到立竿见影的效果。

2.打表找规律,要考虑把结果,递推关系和项的编号放在一起。

 

转载于:https://www.cnblogs.com/Miracevin/p/9792344.html

你可能感兴趣的文章
vue-cli3.0
查看>>
window.location.replace vs window.location.href
查看>>
CVPR 2018:阿里提出应用 LocalizedGAN 进行半监督训练
查看>>
被劫持的wordpress.com账户被用来感染站点
查看>>
分享一下最近看的东西
查看>>
《大数据、小数据、无数据:网络世界的数据学术》一 第2章 何为数据 2.1 引言...
查看>>
寓教于乐的顶峰:新一届大学生集群竞赛火热开战
查看>>
《计算机科学与工程导论:基于IoT和机器人的可视化编程实践方法第2版》一第1章 职业发展机会和团队建设...
查看>>
HBase BlockCache系列 - 探求BlockCache实现机制
查看>>
【参与有奖】您用的MySQL、MongoDB、Redis等服务被勒索过吗?
查看>>
Java核心技术卷I基础知识1.2.6 体系结构中立
查看>>
Libvirt 虚拟化库介绍
查看>>
Xmemcached发布1.2.6.1(推荐升级)
查看>>
《Spring 5 官方文档》26. JMS(一)
查看>>
《Python Cookbook(第2版)中文版》——1.11 检查一个字符串是文本还是二进制
查看>>
Tkinter之Label
查看>>
PostgreSQL merge json的正确姿势
查看>>
java反射
查看>>
【IOS-COCOS2D游戏开发之二】COCOS2D 游戏开发资源贴(教程以及源码)
查看>>
nodejs安装记录
查看>>