Moody_Nabil's blog

By Moody_Nabil, history, 2 years ago, In English

A problem collection of ODE and differential technique

This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them.

For those who are interested in well-known problems in China.

Thank Elegia and [uset:djq_cpp] for developing this technique. Thank Rewinding for reviewing this article.

Chain Reaction in UOJ Round 3 By vfleaking

Statement

​ You are given a set A, you need to compute gi=12∑j,k(i−1j)(i−1−jk)gjgk where i−1−j−k∈A.

Solution

​ Let the EGF of g be x(t) and EGF of A be a(t). Thus x′(t)=12a(t)x2(t)+1. We can solve this equation by D&C and FFT in O(nlog2n). But there is a slower solution in O(nlogn).

​ For a polynomial equation f(x(t))=0, we can use the Newton's method to solve it. If we find a polynomial xn that x≡xn(modtn). We can derive the following equation by the Taylor series:

0=f(x2n)=f(xn)+f′(xn)(x2n−xn)+… ​ Thus x2n=xn−f(xn)f′(xn)(modt2n).

​ For an ODE ddtx=f(x), we have

ddtx2n≡≡f(xn)+f′(xn)(x2n−xn)(modt2n)f(xn)+f′(xn)x2n−f′(xn)xn(modt2n) Let r=e−∫f′(xn)dt.

(ddtx2n)rddt(x2nr)≡≡(f(xn)−f′(xn)xn)r+f′(xn)x2nr(modt2n)(f(xn)−f′(xn)xn)r(modt2n) In this problem, f(x)=12a(t)x2(t)+1. Since exp, multiplication and division takes O(nlogn) time, the we have the time complexity T(n)=T(n/2)+O(nlogn),which is O(nlogn).

​ Note: I think we can generalize this method to solve high order ODE or system of ordinary differential equations. But the constant factor will be much more terrible.

Gnutella Chessmaster in MIPT contest Ptz camp 2018, Summer

Statement

​ I think the author of this problem is [user:Endagorion.]

​ This is a simplified version of this problem: We define the weight of a sequence a1,a2,…,ak as ∏ki=1(ai+i). You are given a sequence c1,c2,…,cn. Compute the sum of the weight of all the subsequences of c with length k=1,2,…,n.

​ You can submit this problem here Little Q's sequence. However, you only need to compute the sum of all the subsequences here.

Solution

​ First, we consider the naive dp: fi,j=fi−1,j+fi−1,j−1⋅(j+ai). Let gi,j=fi,i−j,bi=ai+i, we have gi,j=gi−1,j−1+gi−1,j(bi−j).

​ Let gi(x) be the OGF of gi, we have gi(x)=xgi−1(x)+bigi−1(x)−xg′i−1(x)=x(gi−1(x)−g′i−1(x))+bigi−1(x).

gi(x)e−x=x(gi−1(x)e−x−g′i−1(x)e−x)+bigi−1(x)e−x=x(gi−1(x)e−x)′+bigi−1(x)e−x ​ Let hi=gi(x)e−x, hi=xh′i−1+bihi−1, where hi,j=jhi−1,j+bihi−1,j=(bi+j)hi−1,j. Thus hn,j=h0,j∏ni=1(bi+j). It's a multipoint evaluation of the polynomial P(x)=∏ni=1(x+bi), which can be solved in O(nlog2n).

​ If we only need to compute the sum, there is also an alternative way to solve it. gi=(x−xddx+bi)gi−1(x). Let P(x)=∏ni=1(x+bi)=∑nk=0pkxk. Then gn=∑nk=0pk(x−xddx)k(1). By induction, (x−xddx)k(1)=∑kj=0{kj}(−1)k−jxj. Let qk=∑kj=0{kj}(−1)k−j. According to OEIS, ∑k≥0qkxk=e1−x−e−x. Thus we can compute qk in O(nlogn).

