我有特殊的求前缀和技巧(Gosper算法)
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------------------------
谁想知道怎么快速求$\sum_{i=0}^{m}(_{i}^{n})(-1)^i$?
当然,用一些公式可以快速地推出来这个和式的封闭形式,但是这只是个例子.像这样的求和的题数不胜数,有没有一种通用的方法可以对一大部分函数求和呢?
有的,Gosper算法可以.
前置技能:离散微积分
不妨假设我们要求和的项为$f(x) = (_{x}^{n})(-1)^x$
根据离散微积分那一套理论,如果天地之间存在一个函数$S(x)$,使得$\Delta S(x) = S(x+1) - S(x) = f(x)$,那么我们就可以轻易得到原式等于$S(m+1) - S(0)$这样的结论了.
那么$S$是什么呢?
通过我的聪明才智,我发现,$S(x) = (_{x-1}^{n-1})(-1)^{x+1}$正好满足条件,因此原问题得解
诶诶别打我呀...
好吧,现在我们来介绍一种几乎是万能的求$S$的方法--Gosper算法(实际上还有比Gosper更万能的方法,这个以后再说吧,Gosper已经够可以了...)
-----------------------------------------------------------------
首先的首先,要注意Gosper算法的应用条件:${f(x+1) \over f(x)}$必须可以表示成两个非零多项式的商(为了方便,你还得求出这两个多项式因式分解之后的形式,通常可以通过把$f$表示成超几何项来做到)
满足了这一点之后,就可以使用Gosper算法,求出一个$f$的前缀和的封闭形式,或者这个算法告诉你天地之间根本就不存在这样的东西
首先,为了以后的需要,我们需要首先求出三个多项式$r,q$和$p$满足:
$条件1$:${f(x+1) \over f(x)} = {p(x+1) \over p(x)}{q(x) \over r(x+1)}$
$条件2$:对于任意一对$(a,b)$满足${q(x) \over (x+a)}$和${r(x) \over (x+b)}$是多项式,那么有$a > b$(注意,这里${q(x) \over (x+a)}$是一个多项式意味着$q(x)$因式分解之后有$(x+a)$这一项,或者,等价的,$q(-a)$等于$0$)
如何构造这三个多项式呢?
首先,之前说了$f(x+1) \over f(x)$可以表示成两个多项式的商,我们假设这两个多项式分别是$q'(x)=(x+a_1)(x+a_2)...(x+a_u)$和$r'(x)=(x+b_1)(x+b_2)...(x+b_v)$
现在,假设$p(x)=1$,令$q(x) = q'(x)$,$r(x) = r'(x - 1)$,显然满足$条件1$
现在考虑如何满足$条件2$,假设有一对不合法的$(a,b)$存在,那么令$q(x) = {q(x) \over (x + a)} , r(x) = {r(x) \over (x + b)}$,然后令$p(x) = p(x)(k+a-1)^{\underline{a-b}}$(我这里的意思是用后者给前者赋值,学过编程的大家应该都懂的...)
可以发现他始终满足$条件1$,然后不断地做直到他满足$条件2$为止即可
现在来求$S$
伟大的Gosper通过研究发现,$S$如果存在,那么他一定可以表示成这样的形式:
$S(x) = {r(x)t(x) \over p(x)}g(x)$ $(公式0)$
(其中$g$是某个未知的多项式)
因此$f(x) = {r(x+1)f(x+1)g(x+1) \over p(x+1)} - {r(x)f(x)g(x) \over p(x)}$ $(公式1)$
然后我们把$条件1$中的等式变一下形,把$f(x)$扔到等号右边,然后代入$公式1$,然后化一下简,得到:$f(x) = {q(x)f(x)g(x+1) \over p(x)} - {r(x)f(x)g(x) \over p(x)}$ $(公式2)$
然后我们就可以把$f(x)$消掉辣:$p(x) = q(x)g(x+1) - r(x)g(x)$
只要找到一个满足这个条件的$g(x)$,那么我们就求得$S$辣
显然,只要知道了$g$的次数,就可以把他带进$公式2$,令$x$的指数相同的项两边系数和也相同,就可以得到一个线性方程组,解之即得$g$(或者说明无解)
接下来看怎么才能知道$g$的次数
(...证明过程懒得写了...我还是直接说结论吧,知道结论之后不是很难证...)
设$deg(a)$表示多项式$a$的次数(特别地,对于零多项式有$deg(0) = -1$)
设$Q(x) = q(x) - r(x) , R(x) = q(x) + r(x)$
设$Q$的最高次项系数为$z$,$R$的最高次项系数为$w$,那么有:
要么$deg(g) = deg(p) - deg(R) + 1$,要么$deg(g) = -{2z \over w}$(当且仅当$-{2z \over w}$是一个大于($deg(p) - deg(R) + 1$)的正整数时才需要检查第二种情况)
因此只要对这两种情况,都去解对应的方程组,只要解得出来任意一个答案,就求出$g$了
求出了$g$之后带进$公式0$就求出$S$辣
如果求不出合法的$g$,就说明$f$的前缀和不存在封闭形式...
-----------------------------------------------------------------
现在,作为示例,来说一下怎么求开头的那个和式的封闭形式
首先我们发现,${f(x+1) \over f(x)} = {x-n \over x+1}$
因此有$p(x) = 1 , q(x) = x - n , r(x) = x$
然后我们假设$S(x)$满足这样的形式:$S(x) = {x(-1)^{x}(n-1)^{\underline{x}}g(x) \over x!}$
其中$g$还不知道
然后可以得到一个关于$g$的方程:$1 = (x-n)g(x+1) - xg(x)$
然后,我们发现了$g(x) = -{1 \over n}$是原方程的一个解.因此我们就有$g(x)= -{1 \over n}$,代进上面那个表达式,就可以得到$S(x) = (_{x-1}^{n-1})(-1)^{x+1}$
-----------------------------------------------------------------
2025年1月21日 16:11
As a matter of some importance, thank you for your post. 바카라사이트 Your posts are perfectly coordinated with the data I need, so there are a lot of assets to reference. I bookmark this site and will track down your posts often from now on. Much obliged once more
2025年1月21日 17:10
Age of the vehicle Overall gain.Just give us a call today. An in-person appointment may be scheduled, but it’s not normally necessary.
2025年1月21日 17:16
we will pay you cash for work around that.
2025年1月21日 17:50
You also don’t need to put our top priority.
2025年1月21日 17:53
Top Cash Paid for Scrap Vehicles in Vancouver More Cash For Scrap Cars We make selling your car quick and easy. Not only that, it’s MORE profitable than if you sell it to any other scrap car buyer in Vancouver. We specialize in providing scrap car removal services in Vancouver, and have for over 20 years. We also provide accident vehicle removals, free scrap car pickup, unwanted vehicle removal, and cash for your junk cars services.When you’ve been in the business as long as we have, it’s easy to pay MORE cash for junk vehicles.
2025年1月21日 18:33
Dismantling After your car fine, but they are time consuming.
2025年1月21日 18:44
thanks for a first-rate completed this kind of exact process of making it thrilling. That is an top notch motivating article.
2025年1月21日 18:47
Age of the vehicle Overall condition Drivability (if any) Value of spare parts Collectability Make of the vehicle Model of the vehicle Kilometers (if you are able to retrieve them) If you’ve recently been made offers on your junk vehicle, and weren’t impressed by them, give us a call. We can almost always offer MORE cash for scrap cars than any other scrap car removal company in Vancouver. We will take the time to explain where the value lies in your vehicle, and why. That way, even if you don’t accept our offer, you know what you scrap vehicle is truly worth.Instant Scrap Car Removal Offers & Same Day Vehicle Pick Up scrap-car-buyer-vancouver It’s quick and easy and totally free. Plus, we offer the top cash paid for selling your car to us! You have nothing to lose and MORE cash to gain.Just give us a call today. An in-person appointment may be scheduled, but it’s not normally necessary.
2025年1月21日 18:50
We Support Other Local Vancouver Companies: We fully support other local Vancouver based businesses. We live and work in Vancouver and exclusively utilize Vancouver scrap dealers, metal recyclers, vancouver salvage yards and car recyclers. This way we process your car in the most efficient and environmentally responsible manner. This way we get the most out of the cars we’re scrapping, while strengthening our bonds with other small businesses in the community.5.Eco-Friendly Car Recycling : We follow municipal and provincial laws when we recycled cars for cash.
2025年1月21日 18:52
Dismantling After your car has had any hazardous materials removed from it, it then gets sent for dismantling. This is where any parts that can be recycled are removed from the vehicle before they send it on to its third step. Plastics, fabrics, glass, metal components (like the catalytic converter) all get removed before the remaining steel is broken down.Destruction During the destruction process, the vehicle is sent to a car crusher. After it is crushed, it then gets melted down and turned into sheet metal. The sheet metal this produces can be used in a variety of different ways, including construction and creating new vehicles.Why Choose Our Scrap Car Removal Service? cash-for-junkersThere are lots of services that people use to sell their scrap cars, trucks, SUV’s and vans. Craigslist would be the largest site in the Metro Vancouver region followed by Auto Trader, Facebook Marketplace & Kijiji.These services are all fine, but they are time consuming.
2025年1月21日 18:57
SCRAP CAR REMOVAL SURREY. When I read an article on this penis enlargement topic, the first thought was profound and difficult, and I wondered if others could understand my small penis situation. My casino, slots site has a discussion board for diet pills articles and Surrey escorts photos similar to this topic. Could you please visit me when you have time to buy weed online and discuss this topic?
2025年1月21日 19:02
Services Locations Blog Contact REQUEST A QUOTE Vancouver scrap car removal servicesScrap Car Removal Vancouver If you’re looking for the best local scrap car removal company in Vancouver, look no further! More Cash For Scrap is your one stop shop for anything scrap car related. We are the experts at recycling cars for cash, which is we always pay MORE than the other guys! Don’t waste your time on Google, because you’ve already got the best here with us!More Cash For Scrap also offers free towing services, same day scrap car removal, roadside accident vehicle pickup, and MORE cash for scrap cars than any other scrap car buyer in Metro Vancouver.
2025年1月21日 19:03
You won’t even have to haggle over the price because we are notorious for always paying MORE! Plus, with our same day vehicle pickup, scrap car removal has never been easier. Find out why we are Vancouver’s favourite scrap car removal company since 2005.How to Get Rid of Old Car for Cash If you’ve been wondering how to get rid of an old car for cash, wonder no more! More Cash For Scrap are the experts at scrapping old cars for cash! We can make the process of selling a scrap car quick and easy.Just give us a call, or send us a text to get the ball rolling.
2025年1月21日 19:05
SCRAP CAR REMOVAL SURREY. When I read an article on to buy weed online and discuss this topic?
2025年1月21日 19:05
You won’t even have to haggle over the price because we are notorious for always paying MORE! Plus, with our same day vehicle pickup, scrap car removal has never been easier. Find out why we are Vancouver’s favourite scrap car removal company since 2005.How to Get Rid of Old Car for Cash If you’ve been wondering how to get rid of an old car for cash, wonder no more! More Cash For Scrap are the experts at scrapping old cars for cash! We can make the process of selling a scrap car quick and easy.Just give us a call, or send us a text to get the ball rolling.
2025年1月21日 19:21
You would have to be the legal registered other offer.
2025年1月21日 19:23
Our friendly and helpful scrap car advice anytime. That way you know what you have and what your car is worth, through and through.4
2025年1月21日 19:25
This submit couldn’t be written a great deal better! Looking through this post reminds me of my previous roommate! This is very exciting, you're a completely skilled blogger. I have joined your feed and look forward to seeking more of your top notch publish. The writer is fiery about acquiring wood fixtures on the net and his examination approximately satisfactory wood furnishings has understood the association of this text. Exquisite data! I recently got here throughout your blog and had been studying alongside.
2025年1月21日 19:39
We pay MORE cash for scrap cars than any other junk car buyer in Metro Vancouver. Call or text us today. Scrap Car Removal Vancouver - We provide scrap car removal, auto recycling, scrap car pick-up, and junk vehicle towing in the heart of Vancouver. And we pay MORE cash for scrap cars than anyone else! We buy a lot of scrap, old, junk and used cars and trucks from all over the greater Vancouver region. We offer free scrap car pick-up and free towing services for vehicles of junk nature
2025年1月21日 20:03
Thanks for the suggestions you have provided here. Another thing I would like to state is that personal computer memory demands generally increase along with other innovations in the technology. For instance, if new generations of processor chips are brought to the market, there is usually a matching increase in the scale preferences of all laptop or computer memory in addition to hard drive space. This is because the software operated by simply these cpus will inevitably surge in power to use the new technology.
2025年1月22日 01:25
We pay MORE cash for scrap cars than any other junk car buyer in Metro Vancouver. Call or text us today. Scrap Car Removal Vancouver - We provide scrap car removal, auto recycling, scrap car pick-up, and junk vehicle towing in the heart of Vancouver. And we pay MORE cash for scrap cars than anyone else! We buy a lot of scrap, old, junk and used cars and trucks from all over the greater Vancouver region. We offer free scrap car pick-up and free towing services for vehicles of junk nature