介绍

生成函数可以解决形如 满足XX条件的方案数共有多少种 的问题,它也能够解决 推导通项公式 等问题,生成函数常常与多项式运算结合在一起。

定义

对于一个无限数列

$$a = \{a_0, a_1, a_2, …\}$$

它的生成函数为

$$f(x) = a_0 + a_1x + a_2x^2 + … = \sum\limits_{i=0}^{\infty}a_ix^i$$

其中 $x$ 的值并没有意义。

• 有限数列 $\{a_0, a_1, a_2, …, a_n\}$ 的生成函数就是 $f(x) = a_0 + a_1x + a_2x^2 + … + a_nx^n = \sum\limits_{i=0}^{n}a_ix^i$

• 我们定义 $[x^{k}]f(x)$ 为 $f(x)$ 表达式中,$x^k$ 的系数。(为了方便表达,有的时候也会使用 $a_k, b_k$)

封闭形式与展开形式

生成函数有 封闭形式展开形式 两种形态。

封闭形式适合进行生成函数之间的运算展开形式则可以得到生成函数各项的系数(通项公式),从而获得最终的答案(方案数的统计)。

例如,对于无限数列

$$\{1,1,1,1,…\}$$

它的生成函数展开形式为:

$$f(x) = 1+x+x^2+x^3+…$$

很明显这是一个等比数列,公比为 $x$,进行求和可以得到封闭形式:

$$f(x) = 1+x+x^2+x^3+… = \frac{1}{1-x}$$

一些常见的封闭式与展开式的对应

封闭形式 展开形式 数列 通项公式
$\frac{1}{1-x}$ $\sum\limits_{i=0}^{\infty}x^i = 1+x+x^2+x^3+…$ $\{1,1,1,1,…\}$ $b_k = 1$
$\frac{1}{(1-x)^2}$ $\sum\limits_{i=0}^{\infty}(i+1)x^i = 1+2x+3x^2+4x^3+…$ $\{1,2,3,4,…\}$ $b_k = k+1$
$\frac{1}{1-ax}$ $\sum\limits_{i=0}^{\infty}a^ix^i = 1+ax+a^2x^2+a^3x^3+…$ $\{1,a,a^2,a^3,…\}$ $b_k = a^{k}$
$\frac{1}{(1-ax)^n}$ $\sum\limits_{i=0}^{\infty}C_{(n-1)+i}^{(n-1)}a^ix^i$ $\{1, C_{n}^{1}a^1, C_{n+1}^{2}a^2,C_{n+2}^{3}a^3,…\}$ $b_k = C_{n+k-1}^{k}a^k$
$\frac{1}{1+x}$ $\sum\limits_{i=0}^{\infty}(-1)^ix^i = 1-x+x^2-x^3+…$ $\{1,-1,1,-1,…\}$ $b_k = -1^k$

证明

证明1

$$\frac{1}{1-x} = 1+x+x^2+x^3+…$$

证:等比数列,公比为 $x$。

证明2

$$\frac{1}{(1-x)^2} = 1+2x+3x^2+4x^3+…$$

证:因为

$$\frac{1}{(1-x)^2} = (\frac{1}{1-x})^2 = (1+x+x^2+x^3+…)^2$$

根据组合意义,对于 $x^k$,有 $(0,k),(1,k-1),…,(k,0)$ 共 $(k+1)$ 种组合方式,并且每一种的系数为 $1$,所以 $x^k$ 的系数为 $(k+1)$。

证明3

$$\frac{1}{1-ax} = 1+ax+a^2x^2+a^3x^3+…$$

证:等比数列,公比为 $ax$。

证明4

$$\frac{1}{(1-ax)^n} = \sum\limits_{i=0}^{\infty}C_{(n-1)+i}^{(n-1)}a^ix^i$$

证:因为

$$\frac{1}{(1-ax)^n} = (1+ax+a^2x^2+a^3x^3+…)^n$$

根据组合意义,对于 $x^k$ 而言,每个 $(1+ax+a^2x^2+a^3x^3+…)$ 都可以贡献给 $k$,而这样的式子有 $n$ 个。

所以相当于:

求 $a_1+a_2+…+a_n = k$ 的非负整数解的个数。

这是 小球放盒子 模型,$k$ 个球放入 $n$ 个盒子并且允许空盒,用隔板法即可,方案数为 $C_{(n-1)+k}^{(n-1)}$,这就是 $a^kx^k$ 的系数。