​ Note: Due to the special property, the original version can also be solved in O(nlogn) by a combinatorial method.

Exp in Gennady Korotkevich Contest 5 By tourist

Statement

​ You are given a polynomial P(x), you need to find the first m coefficients of Q=Pn(x) in O(m|P|).

Solution

​ There are many similar problems like Lucky Tickets, or computing Catalan numbers, Large Schröder numbers. Also, we will discuss the relation between ODE and P-recursive sequence further in the latter part.

​ We have

(Pn+1)′=(n+1)PnP′=(PnP)′=(Pn)′P+PnP′ ​ Thus nQP′=Q′P. Consider the coefficient of xi in both parts, we have

n(qip1+2qi−1p2+⋯+kqi−k+1pk)=(i+1)qi+1p0+iqip1+⋯+(i−k+1)qi−k+1pk .

​ We can compute qi+1 from qi−k+1,qi−k+2,…,qi in O(k).

​ BTW, a more intuitive way to derive this formula is we take ln of both sides and then take the derivative. lnG=nlnF⇒G′/G=nF′/F.

​ Note: This method also works for n is not an integer. For example, you can also compute P(x)−−−−√ in the same manner. More example: compute G=∑ki=0Fii! . G′=F′(G−Fkk!). We can compute Fk using the above method and then solve this equation in a similar way.

Dirichlet k-th root in EC Final By jqdai0815

Statement

​ You are given a number theory function g and k, you need to find a function f such that g=fk. The multiplication is Dirichlet convolution here.

Solution

​ The intended solution is O(nlog2n). This improved solution credits to _rqy and Elegia.

​ Let F(s)=∑n≥1f(n)ns, which is the Dirichlet generating function. We also denote the Dirichlet generating function of gi by G(s). F′(s)=∑n≥1f(n)lnnns, thus f′(n)=f(n)lnn.

​ Using the argument of the previous problem, we have kGF′=F′Q. Consider the coefficient of n-th term, we have ∑d|nf′(d)g(nd)=1k∑d|nf(d)g′(nd). Since g(1)=1,g′(1)=0, we can compute f′(n) and then f(n) in O(nlogn).

​ The remaining problem is how to deal with lnn in the modular arithmetic. Intuitively, we can replace lnn with Ω(n), which is the number of prime factors of n counted with multiplicities. Since it's completely additive like lnn. A rigorous proof can be like that we define a transformation T of f such that (Tf)(n)=Ω(n)f(n), and we can find T(fg)=(Tf)g+f(Tg). So we can just replace the derivative of the DGF in the above argument to this transformation.

Rhyme By Elegia

Statement

​ Compute the sum of n!∏ki=1xi! where ∑ki=1xi=n and d|xi for all i(1≤i≤k).

​ n≤109,k≤2000,d=6

Solution

​ The EGF of each term is ∑j≥0xjd(jd)!=1d∑d−1j=0eωjx. Let f(x)=(1d∑d−1j=0eωjx)k.

​ Since w2=w−1, we have f(x)=∑ca,be(a+bω)x where −k≤a,b≤k. And then we can sum over ca,b(a+bω)n to get the answer. The question is that how to compute ca,b effectively. Since 1 and ω are independent, we can regard 1d∑d−1j=0eωjx as a bivariate polynomial F(u,v) where u=ex,v=eωx. We need to compute G(u,v)=F(u,v)k. If we use FFT directly, the time complexity is O(k2logk), which might be not fast enough. However, we have F∂G∂u=k∂F∂uG. Thus we can compute G in O(k2) in the same manner. We omit the details here.

Discussion about ODE and P-recursive sequence ​ It is known that every algebraic generating function is D-finite, and the coefficient is P-recursive.

​ First, there are some known results from Enumerative Combinatorics Volume 2. If w be a formal power series over K, let Vw denote the vector space over K(x) spanned by w,w′,…. Since it's D-finite, the dimension of Vw is finite.

