2020-2021:teams:legal_string:jxm2001:生成函数_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:生成函数_1 [2020/08/13 20:59] jxm2001 |
2020-2021:teams:legal_string:jxm2001:生成函数_1 [2020/08/21 20:48] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 278: | 行 278: | ||
| ==== 例题五 ==== | ==== 例题五 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4451|洛谷p4451]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 求 $\sum\prod_{i=1}^mF_{a_i}$，其中 | ||
| + | |||
| + | - $m\gt 0$ | ||
| + | - $a_i\gt 0$ | ||
| + | - $sum_{i=1}^m a_i=n$ | ||
| + | - $F$ 为斐波那契数列，且 $F_0=0,F_1=1$ | ||
| + | |||
| + | 答案对 $10^9+7$ 取模。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 先考虑 $m=1$ 的生成函数，有 $G(x)=\sum_{i=0}^n F_ix^i$。 | ||
| + | |||
| + | 于是答案的生成函数为 $H(x)=\sum_{m=1}^{\infty} G^m(x)=\cfrac {G(x)}{1-G(x)}$，接下来考虑求解 $G(x)$。 | ||
| + | |||
| + | 有 $G(x)-xG(x)-x^2G(x)=F_0+F_1x-F_0=x$，于是 $G(x)=\cfrac x{1+x+x^2}$，代入可得 $H(x)=\cfrac {x}{1-2x-x^2}$。 | ||
| + | |||
| + | 于是有 $(1-2x-x^2)H(x)=x$，于是 $h_n=2h_{n-1}+h_{n-2}+[n==1]$。 | ||
| + | |||
| + | 通过特征根求解得 $h_n=\cfrac {\sqrt 2}4(1+\sqrt 2)^n-\cfrac {\sqrt 2}4(1-\sqrt 2)^n$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXL=1e4+5,Mod=1e9+7,sqrt2=59713600,inv4=250000002; | ||
| + | int quick_pow(int a,int b){ | ||
| + | int ans=1; | ||
| + | while(b){ | ||
| + | if(b&1)ans=1LL*ans*a%Mod; | ||
| + | a=1LL*a*a%Mod; | ||
| + | b>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | char buf[MAXL]; | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%s",buf); | ||
| + | int n=0,len=strlen(buf); | ||
| + | _for(i,0,len) | ||
| + | n=(10LL*n+buf[i]-'0')%(Mod-1); | ||
| + | int ans=1LL*(quick_pow(1+sqrt2,n)-quick_pow(1-sqrt2,n))*sqrt2%Mod*inv4%Mod; | ||
| + | enter((ans+Mod)%Mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 例题六 ==== | ||
| [[https://ac.nowcoder.com/acm/contest/5670/C|牛客暑期多校(第五场) C 题]] | [[https://ac.nowcoder.com/acm/contest/5670/C|牛客暑期多校(第五场) C 题]] | ||
| 行 365: | 行 418: | ||
| </hidden> | </hidden> | ||
| - | ==== 例题六 ==== | + | ==== 例题七 ==== |
| [[https://www.luogu.com.cn/problem/CF923E|CF923E]] | [[https://www.luogu.com.cn/problem/CF923E|CF923E]] | ||
| 行 513: | 行 566: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
2020-2021/teams/legal_string/jxm2001/生成函数_1.1597323564.txt.gz · 最后更改: 2020/08/13 20:59 由 jxm2001
