刚刚学了生成函数, 真觉得是个巧妙的东西
我们不妨设答案为 , 它的生成函数是 , 斐波那契的生成函数是
考虑每个 Fi 对当前 gn 的贡献, 显然有
也就是
又因为 , 所以
因式分解一下
待定系数
解得
如何将G展开成多项式 ? 我开始也不理解, 我们先倒着来
令
则
相减就有
这里相当于
于是
然后求二次剩余, 发现
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll Mod = 1e9+7, inv2 = (Mod+1)>>1, sqr2 = 59713600; int n; ll mul(ll a, ll b){ return a * b % Mod;} ll add(ll a, ll b){ return (a+b) >= Mod ? (a+b-Mod) : (a+b);} ll dec(ll a, ll b){ return (a-b) < 0 ? (a-b+Mod) : (a-b);} ll power(ll a, ll b){ ll ans = 1; for(;b;b>>=1){ if(b&1) ans = mul(ans, a); a = mul(a, a); } return ans; } int main(){ scanf("%d", &n); ll tmp = mul(mul(inv2, inv2), sqr2); ll tmp1 = power(add(1, sqr2), n); ll tmp2 = power(dec(1, sqr2), n); printf("%lld", mul(tmp, dec(tmp1, tmp2))); }