证明5

$$\frac{1}{1+x} = 1-x+x^2-x^3+…$$

等比数列,公比为 $-x$。

计算例子

例1

题意

求无限数列 $a_i = i^2$ 的生成函数。

分别求出展开式和封闭式。

展开式 $\Rightarrow$ 封闭式

数列 $a$ 为:

$$a = \{0,1,4,9,16,…\}$$

那么生成函数的展开式为:

$$f(x) = x + 4x^2 + 9x^3 + 16x^4 + … = \sum\limits_{i=1}^{\infty}i^2x^i$$

在推导生成函数的封闭式时,一个非常重要的 trick 是给展开式 乘上一个 $x$

那么乘上 $x$ 以后,相当于整个展开式向右移动了一位,对应的生成函数就是

$$xf(x) = 0 + x^2 + 4x^3 + 9x^4 + … = \sum\limits_{i=1}^{\infty}(i-1)^2x^i$$

所以两者相减,可得:

$$(1-x)f(x) = \sum\limits_{i=1}^{\infty}(i^2 - (i-1)^2)x^i = \sum\limits_{i=1}^{\infty}(2i-1)x^i$$

$$=2\sum\limits_{i=1}^{\infty}ix^i - \sum\limits_{i=1}^{\infty}x^i$$

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

• 注意到因为求和是从 $i=1$ 开始的,相当于 $i=0$ 的情况整体右移了一位,所以要乘上 $x$ 得到 $\frac{2x}{(1-x)^2}$

所以生成函数 $f(x)$ 的封闭式为:

$$f(x) = \frac{2x}{(1-x)^3} - \frac{x}{(1-x)^2} = \frac{x(x+1)}{(1-x)^3}$$

封闭式 $\Rightarrow$ 展开式

已知 $f(x)$ 的封闭式为

$$f(x) = \frac{x(x+1)}{(1-x)^3}$$

我们将其化简为上面 常用表 里面的组合,也就是 裂项

$$f(x) = \frac{x(x+1)}{(1-x)^3} = \frac{2x}{(1-x)^3} - \frac{x}{(1-x)^2}$$

考虑第 $k$ 项的系数,注意到我们可以将分子中的 $x$ 提出来,所以 $f(x)$ 的第 $k$ 项系数 $a_k$ 就等于 $g(x) = (\frac{2}{(1-x)^3} - \frac{1}{(1-x)^2})$ 的第 $(k-1)$ 项系数 $b_{k-1}$。

$$\frac{2}{(1-x)^3} = 2\sum\limits_{i=0}^{\infty}C_{2+i}^{2}x^i, ~ \frac{x}{(1-x)^2} = \sum\limits_{i=0}^{\infty}(i+1)x^i$$

所以 $g(x)$ 的第 $(k-1)$ 项系数为:

$$b_{k-1} = [x^{k-1}]2(\sum\limits_{i=0}^{\infty}C_{2+i}^{2}x^i) - \sum\limits_{i=0}^{\infty}(i+1)x^i = 2C_{k+1}^2 - k = k^2$$

所以 $f(x)$ 的第 $k$ 项系数为 $a_k = b_{k-1} = k^2$。

于是生成函数的展开式为:

$$f(x) = \sum\limits_{i=0}^{\infty}i^2x^i = x + 4x^2 + 9x^3 + 16x^4 + …$$

例2

题意

求斐波那契数列 $$f_0 = 0, f_1 = 1, f_i = f_{i-1} + f_{i-2}$$

的生成函数,分别求出展开式(通项公式)和封闭式。

封闭式

注意到

$$f(x) = f_0 + f_1x^1 + f_2x^2 + f_3x^3 + …$$

$$xf(x) = 0 + f_0x^1 + f_1x^2 + f_2x^3 + …$$

$$x^2f(x) = 0 + 0+ f_0x^2 + f_1x^3 + …$$

由于 $f_i = f_{i-1} + f_{i-2}$,所以:

$$f(x)(1-x-x^2) = f_0 + (f_1-f_0)x^1 = x$$

所以 $$f(x) = \frac{x}{1-x-x^2}$$

封闭式$\Rightarrow$展开式

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

我们希望将它转为表格中存在的形式,所以我们设:

$$(1-ax)(1-bx) = 1-x-x^2$$

可得 $a = \frac{1 + \sqrt 5}{2}, b = \frac{1 - \sqrt 5}{2}$