If u,v∈D, then w=au+bv∈D, dimVw≤dimVu+dimVv If u,v∈D, then w=uv∈D, dimVw≤dimVudimVv If u,v∈D, then w=u∗v∈D, dimVw≤dimVudimVv, u∗v is the Hadamard product here.

If u∈D, v is algebraic and v(0)=0, then w=u(v(x))∈D Thus we can construct ODE for the generating function of P-recursive sequences. Here are some example:

g1(x)=∑i≥0xii!⇒g1=g′1 g3(x)=∑i≥0xii!⇒g3=g′3x2+g3x+1 g4(x)=∑i≥0xii!(i+k)!⇒g4=g"4x+(k+1)g′4 g5(x)=∑n≥01(k−1)n+1(knn)x(k−1)n+1⇒g5=kxg′51+(k−1)g′5 g6(x)=(1+x)a(1−x)b⇒g′6=ag61+x+bg61−x g8(x)=fn⇒ng8f′=fg′8 Other examples are we can construct the ODE for the truncation of P-recursive sequences.

g2(x)=∑ki=0xii!⇒g2=g′2+xii! g7(x)=∑ki=0(ni)aibn−i⇒ng7(a′+b′)−g′7(a+b)=n(n−1k)(a′akbn−k−b′ak+1bn−k−1) Universal Judge Aircraft in UOJ Round 19 By [user:ridiculos] Statement

​ There are n variables x1,x2,…,xn and two given parameters a,b(a>b). Initially, all the variables are set to 0.

​ Every time, you will choose a variable xi randomly and uniformly among the variables, which are less than a. You will terminate the process when all variables are not less than b. Compute the expected value of the number of variables that are equal to a.

​ n,a,b≤250

Solution

​ The intended solution is O(na2logn). This solution credits to djq_cpp.

​ We omit the routine generating function manipulations here. The hardest part of this problem is that let P(x)=∑b−1i=0xii!, you need to compute P(x),P2(x),…,Pn−1(x). If we use FFT directly, the time complexity is O(na2logn). Since the degree of P is not small, the method in problem Exp doesn't help a lot here.

​ Let R=xb−1(b−1)!,S=Pk−1,T=Pk,U=RS. We notice that P′=P−xb−1(b−1)=P−R. Thus T′=kP′S=k(P−R)S=kPS−RS=kT−U⇒(i+1)ti+1=kti−ui. Since U can be computed from S in linear time, Pk can be computed from Pk−1 in linear time. We remove the O(logn) factor here.

Generalization and Discussion

​ I'm thinking to generalize this technique to other problems. But I don't find amazing results. The following is the discussion with Rewinding.

​ For example, let P(x)=∑ni=0xii!i!, we can only get the similar recurrence of Pi(P′)j. If we need to compute P1,P2,…,Pk, we need to compute all terms Pi(P′)j for i+j≤k. So the time complexity is O(k2nk). It may perform well when k is extremely small, and n is very large. However, there is another concern that I conjecture that the in,in+1,…,i(n+1) term of Pk maybe a P-recursive sequence. I do believe it's a P-recursive sequence. But I don't know how large the degree and the order it can be.

​ Another direction of generalization is to compute the first n-th term of k-th power of P(x)=∑ai=0xii! more effectively. I don't think we can improve it to linear time. But it might be possible to improve it to O(nloga) or just O(nlogn) but without exp,ln.

Chinese Elephant Chess By djq_cpp

Statement

​ Find the number of binary matrixes with n rows and m columns that there are at most 2 ones in each row and column.

​ n,m≤5×104.

Solution

​ You can regard it as a bipartite graph with n vertices and m vertices in both parts. The degree of every vertex is no more than 2. The graph consists of even cycles, even chains, and odd chains.

​ The EGF of even cycles, even chains and odd chains are

F=∑i≥212ixiyi ,

G=∑i≥1xiyi ,

