Luogu

分析

设 $g_n$ 为 $n$ 的答案,则

$$ g_n=\begin{cases}1,&n=0\\\sum_{i=0}^nF_i\times g_{n-i},&n\geq 1\end{cases} $$

设 $F(x)$ 为 $F_i$ 的 OGF,$G(x)$ 为 $g_i$ 的 OGF,于是有

$$ G(x)=F(x)G(x)+1 $$

所以

$$ G(x)=\frac{1}{1-F(x)} $$

我们知道

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

所以

$$ \begin{aligned} G(x)&=\frac{1-x-x^2}{1-2x-x^2}\\ &=1+\frac{x}{1-2x-x^2}\\ &=1+\frac{x}{[1-(1+\sqrt{2})x][1-(1-\sqrt{2})x]}\\ &=1+\frac{1}{2\sqrt{2}}\left[\frac{1}{1-(1+\sqrt{2})x}-\frac{1}{1-(1-\sqrt{2})x}\right]\\ &=1+\sum_{i=0}^{+\infty}\frac{(1+\sqrt{2})^i-(1-\sqrt{2})^i}{2\sqrt{2}}x^i \end{aligned} $$

我们只需要求 $[x^n]G(x)$,即 $\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$,而 $2$ 在模 $10^9+7$ 意义下是有二次剩余的,所以直接计算即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int read() {
    int X=0; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=(10ll*X+c-'0')%(mod-1),c=getchar();
    return X;
}

int main() {
    int n=read();
    printf("%lld\n",14928400ll*(qpow(59713601,n)-qpow(940286408,n)+mod)%mod);
    return 0;
}
最后修改:2020 年 08 月 13 日 09 : 51 PM