$$g(x) = \frac{f(x)}{x} = \frac{1}{(1-ax)(1-bx)}$$

那么要求 $f(x)$ 的第 $n$ 项系数,只要求 $g(x)$ 的第 $(n-1)$ 项系数即可。

因为

$$g(x) = \frac{1}{(1-ax)(1-bx)}$$ $$= \sum\limits_{i=0}^{\infty}a^ix^i * \sum\limits_{j=0}^{\infty}b^jx^j$$ $$= (1+ax+a^2x^2+a^3x^3+…) * (1+bx+b^2x^2+b^3x^3+…)$$

这是个卷积,那么 $g(x)$ 的第 $(n-1)$ 项系数为:

$$[x^{n-1}]g(x) = \sum\limits_{k=0}^{n-1}a^{k}b^{n-1-k}$$

$$=b^{n-1}\sum\limits_{k=0}^{n-1}a^{k}b^{-k}$$

$$=b^{n-1}\sum\limits_{k=0}^{n-1}(\frac{a}{b})^k$$

右边就是个等比数列求和了,公比为 $\frac{a}{b}$,最后可得

$$[x^n]f(x) = [x^{n-1}]g(x) = \frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n)$$

那么求出了 $f(x)$ 的通项公式,展开式也就可以写出来了。

例题

例1 洛谷P4721【模板】分治 FFT

题意

给定 $n-1$ 个非负整数 $g_1, g_2, … g_{n-1}$。

定义 $$f_0 = 1, f_i = \sum\limits_{j=1}^if_{i-j}g_j$$

求出 $f_1, f_2, …, f_{n-1}$,答案对 $998244353$ 取模。

其中,$2 \leq n \leq 10^5$

题解

看到 $\sum\limits_{j=1}^if_{i-j}g_j$ 就想到卷积,也就是多项式乘法。

那么令

$$f(x) = f_0 + f_1x^1 + f_x2x^2 + … + f_{n-1}x^{n-1}$$

$$g(x) = g_0 + g_1x^1 + g_x2x^2 + … + g_{n-1}x^{n-1}$$

$$h(x) = f(x)g(x)$$

则有:

$$[x^n]h(x) = \sum\limits_{i=0}^nf_ig_{n-i}$$

发现和 $f_n = \sum\limits_{j=1}^nf_{n-j}g_j$ 就差一个 $j=0$ 的情况(多了一个 $g_0f_n$),那么我们直接令 $g_0 = 0$ 就没问题了。

这样的话,当 $n=0$ 时,$h_0 = 0$,其他时候 $h_n = f_n$。

所以:

$$f(x)g(x) = h(x) = 0 + f_1x^1 + f_x2x^2 + … + f_{n-1}x^{n-1} = f(x) - f_0 = f(x) - 1$$

得到

$$f(x)(1-g(x)) = 1$$

$$f(x) = \frac{1}{1-g(x)}$$

多项式求逆即可。

代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = (1<<22) + 5;
// 板子省略
ll f[maxn], g[maxn], invG[maxn];
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n-1; i++) cin >> g[i];
    for (int i = 1; i <= n-1; i++) g[i] = (-g[i] + mod) % mod;
    g[0] = 1;
    poly_inverse(g, invG, n);
    for (int i = 0; i < n; i++) {
        cout << (invG[i]) % mod << " ";
    }
    cout << endl;    
}

注意点

多项式的题目中,要注意几个点:

  1. 看到 $\sum_{i=0}^n f_ig_{n-i}$ 这种形式,即系数之和无论 $i$ 为多少,均为定值的,就想到 卷积,从而想到 多项式乘法。
  2. 转化出来的新多项式要注意 常数项。也就是代入 $n=0$ 判断一下左右两边是否相等。

例2 洛谷P4841 集训队作业2013 城市规划

题意

求 $n$ 个节点的 简单(无重边无自环)有标号无向 连通 图数目。答案对 $1004535809$ 取模。

其中,$n \leq 130000$

题解

小tips:计数问题可以想想 dp 怎么做。

设 $f_n$ 为 $n$ 个节点的 简单(无重边无自环)有标号无向 连通 图数目。

设 $g_n$ 为 $n$ 个节点的 简单(无重边无自环)有标号无向图数目。(区别在于不需要连通)

发现在一个完全图中有 $C_n^2$ 条边,每条边可以选或者不选,那么

$$g_n = 2^{C_n^2}$$

