洛谷-P15427 Nobody Tells 题解

Solution我们不能直接查询数列前几项只能查询L≤iML\le iML≤iM的位置。这意味着很可能需要利用数列本身的数学结构和性质。我们需要一个可以让我们从任意靠后的几项推出p,qp,qp,q的性质。这里直接上结论fi2−fi−1fi1≡(−q)i f_i^2-f_{i-1}f_{i1}\equiv(-q)^ifi2​−fi−1​fi1​≡(−q)i不难归纳证明。专门对着这个式子出的题吧没学过二阶齐次线性递推做不出来很正常最自然的想法是问fM−3,fM−2,fM−1f_{M-3},f_{M-2},f_{M-1}fM−3​,fM−2​,fM−1​。此时根据结论有fM−22−fM−3fM−1≡(−q)M−2 f_{M-2}^2-f_{M-3}f_{M-1}\equiv(-q)^{M-2}fM−22​−fM−3​fM−1​≡(−q)M−2由费马小定理(−q)M−2≡(−q)−1(-q)^{M-2}\equiv(-q)^{-1}(−q)M−2≡(−q)−1因此q≡−(fM−22−fM−3fM−1)−1 q\equiv-\left(f_{M-2}^2-f_{M-3}f_{M-1}\right)^{-1}q≡−(fM−22​−fM−3​fM−1​)−1我们就得到了qqq。再来考虑如何得到ppp。由递推式得fM−1≡qfM−3pfM−2pfM−2≡fM−1−qfM−3 \begin{aligned} f_{M-1}\equiv qf_{M-3}pf_{M-2} \\ pf_{M-2}\equiv f_{M-1}-qf_{M-3} \end{aligned}fM−1​pfM−2​​≡qfM−3​pfM−2​≡fM−1​−qfM−3​​此时如果fM−2≢0f_{M-2}\not\equiv 0fM−2​≡0我们就做完了。接下来只需要考虑fM−2≡0f_{M-2} \equiv 0fM−2​≡0的情况。此时仅仅知道fM−3,fM−2,fM−1f_{M-3},f_{M-2},f_{M-1}fM−3​,fM−2​,fM−1​肯定得不出ppp尝试查询fM−4f_{M-4}fM−4​。由结论得fM−32−fM−4fM−2≡(−q)M−3 f_{M-3}^2-f_{M-4}f_{M-2} \equiv(-q)^{M-3}fM−32​−fM−4​fM−2​≡(−q)M−3由费马小定理和fM−2≡0f_{M-2}\equiv 0fM−2​≡0得fM−32≡(−q)−2 f_{M-3}^2\equiv(-q)^{-2}fM−32​≡(−q)−2因此q≡±1fM−3q\equiv\pm \frac{1}{f_{M-3}}q≡±fM−3​1​。显然fM−3≢0f_{M-3}\not\equiv 0fM−3​≡0不然整个数列就全000了。可以放心将解出的两个qqq代入fM−2≡pfM−3qfM−4f_{M-2}\equiv pf_{M-3}qf_{M-4}fM−2​≡pfM−3​qfM−4​解出两个ppp分别提交即可。最终交互策略步骤操作第一次查询fM−2f_{M-2}fM−2​第二次查询fM−3f_{M-3}fM−3​第三次若fM−2≢0f_{M-2}\not\equiv0fM−2​≡0查询fM−1f_{M-1}fM−1​求出唯一解第三次若fM−2≡0f_{M-2}\equiv0fM−2​≡0查询fM−4f_{M-4}fM−4​求出两组解Code#includeiostream#defineintlonglongusingnamespacestd;intm,l;intquery(intx){intres;cout? xendl;cinres;returnres;}voidguess(intp1,intq1,intp2,intq2){p1(p1m)%m,p2(p2m)%m;q1(q1m)%m,q2(q2m)%m;cout! p1 q1 p2 q2endl;}intksm(intx,inty){intres1;while(y){if(y1)(res*x)%m;(x*x)%m,y1;}returnres;}voidsolve(){cinml;// f_{m-4}:a// f_{m-3}:b// f_{m-2}:c// f_{m-1}:dintcquery(m-2),bquery(m-3);if(c){intdquery(m-1);intq-ksm((c*c%m-b*d%m)%m,m-2);intp(d-q*b)%m*ksm(c,m-2)%m;guess(p,q,p,q);}else{intaquery(m-4);intqksm(b,m-2);intp-q*a%m*ksm(b,m-2)%m;guess(p,q,-p,-q);}}signedmain(){intT;cinT;while(T--)solve();return0;}