H=12(∑i>0xi+1yi+∑i>0xiyi+1)+x+y respectively.

​ And the answer is n!m![xnym]eF+G+H.

​ It's hard to deal with bivariate EGFs. We need to transform them into univariate EGFs. Since the degrees of x and y are the same in EGF of even cycles and even chains, we can transform them into univariate EGFs directly. For odd chains, we know the number of chains starting in the left part is less than the number in the right part by m−n. So we can enumerate the number of odd chains in the left part, and transform it into a univariate EGF.

​ The new EGF is

F=∑i≥212ixi ,

G=∑i≥1xi ,

H=x+12∑i≥2xi .

​ The answer is n!m![xm]eF+G∑ni=0HiHm−n+ixii!(m−n+i)!. Let P(x)=∑i≥0xii!(m−n+i)!,Q=H2x. The formula can be simplified to n!m![xm]eF+GHm−nP(Q).

​ We know the coefficient of P is P-recursive. So we can construct an ODE for P that P=P"x+(m−n+1)P′.

​ We also have that

(P(H))′=P′(H)H′,(P(H))"=P"(H)(H′)2+P′(H)H" . So

P′(H)=P(H)′H′,P"(H)=P(H)"H′−P(H)′H"H′3 .

​ Then we can get the ODE of P(H) :

P(H)H′3=P(H)′((m−n+1)H′2−H"H)+P(H)"H′H , which is something like $$$P(H)\cdot A=(P(H))' \cdot B+(P(H))" \cdot C$$$, where A,B,C are three polynomials. So we can use D&C and FFT to solve this equation in O(nlog2n).

​ Note that H=12(x+x1−x), if we multiply (1−x)6 in the both side of the ODE of P(H), we can get a polynomial recurrence of P(H) with small order and degree. So P(H) can be computed in O(n) here. It's not hard to see Hm−n and eF+G are also P-recursive, so the convolution should also be P-recursive. Then we solved this problem in the linear time easily. But I think the order and degree will be too large if we try to find the recurrence of the answer directly. So a more effective way might solve these recurrences directly and compute the answer by FFT.

Generalization and Discussion

​ It looks polynomial modular composition can be computed in O~(n) in academia. But I don't know whether it's practical. The most popular algorithm is O(n2+n1.5logn). You can also read the discussion and implementation of the Brent-Kung algorithm here. However, it is a bit slower than O(n2) one when n=20000.

​ It's not hard to see the above method can be applied to compute the polynomial composition F(G(x)) when F is D-finite. We can construct the ODE of F(G(x)) and solve the equation using D&C and FFT in O(nlog2n). However, when the ODE of F is too complicated, there is a severe issue of the constant factor.

​ Combined with Newton's method, we can compute the composition inverse of a D-finite series. A good application is to compute the number of simple permutations (a.k.a NEERC18 I) with length 1,2,…,n in O(nlog2n).

Pearl in CTSC 2019 By laofudasuan

Statement

​ Compute n!2d[xn]∑kp=0(mp)(ex−e−x)p(ex+e−x)m−p.

​ n≤109,m≤105

Solution

​ This solution credits to djq_cpp.

​ Let Q(x)=∑kp=0(mp)(x−1)p(x+1)m−p. So

2mQ−(2x)Q′=m(m−1k)((x−1)k(x+1)m−k−(x−1)k+1(x+1)m+k−1) . And we can simplify it to

mQ−xQ′=m(m−1k)(x−1)k(x+1)m−k−1 .

​ The right is P-recursive, thus Q can be computed in O(m). So the answer is n!2d[xn]Q(e2x)e−mx. The whole problem can be solved in O(m(1+logmn)).

​ Note: We need to compute 1n,2n,…,mn, but it's multiplicative. Thus we can compute them in O(mlogmn).

  • Vote: I like it
  • -95
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

This was plagiarized from jqdai0815's earlier blog post here.

»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Hey let's take a small challenge:

Fix the Latex