我们想要用另外一种方式表示 $g_n$,可以枚举 节点 $1$ 所在的联通块的大小:

  1. 节点 $1$ 所在联通块大小为 $1$ 时,方案数为:$f_1g_{n-1}$
  2. 节点 $1$ 所在联通块大小为 $2$ 时,方案数为:$C_{n-1}^{1}f_2g_{n-2}$
  3. 节点 $1$ 所在联通块大小为 $k$ 时,方案数为:$C_{n-1}^{k-1}f_kg_{n-k}$

所以联通块大小 $1$ 枚举到 $n$,有:

$$g_n = \sum\limits_{i=1}^n C_{n-1}^{i-1}f_ig_{n-i}$$

看到 $f_ig_{n-i}$ 的形式马上想到 卷积,也就是 多项式乘法。

但是有一个 $C_{n-1}^{i-1}$,我们把它拆开即可:

$$g_n = \sum\limits_{i=1}^n C_{n-1}^{i-1}f_ig_{n-i}$$

$$g_n = (n-1)!\sum\limits_{i=1}^n\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}$$

$$F_i = \frac{f_i}{(i-1)!}, G_i = \frac{g_i}{i!}$$

则有:

$$\frac{g_n}{(n-1)!} = \sum\limits_{i=1}^nF_iG_{n-i}$$

$$F(x) = 0 + F_1x + F_2x^2 + … + F_{n}x^n$$

$$G(x) = G_0 + G_1x + G_2x^2 + … + G_{n}x^n$$

则可以发现,(注意 $F(x)$ 的常数项为 $0$):

$$[x^n]\frac{g(x)}{(n-1)!} = [x^n]F(x)G(x)$$

注意到 $\frac{1}{(n-1)!}$ 是不可以提到外面去的,因为它与 $n$ 有关。

定义

$$H_n = \frac{g_n}{(n-1)!}, H_0 = 0$$

• $H_0 = 0$ 是因为:如果我们代入 $n=0$ 进 $[x^n]\frac{g(x)}{(n-1)!} = [x^n]F(x)G(x)$,会发现右边为 $0$,所以 $H_0 = 0$。

则有:

$$[x^n]H(x) = [x^n]F(x)G(x)$$

注意到左右两个多项式的 $n$ 次项系数对于任何 $n$ 都相等,所以有

$$H(x) = F(x)G(x)$$

$$F(x) = \frac{H(x)}{G(x)}$$

由于 $H(x), G(x)$ 均已知,多项式求逆即可求出 $F(x)$,在每一项系数上乘以 $(n-1)!$ 即可得到 $f(x)$。

代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 1004535809;
const int maxn = (1<<22) + 5;
// 多项式板子部分省略

ll f[maxn], g[maxn], G[maxn], invG[maxn], fac[maxn], invfac[maxn], h[maxn];
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}


