首页 > 其他分享 >[Maths] 数学做题记录

[Maths] 数学做题记录

时间:2024-02-18 19:44:42浏览次数:34  
标签:dbinom 记录 公式 sum 数学 Maths displaystyle

P7481 梦现时刻

由题得:

\[F(a, b) = \sum_{i = 0} ^ {b}\dbinom{b}{i}\dbinom{n - i}{a} \]

根据公式 \(\displaystyle \dbinom{n}{m} = \dbinom{n - 1}{m - 1} + \dbinom{n - 1}{m}\),有:

\[F(a, b) = \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} + \sum_{i = 0} ^ {b}\dbinom{b - 1}{i}\dbinom{n - i}{a} \]

\[F(a, b) = \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} + F(a, b - 1) \]

好的我们发现这个式子烦人的一点就是 \(\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a}\),考虑将其也写成若干个 \(F\) 乘系数的形式。

\[\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} = \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a} \]

\[= \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i}{a} - \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} \]

\[= F(a, b - 1) - \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} \]

现在的目标转化为化简 \(\displaystyle \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1}\),继续:

\[\sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} = \sum_{i = -1} ^ {b - 1}\dbinom{b}{i + 1}\dbinom{n - i - 1}{a - 1} - \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i + 1}\dbinom{n - i - 1}{a - 1} \]

\[= \sum_{i = 0} ^ {b}\dbinom{b}{i}\dbinom{n - i}{a - 1} - \sum_{i = 0} ^ {b}\dbinom{b - 1}{i}\dbinom{n - i}{a - 1} \]

因为 \(\dbinom{b - 1}{b} = 0\),所以有:

\[= \sum_{i = 0} ^ {b}\dbinom{b}{i}\dbinom{n - i}{a - 1} - \sum_{i = 0} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i}{a - 1} \]

\[= F(a - 1, b) - F(a - 1, b - 1) \]

整理一下,有:

\[\displaystyle \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} = F(a - 1, b) - F(a - 1, b - 1) \]

\[\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} = F(a, b - 1) - (F(a - 1, b) - F(a - 1, b - 1)) \]

\[\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} = F(a, b - 1) - F(a - 1, b) + F(a - 1, b - 1) \]

\[F(a, b) = F(a, b - 1) - F(a - 1, b) + F(a - 1, b - 1) + F(a, b - 1) \]

\[F(a, b) = 2F(a, b - 1) - F(a - 1, b) + F(a - 1, b - 1) \]

好的!我们现在得到了递推式,可以 \(O(m ^ 2)\) 计算,但是考虑一些边界情况:

\[F(0, b) = 2^b \]

\[F(a, 0) = \dbinom{n}{a} \]

因为 \(n \leq 10^9\),所以需要使用以下公式计算:

\[\dbinom{n}{a} = \dfrac{\displaystyle \prod_{i = n - a + 1} ^ {n} i}{a!} \]

标签:dbinom,记录,公式,sum,数学,Maths,displaystyle
From: https://www.cnblogs.com/RB16B/p/18019850

相关文章

  • 惠普HP519打印机缺色处理记录
    打印蓝色缺失开盖检查,发现蓝色墨水管路中间有断线,拆开打印头后,用随机器配的桔红色吸墨器吸墨.之后重新开机还是缺色.检查彩色打印头,用浅浅的一层热水泡下方喷嘴,黄色红色出墨明显,蓝色几乎没颜色,于是用针管从入口注入一些蓝色墨水,再用另一个针管拆掉针头后,套上......
  • 记录--你还在使用websocket实现实时消息推送吗?
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助前言在日常的开发中,我们经常能碰见服务端需要主动推送给客户端数据的业务场景,比如数据大屏的实时数据,比如消息中心的未读消息,比如聊天功能等等。本文主要介绍SSE的使用场景和如何使用SSE。服务端向客户端推送......
  • 算法题记录
    试写一个python程序,求平面直角坐标系中两点的距离:classCoordinate:def__init__(self,x,y):self.x=xself.y=ydefdistance(self,other):x_diff_sq=(self.x-other.x)**2print(x_diff_sq)y_diff_sq=(self.y-other.y)**2......
  • pyspark集成访问hive数据踩坑记录
    当前环境anaconda3、python3.9.13、jupyter需要安装的pyspark、py4jpyspark和py4j的离线安装包地址Linksforpyspark(tsinghua.edu.cn)和Linksforpy4j(tsinghua.edu.cn)一开我自己没有仔细的对应版本,找了一个pyspark3.4.1的包正常安装上去了,通过pyspark进入shell可以正......
  • bug记录:输入框延迟、卡顿
    问题场景离开本页签时(即点击其他页签时),存储查询数据。导致bug:首次打开页签,或者点击浏览器按钮刷新时后,页面上的输入框输入后,会出现无法输入、延迟显示、输入卡顿。代码如下:/*===initDataMixin.js===*/beforeRouteLeave(to,from,next){//跳转路由之前,存储滚......
  • 做题记录:SP703 SERVICE - Mobile Service
    SERVICE-MobileService暴力设\(f_{i,a,b,c}\)表示处理完前\(i\)个任务,第一个人在\(a\)位置,第二个人在\(b\)位置,第三个人在\(c\)位置的最小代价。方程:\[f_{i,a,b,c}=\min{f_{i-1,a',b,c}+c(a,a'),f_{i-1,a,b',c}+c(b,b'),f_{i-1,......
  • Openwrt罢工后重新配置记录
    春节回乡过年,远程登陆时发现,socat端口转发有点儿问题,无法访问自己的NAS。尝试重启openwrt,结果直接跪了,再也无法登录了。返京后摸索了半天,发现是安装系统的U盘可能是不行了,导致配置无法存储,每次重启系统都会直接复位。本来想一不做二不休,直接把系统装到买软路由时送的mSAT......
  • 刷题记录_2024寒假2/17
    我都AFO了为什么还要我写题目P多少多少默认洛谷P3313旅行题意略,自己不会看吗考虑对每个信仰开一个线段树,下标为dfs序,然后就是树剖板子对于这种开一堆动态开点线段树的题目可以存每个线段树的根节点然后就只需要开一个结构体了code:#include<bits/stdc++.h>#definelct[n......
  • Tacotron-2 实验记录
    https://blog.csdn.net/u013625492/article/details/100155542TrytheStdVersion1.GetTacotron-2-master.zipfromhttps://github.com/Rayhane-mamah/Tacotron-22.UnzipTacotron-2-master.ziponUnbuntu3.Terminal:cp-rtraining_data./Tacotron-2#training_......
  • 最小差距(简单数学)
    第1题   最小差距 查看测评数据信息有a张1元钱,b张2元钱,c张3元钱,现在要把这些钱分给两个人,应该如何分配才能使得两个人的钱的差距最小?输出最小差距。输入格式 多组测试数据。第一行,一个整数G,表示有G组测试数据。1<=G<=10000.每组测试数据格式如下:   一行,3个......