[题解] LuoguP6197 [EER1]礼物

https://www.luogu.com.cn/problem/P6197

毒瘤题，还卡常qwq.......

Description

给一个长度为(n)的数列(a)，满足递推关系(a_n=2a_{n-1}+ka_{n-2})（(k)是你指定的值），边界(a_1=1,a_2=2)。

然后在给出(m)个质数，求最小的(k)使得对于在(1cdots n)内且不在指定的数内的素数(p)，都有(pmid a_p)，对一个(NTT)模数(c)取模。

Solution

你看它递推式长得那么别致就知道肯定有用 但NTT模数就很迷惑

于是大力推通项

先假设(a_n=q^n)，首先要满足

[q^n-2q^{n-1}-kq^{n-2}=0 ]

提个(q^{n-2})出来

[q^{n-2}(q^{2}-2q-k)=0 ]

及(q^2-2q-k=0)，解方程得到

[q_0=frac{2+sqrt{4+4k}}{2}=1+sqrt{k+1} ]

[q_1=1-sqrt{k+1} ]

然后找(c_0,c_1)满足(c_0q_0+c_1q_1=a_1=1,c_0q_0^2+c_1q_1^2=a_2=2)

解得

[c_1=frac{1}{2sqrt{k+1}},c_2=frac{-1}{2sqrt{k+1}} ]

通项即为(a_n=c_0q_0^n+c_1q_1^n=frac{(1+sqrt{k+1})^n-(1-sqrt{k+1})^n}{2sqrt{k+1}})，下面令(r=sqrt{k+1})

[a_n=frac{(1+r)^n-(1-r)^n}{2r} ]

注意到分母，用二项式定理展开

[sumlimits_{i=0}^n inom{n}{i} r^i-sumlimits_{i=0}^n (-1)^iinom{n}{i}r^i ]

发现偶数项全部蒸发了，即

[2sumlimits_{2i+1 le n} inom{n}{2i+1}r^{2i+1} ]

把分母去掉

[a_n=sumlimits_{2i+1 le n} inom{n}{2i+1} r^{2i}=sumlimits_{2i+1le n} inom{n}{2i+1} (k+1)^i ]

太神奇辣

而我们仅要求(p mid a_p)，其中(p)是一个质数，有注意到(inom{p}{i}=frac{p!}{i!(p-i)!})，分母与(p)互质，讲除法转换成乘逆元，分子又有因数(p)，所以当(0<i<p)时(pmid inom{p}{i})（需要特判(inom{p}{0}=inom{p}{p}=1)）。

我们只关心大于(2)的质数(p)（(a_2=2)显然(2 mid a_2)），所以

[a_p=sumlimits_{i=0}^{(p-1)/2} inom{p}{2i+1}(k+1)^i equiv (k+1)^p pmod p ]

所以我们只要求一个(k)满足对于不在指定的数中的素数，都有(k+1 equiv 0 pmod p)，由于质数两两互质，由中国剩余定理可得最小的(k=prod p - 1)（(p)没有被指定且(1le p le n)）。

于是线性筛出(1...n)内的素数算上面那个东西就好了。

无解的情况就是指定的素数中有(2)的时候（与题目里不同，题目中是指定第(i)大的质数）。

---

但这题非常毒瘤...还要卡常.....

并不会一些奇怪的筛法...这里就提一下普通的线性筛如何卡常吧qwq...

建议不要用vector，vector就算开了c++11和O2还是慢.....

所以尽量用数组，另外bitset也不用了...bool数组挺快的感觉...

还有可以特判一下当前遍历到的数(i)是(2)的倍数的时候..

再写一写循环展开啥的...火车头也加上好了...

如果还卡不过就洗洗睡吧多交几次试试...

实在卡不过也没办法了...写出题人那种埃氏筛吧qwq

代码太丑就不放了qwq