P4451 [国家集训队]整数的lqp拆分

柔光的暖阳◎ 2021-10-26 16:20 293阅读 0赞

[传送门][Link 1]

显然有 $dp$，设 $f\_i$ 为 $i$ 的 $lqp$ 拆分的权值和，考虑枚举拆分的最后一个数，不妨设 $f\_0=1$

那么有 $f\_i=\\sum\_\{j=1\}^\{i\}f\_\{i-j\}F\_\{j\}$ ，$F\_\{i\}$ 表示斐波那契数列的第 $i$ 项

变一下就是 $f\_i=\\sum\_\{j=0\}^\{i-1\}f\_\{j\}F\_\{i-j\}$，这样是 $n^2$ 的

然后有 $3$ 种做法，先从最容易的讲起

$1.$ 直接打表....，发现 $f\_i=2f\_\{i-1\}+f\_\{i-2\}$

$2.$ 稍微动点脑子，$f\_\{i+1\}-f\_\{i\}=\\sum\_\{j=0\}^\{i\}f\_\{j\}F\_\{i+1-j\}-\\sum\_\{j=0\}^\{i-1\}f\_\{j\}F\_\{i-j\}$

$=\\sum\_\{j=0\}^\{i-1\}f\_\{j\}F\_\{i+1-j\}+f\_i-\\sum\_\{j=0\}^\{i-1\}f\_\{j\}F\_\{i-j\}$

$=\\sum\_\{j=0\}^\{i-1\}f\_\{j\}(F\_\{i+1-j\}-F\_\{i-j\})+f\_i$

$\\sum\_\{j=0\}^\{i-1\}f\_\{j\}F\_\{i-1-j\}+f\_i$

发现当 $j=i-1$ 时和式为 $0$，所以 $=\\sum\_\{j=0\}^\{i-2\}f\_\{j\}F\_\{i-1-j\}+f\_i$

因为 $f\_\{i-1\}=\\sum\_\{j=0\}^\{i-2\}f\_\{j\}F\_\{i-1-j\}$，所以 $f\_\{i+1\}-f\_\{i\}=f\_\{i-1\}+f\_\{i\}$

即 $f\_\{i+1\}=2f\_\{i\}+f\_\{i-1\}$

上面两种方法都可以比较正常地推出式子，然后也可以矩阵优化到 $ \\log n$

$3.$ 考虑生成函数，设 $A(x)$ 为 $f$ 的生成函数，$G(x)$ 为 $F$ 的生成函数

那么有 $A(x)=\\sum\_\{n=0\}^\{\\infty \}(f\_n)x^n$，代入得到

$A(x)=\\sum\_\{n=0\}^\{\\infty\}(\[n==0\]+\\sum\_\{i=0\}^\{n-1\}f\_iF\_\{n-i\})x^n$，感觉这个 $\[n==0\]$ 很烦，提出来

$A(x)=1+\\sum\_\{n=1\}^\{\\infty\}(\\sum\_\{i=0\}^\{n-1\}f\_iF\_\{n-i\})x^n$，发现 $n=0$ 时式子没贡献，$i=n$ 时式子也没贡献，所以

$A(x)=1+\\sum\_\{n=0\}^\{\\infty\}(\\sum\_\{i=0\}^\{n\}f\_iF\_\{n-i\})x^n$，这样我们就把右边变成卷积形式了

$A(x)=1+A(x)G(x)$，所以 $A(x)=\\frac\{1\}\{1-G(x)\}$，因为 $G(x)=\\frac\{x\}\{1-x-x^2\}$，代入得到

$A(x)=\\frac\{1\}\{1-\\frac\{x\}\{1-x-x^2\}\}$

$A(x)=\\frac\{1-x-x^2\}\{1-2x-x^2\}$

$A(x)=1+\\frac\{x\}\{1-2x-x^2\}$，然后经过一些数学技巧，得到

$A(x)=1+\\frac\{x\}\{(1-(1+\\sqrt2)x)(1-(1-\\sqrt2)x)\}$

设 $a=1-(1+\\sqrt2)x,b=1-(1-\\sqrt2)x$，那么有 $a-b=1-1x-\\sqrt2x-1+1x-\\sqrt2x=-2\\sqrt2x$，则

$A(x)=1+\\frac\{1\}\{2\\sqrt2\}(\\frac\{b-a\}\{ab\})$

$A(x)=1+\\frac\{1\}\{2\\sqrt2\}(\\frac\{1\}\{a\}-\\frac\{1\}\{b\})$ 重新带回去得到

$A(x)=1+\\frac\{1\}\{2\\sqrt2\}(\\frac\{1\}\{1-(1+\\sqrt2)x\}-\\frac\{1\}\{1-(1-\\sqrt2)x\})$，因为 $\\frac\{1\}\{1-x\}=\\sum\_\{i=0\}^\{\\infty \}x^i$ 所以

$A(x)=1+\\frac\{1\}\{2\\sqrt2\}(\\sum\_\{i=0\}^\{\\infty \}((1+\\sqrt2)x)^i-\\sum\_\{i=0\}^\{\\infty \}((1-\\sqrt2)x)^i)$

$A(x)=1+\\frac\{1\}\{2\\sqrt2\}\\sum\_\{i=0\}^\{\\infty \}((1+\\sqrt2)^i-(1-\\sqrt2)^i)x^i$，倒回去得到

$f\_i=\\frac\{(1+\\sqrt2)^i-(1-\\sqrt2)^i\}\{2\\sqrt2\}$

然后可以本机打表求出 $C^2 \\equiv 2( \\mod 1e9+7)$，那么 $\\sqrt2$ 在模 $1e9+7$ 下的逆元即为 $C$

然后直接快速幂即可

代码？这么好写就不用了吧...

转载于:https://www.cnblogs.com/LLTYYC/p/11371854.html

[Link 1]: https://www.luogu.org/problem/P4451

P4451 [国家集训队]整数的lqp拆分

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关整体二分+洛谷P1527 [国家集训队]矩阵乘法

相关洛谷P1792——[国家集训队]种树

相关【国家集训队】Tree II

相关 PTA--整数拆分

相关 343. 整数拆分

相关 190512 | 整数拆分

相关 [国家集训队]航班安排

相关洛谷 P4827 [国家集训队] Crash 的文明世界

相关 [国家集训队]拉拉队排练

相关 P4451 [国家集训队]整数的lqp拆分