题解 P6112 【直接自然溢出啥事没有加强版】

我也在想此题如何用$O(n)$解决，然后看到了这个题，就有了这个题解。  
由于我比较懒，以下的函数均省略$(x)$

---
引理：设连续可导函数$F_1,F_2,G$满足$G^2+F_1G+F_2=0$，那么$G$也满足$(4F_2-F_1^2)G'+(F_1F_1'-2F_2')G+2F_1'F_2-F_1F_2'=0$。  
证明（懒得看就算）：原式对$x$求导得
$$2GG'+F_1'G+F_1G'+F_2'=0$$
即
$$G'=-\frac{F_1'G+F_2'}{2G+F_1}=-\left(\frac{F_1'}{2}+\frac{F_2'-\frac{F_1F_1'}{2}}{2G+F_1}\right)$$
另一方面，原式等价于
$$\frac{G^2+F_1G+F_2}{2G+F_1}=0$$
即
$$\frac{G}{2}+\frac{F_1}{4}+\frac{F_2-\frac{F_1^2}{4}}{2G+F_1}=0$$
从而
$$\frac{1}{2G+F_1}=-\frac{2G+F_1}{4F_2-F_1^2}$$
代入后化简即得证。

---
记$A_0$为程序片段数量的生成函数，$A_1$为语句数量的生成函数，$A_2$为语句块数量的生成函数，$A_3$为函数的生成函数，$A_4$为值数量的生成函数  
那么有
$$\begin{cases}A_0=1+A_0A_1\\A_1=x+A_2+xA_4\\A_2=x^2A_0\\A_3=x^2A_2+x^4A_2+x^2A_3\\A_4=A_3+x^2A_4\end{cases}$$
关于$A_4$需要提的一点就是：直接把函数作为值（总是合法），在函数右端加括号作为值（总是合法），在值的两端加括号得到值（合法当且仅当这个值不能作为函数），注意到所有的函数都是值，因此$A_4=A_3+x^2A_3+x^2(A_4-A_3)$  
由上面的方程组解得
$$(x^7+x^6+x^5-2x^4+x^2)A_0^2+(x^5-x^4-2x^3+2x^2+x-1)A_0+(x^4-2x^2+1)=0$$
###### （注：用NTT或分治NTT直接解理论上能获得30pts,实际上懒得写）
## 请注意以下过于暴力！！！
由引理，得下面的定理：  
设生成函数$G$满足$F_1G^2+F_2G+F_3=0$（其中$F_1,F_2,F_3$均是连续可导函数），那么$G$也满足$F_1(4F_1F_3-F_2^2)G'+(F_1F_2F_2'-F_1'F_2^2-2F_1^2F_3'+2F_1F_1'F_3)G+2F_1F_2'F_3-F_1'F_2F_3-F_1F_2F_3'=0$。  
这是因为
$$G^2+\frac{F_2}{F_1}G+\frac{F_3}{F_1}=0$$
$$\left(\frac{4F_3}{F_1}-\frac{F_2^2}{F_1^2}\right)G'+\left(\frac{F_2}{F_1}\cdot\frac{F_2'F_1-F_2F_1'}{F_1^2}-2\cdot\frac{F_3'F_1-F_3F_1'}{F_1^2}\right)G+2\cdot\frac{F_2'F_1-F_2F_1'}{F_1^2}\cdot\frac{F_3}{F_1}-\frac{F_3'F_1-F_3F_1'}{F_1^2}\cdot\frac{F_2}{F_1}=0$$
$$F_1(4F_1F_3-F_2^2)G'+(F_1F_2F_2'-F_1'F_2^2-2F_1^2F_3'+2F_1F_1'F_3)G+2F_1F_2'F_3-F_1'F_2F_3-F_1F_2F_3'=0$$
令
$$F_1=x^7+x^6+x^5-2x^4+x^2,F_2=x^5-x^4-2x^3+2x^2+x-1,F_3=x^4-2x^2+1$$
则
$$F_1'=7x^6+6x^5+5x^4-8x^3+2x,F_2'=5x^4-4x^3-6x^2+4x+1,F_3'=4x^3-4x$$
使用上面的定理得
$$\begin{aligned}&(4x^{18}+7x^{17}+5x^{16}-20x^{15}-33x^{14}+5x^{13}+55x ^{12}+42x^{11}-67x^{10}-63x^9+59x^8+40x^7-31x^6-13x^5+ 9x^4+2x^3-x^2)A_0'\\&+(6x^{17}+8x^{16}-4x^{15}-30x^{14}-63x^{13}+29x^{12}+111x^{11}+27x^{10}-94x^9-78x^8+70x^7+64x^6-39x^5-23x^4+ 15x^3+3x^2-2x)A_0\\&+(-x^{15}+3x^{14}+11x^{13}-15x^{12}-30x^{11}+22x^{10}+40x ^9-6x^8-37x^7-9x^6+27x^5+5x^4-12x^3+2x)=0\end{aligned}$$
然而通过敏锐的观察力可以发现这个式子可以两边同时约去$x(x-1)(x+1)$，这样就有
$$\begin{aligned}&(4x^{15}+7x^{14}+9x^{13}-13x^{12}-24x^{11}-8x^{10}+31x^9+34x^8-36x^7-29x^6+23x^5+11x^4-8x^3-2x^2+x)A_0'\\&+(6x^{14}+8x^{13}+2x^{12}-22x^{11}-61x^{10}+7x^9+50x^8+34x^7-44x^6-44x^5+26x^4+20x^3-13x^2-3x+2)A_0\\&+(-x^{12}+3x^{11}+10x^{10}-12x^9-20x^8+10x^7+20x^6+4x^5-17x^4-5x^3+10x^2-2)=0\end{aligned}$$
这样就成功地干掉了$A_0^2$  
设第$n$项的答案为$f_n$  
两边取$n$次项系数，有
$$\begin{aligned}&nf_n-2(n-1)f_{n-1}-8(n-2)f_{n-2}+11(n-3)f_{n-3}+23(n-4)f_{n-4}-29(n-5)f_{n-5}-36(n-6)f_{n-6}+34(n-7)f_{n-7}\\&+31(n-8)f_{n-8}-8(n-9)f_{n-9}-24(n-10)f_{n-10}-13(n-11)f_{n-11}+9(n-12)f_{n-12}+7(n-13)f_{n-13}+4(n-14)f_{n-14}\\&+2f_n-3f_{n-1}-13f_{n-2}+20f_{n-3}+26f_{n-4}-44f_{n-5}-44f_{n-6}+34f_{n-7}+50f_{n-8}+7f_{n-9}-61f_{n-10}-22f_{n-11}+2f_{n-12}+8f_{n-13}+6f_{n-14}=0\end{aligned}$$
即
$$\begin{aligned}\\&(n+2)f_n-(2n+1)f_{n-1}-(8n-3)f_{n-2}+(11n-13)f_{n-3}+(23n-66)f_{n-4}-(29n-101)f_{n-5}-(36n-172)f_{n-6}+(34n-204)f_{n-7}\\&+(31n-198)f_{n-8}-(8n-79)f_{n-9}-(24n-179)f_{n-10}-(13n-121)f_{n-11}+(9n-106)f_{n-12}+(7n-83)f_{n-13}+(4n-50)f_{n-14}\\&-[n=12]+3[n=11]+10[n=10]-12[n=9]-20[n=8]+10[n=7]+20[n=6]+4[n=5]-17[n=4]-5[n=3]+10[n=2]-2[n=0]=0\end{aligned}$$
~~不知道还能不能化简~~  
这样就可以$O(n)$解决此题了  
欢迎各位大佬前来吊打我，方法包括但不限于：用低于$O(n)$的算法切了此题；用更短的式子切了此题；在$\bmod 2^{64}$的意义下切了此题。  
本文即将同步发表于![我的博客](https://01191020csl.github.io)
### Update on 2020.02.21:
1.倒数第二个递推式少考虑了最后的常多项式（但结论是对的），由于~~我懒~~我觉得你们不想再看公式了，因此不给出正确的过程（并且可以自己复原出来）  
2.链接被打成图片了：本文即将同步发表于[我的博客](https://01191020csl.github.io)

正在渲染内容...

题解 P6112 【直接自然溢出啥事没有 加强版】

题解 P6112 【直接自然溢出啥事没有加强版】