int main() {
    int n; cin >> n;
    g[0] = 1;
    for (ll i = 1; i <= n; i++) {
        g[i] = qpow(2, i * (i-1) / 2);
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * (ll)i % mod;
    invfac[n] = qpow(fac[n], mod-2);
    for (int i = n-1; i >= 0; i--) invfac[i] = invfac[i+1] * (ll)(i+1) % mod;

    h[0] = 0;
    for (int i = 0; i <= n; i++) G[i] = g[i] * invfac[i] % mod;
    for (int i = 1; i <= n; i++) h[i] = g[i] * invfac[i-1] % mod;
    poly_inverse(G, invG, n+1);
    poly_multiply(h, n+1, invG, n+1, f);

    f[n] = f[n] * fac[n-1] % mod;
    cout << f[n] << endl;
}

注意点

  1. 计数问题,想想 dp 思路?
  2. 项数不能随便提出去,尤其是与 $n$ 有关的。遇到项数就转化成一个新的多项式来处理。
  3. 如果对于任何 $n$,左右两边的多项式第 $n$ 项系数相同,则这两个多项式相等。

例3 CF438E The Child and Binary Tree

题意

给定一个包含 distinct 正整数的集合 $\{c_1, c_2, …, c_n\}$。

给定整数 $m$,对于所有的 $s \in [1,m]$,求出满足以下条件的本质不同的 带点权二叉树个数:

  1. 每个顶点的权值必须在 $\{c_1, c_2, …, c_n\}$ 中。
  2. 所有顶点的权值之和为 $s$。

答案对 $998244353$ 取模。

其中,$1 \leq n,m,c_i \leq 10^5$。

题解

首先用 dp 的思路:

设 $f_n$ 为权值和为 $n$ 的二叉树个数(根的值 尚未确定),设 $g_n$ 为权值和为 $n$ 的二叉树个数(根的值 已经确定)。

则我们可以得出:

$$f_n = \sum\limits_{i=1}^n g_{n-c_i}$$

$$g_n = \sum\limits_{i=0}^n f_if_{n-i}$$

解释:

对于第一个式子,我们枚举根的值即可。

对于第二个式子,由于根的值已经确定,所以只需要枚举左右子树的权值和即可。

我们看到 $g_n = \sum\limits_{i=0}^n f_if_{n-i}$,发现这就是个卷积,所以有

$$g(x) = f(x)^2$$

但第一个式子怎么办呢?这是个加法,无法表示为卷积?

注意到本题中所有的权值 $\leq 10^5$,我们不如定义 $h_i$ 为:

$$h_i = \begin{cases} 1 ~~~~ \text{if } i \in \{c_1, c_2, …, c_n\} \\
0 ~~~~ \text{if } i \notin \{c_1, c_2, …, c_n\} \end{cases}$$

则我们可以将 $f_n = \sum\limits_{i=1}^n g_{n-c_i}$ 转化为:

$$f_n = \sum\limits_{i=1}^nh_ig_{n-i}$$

这就又是个卷积了,代入 $n=0$ 可以发现:因为 $f_0 = g_0 = 1, h_0 = 0$,所以

$$f(x) = h(x)g(x) + 1 = h(x)f(x)^2 + 1$$

所以:

$$h(x)f(x)^2 - f(x) + 1 = 0$$

利用公式 $x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$ 有:

$$f(x) = \frac{1 \pm \sqrt{1-4h(x)}}{2h(x)}$$

有个问题,$h(x)$ 的常数项 $h(0) = 0$ 没法求逆?(注意到求逆的本质是 $h(x) * h^{-1}(x) = 1$)

没关系,没法求逆就乘到左边去,得到:

$$2f(x)h(x) = 1 \pm \sqrt{1-4h(x)}$$

代入 $x = 0$,由 $h(0) = 0$ 可以得到右边只能取 负号

所以再把 $h(x)$ 除回去,得到:

$$f(x) = \frac{1 - \sqrt{1-4h(x)}}{2h(x)}$$

上下同乘 $(1 + \sqrt{1-4h(x)})$ 得到:

$$f(x) = \frac{2}{1 + \sqrt{1-4h(x)}}$$

多项式求逆求出 $f(x)$ 即可。

代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = (1<<21) + 5;

int n,m;
ll h[maxn], H[maxn];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int c; cin >> c;
        h[c] = 1;
    }
    for (int i = 1; i <= 1e5; i++) {
        h[i] = 4LL * h[i] % mod;
        h[i] = (-h[i] + mod) % mod;
    }
    h[0] = (h[0] + 1) % mod;
    poly_sqrt(h, H, 1e5+1);
    H[0] = (H[0] + 1) % mod;
    memset(h, 0, sizeof(h));
    poly_inverse(H, h, 1e5+1);
    for (int i = 1; i <= m; i++) {
        cout << h[i] * 2LL % mod << "\n";
    }
}

例4 洛谷P4451 整数的lqp拆分

题意

给定正整数 $N$,对于所有可能的 $m > 0$,一个整数拆分是一个有序数组 $(a_1,a_2,…,a_m)$ 满足:

  1. $a_i > 0$
  2. $a_1 + a_2 + … + a_m = N$

我们定义斐波那契数列为:

$$F_0 = 0, F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2}$$

对于 $N$ 而言,它的一个整数拆分 $(a_1,a_2,…,a_m)$ 的权值为:

$$F_{a_1} * F_{a_2} * … * F_{a_m}$$

求所有可能的整数拆分的权值之和?形式化的,求:

$$\sum\limits_{(a_1,a_2,…,a_m)}\prod_{i=1}^mF_{a_i}$$

答案对 $10^9 + 7$ 取模。

其中,$1 \leq N \leq 10^{10000}$

题解

我们发现这个 $\sum$ 和 $\prod$ 的顺序其实可以调换的。

所以我们枚举一下第一个元素 $a_1$,设 $f_n$ 为我们所求的值,问题就转化为:

$$f_n = \sum\limits_{j=1}^nF_j*f_{n-j}$$

其中,$f_0 = 1$。

所以设

$$G(x) = F(x)f(x)$$

$$G(0) = F(0)f(0) = 0$$

所以有

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

得出

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

斐波那契数列的生成函数为(不记得了就手推一下):$$F(x) = \frac{x}{1-x-x^2}$$

所以得到:

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

我们发现这个常数项 $1$ 对我们的 $n$ 次项系数 $f_n$ 并没有任何影响,所以可以直接忽略。

现在我们需要裂项了,转化为表里面的形式:

$$f(x) = \frac{-x}{x^2+2x-1} = \frac{c}{1-ax} + \frac{d}{1-bx}$$

解方程就可以得到

$$b = -1\pm \sqrt 2, a = -1 \mp \sqrt 2$$

发现随便取哪个符号都一样(毕竟 $a,b$ 本就是对称的),所以有:

$$b = 1 + \sqrt 2, a = 1 - \sqrt 2, c = -\frac{1}{2\sqrt 2}, d = \frac{1}{2\sqrt 2}$$

所以

$$f(x) = \frac{c}{1-ax} + \frac{d}{1-bx}$$

$f(x)$ 的第 $n$ 次项系数为:

$$[x^n]f(x) = -\frac{1}{2 \sqrt 2}(a^n - b^n) = \frac{1}{2\sqrt 2}[(1+\sqrt 2)^n - (1-\sqrt 2)^n]$$

最后的问题就是如何求 $(1+\sqrt 2)^n - (1-\sqrt 2)^n$ ?

我们需要先知道 $\sqrt 2$ 在 $\text{mod }10^9 + 7$ 意义下的值,可以利用二次剩余解决。

然后对于 $n$,我们发现它出现在指数位置,而我们由费马小定理知道 $\forall a, a^{P-1} \equiv 1 (\text{mod } P)$

所以,我们只要将 $n$ 取一个 $n = n(\text{mod } (P-1))$ 即可。

代码
#include <bits/stdc++.h>
using namespace std;
const ll mod = 1e9+7;
const int maxn = 1e5+7;

// 求 sqrt(a) 在 mod P 下的值
// 调用 solve(a, P, r1, r2)
// 若有解,r1, r2 分别为两个解,其中 r1 小,r2 大
// 若无解,r1 == -1
namespace Quadratic_residue {
    ll qpow(ll a, ll b, ll P) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }

    bool check_if_residue(ll x, ll P) {
        return qpow(x, (P - 1) >> 1, P) == 1;
    }

    void solve(ll a, ll P, ll& r1, ll& r2) {
        if (a <= 1) {
            r1 = a, r2 = P - a; return;
        }
        if (!check_if_residue(a, P)) {
            r1 = -1; return;
        }
        ll x;
        while (1) {
            x=1ll*rand()*rand()%P;
            if (qpow((x*x-a+P)%P,(P-1)/2, P)!=1) break;
        }
        ll w=(x*x-a+P)%P;
        pll res = {1,0}, t = {x,1};
        auto Mul=[&](pll a,pll b){ // 复数乘法
            ll x=(1ll*a.first*b.first+1ll*a.second*b.second%P*w)%P;
            ll y=(1ll*a.first*b.second+1ll*a.second*b.first)%P;
            return make_pair(x,y);
        };
        ll d=(P+1)/2;
        while (d) {
            if(d&1) res=Mul(res,t);
            t=Mul(t,t);
            d>>=1;
        }
        ll r = (res.first % P + P) % P;
        r1 = min(r, (P - r) % P);
        r2 = max(r, (P - r) % P);
    }
};

ll s2, _;  //sqrt(2)
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll a) {
    return qpow(a, mod-2);
}

ll readBigint() {
    string s; cin >> s;
    ll res = 0;
    for (int i = 0; i < s.size(); i++) {
        res = res * 10 % (mod - 1);
        res = (res + (s[i] - '0')) % (mod - 1);
    }
    return res;
}

int main() {
    ll n = readBigint();
    Quadratic_residue::solve(2, mod, s2, _);

    ll ans = qpow((1LL + s2) % mod, n) - qpow((1LL - s2 + mod) % mod, n);
    ans = (ans + mod) % mod;
    ans = ans * inv(2LL * s2 % mod) % mod;
    cout << ans << "\n";
}

注意事项

$$a^b \equiv a^{b \text{ mod } (P-1)} (\text{mod } P)$$

参考链接

  1. https://blog.csdn.net/a_forever_dream/article/details/102594411