『洛谷』递归

入门级-递归

这里不得不推崇一下 Python 的装饰器 cache(3.9以上版本才有的，3.2以上的用 lru_cache)，记忆化递归神器！

---

P1028 [NOIP2001 普及组] 数的计算

题目描述

我们要求找出具有下列性质数的个数(包含输入的正整数 \(n\))。

先输入一个正整数 \(n\)(\(n \le 1000\)),然后对此正整数按照如下方法进行处理：

1. 不作任何处理；

2. 在它的左边加上一个正整数,但该正整数不能超过原数的一半；

3. 加上数后,继续按此规则进行处理,直到不能再加正整数为止。

输入格式

\(1\) 个正整数 \(n\)(\(n \le 1000\))

输出格式

\(1\) 个整数，表示具有该性质数的个数。

输入输出样例

输入: #1

6

输出: #1

6

说明&提示

满足条件的数为

6，16，26，126，36，136

解题思路

题目的说明有点模糊，从示例和解释中可以看到，所谓“原数”是指最初的数字或者说新加上的数字

可以记忆化递归、动态规划、打表

解答代码

动态规划

#include <cstdio>
#include <vector>
using namespace std;

int NumberCount(int n);

int main() {
    int s;
    scanf("%d", &s);
    printf("%d", NumberCount(s));
    return 0;
}

int NumberCount(int n) {
    if (n <= 1) return 1;
    int ed = (n >> 1) + 1;
    // dp[i] 表示 小于等于 i 的数字之和
    vector<int> dp(ed);
    dp[1] = 1;
    for (int i = 2; i < ed; ++i) {
        // dp[i] = 第 i 个数字的种类数 + 前 i - 1 个数字的种类和
        // dp[i] = dp[i >> 1] + 1   +  dp[i - 1]
        dp[i] = dp[i / 2] + dp[i - 1] + 1;
    }
    // 第 n 个数字的种类数为 dp[n >> 1] + 1
    return dp[ed - 1] + 1;
}

半打表半递推: 打表体现在使用静态变量来记录并静态计算，重复实例化类并不会多次计算，而只需从静态变量中取值即可（不太能确定OJ的机制，所以这个机制不一定能起效）

import Java.util.*;

public class Main {
    static int[] dp = new int[1007];
    static {
        dp[1] = 1;
        for (int i = 2; i < 1007; ++i) {
            dp[i] = dp[i >> 1] + 1 + dp[i - 1];
        }
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        System.out.println(new Main().NumberCount(n));
    }

    public int NumberCount(int n) {
        return dp[n >> 1] + 1;
    }
}

记忆化递归

from functools import lru_cache
@lru_cache(None)
def NumberCount(n: int) -> int:
    if n == 1:
        return 1
    ans = 1  # n 本身也是符合规则的
    for i in range(1, n // 2 + 1):
        ans += NumberCount(i)
    return ans

print(NumberCount(int(input())))

---

P1036 [NOIP2002 普及组] 选数

题目描述

已知 \(n\) 个整数 \(x_1,x_2,\cdots,x_n\)，以及 \(1\) 个整数 \(k\)（\(k\lt n\)）。从 \(n\) 个整数中任选 \(k\) 个整数相加，可分别得到一系列的和。例如当 \(n=4\)，\(k=3\)，\(4\) 个整数分别为 \(3,7,12,19\) 时，可得全部的组合与它们的和为：

\(3+7+12=22\)

\(3+7+19=29\)

\(7+12+19=38\)

\(3+12+19=34\)

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：\(3+7+19=29\)。

输入格式

第一行两个空格隔开的整数 \(n,k\)（\(1 \le n \le 20\)，\(k\lt n\)）。

第二行 \(n\) 个整数，分别为 \(x_1,x_2,\cdots,x_n\)（\(1 \le x_i \le 5\times 10^6\)）。

输出格式

输出一个整数，表示种类数。

输入输出样例

输入: #1

4 3
3 7 12 19

输出: #1

1

说明&提示

无

解题思路

递归思路很简单，对一个数有两种选择：可选可不选

一个剪枝思路：剩下的可选数的数量必须大于 K，否则无法选到足够多的数

另外，校验一个数是否是质数, 小技巧里面有提到

解答代码

递归 + 剪枝 + 米·拉素数测试 + 快速幂

#include <bits/stdc++.h> 
using namespace std;

long quickpow(int x, int y, int mod);
bool isprime(int x);
int Select(vector<int>& nums, int k);

int main() {
    int n, k, x;
    scanf("%d%d", &n, &k);
    vector<int> s(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x);
        s[i] = x;
    }
    printf("%d", Select(s, k));
    return 0;
}

int Select(vector<int>& nums, int k) {
    int n = nums.size();
    function<int(int, int, int)> dfs = [&](int i, int j, int s) -> int {
        if (j == 0) return isprime(s);
        if (i + j > n) return 0;    // 剪枝操作
        return dfs(i + 1, j, s) + dfs(i + 1, j - 1, s + nums[i]);
    };
    return dfs(0, k, 0);
}

long quickpow(int x, int y, int mod) {
    // x ^ y % mod 快速幂
    long ans = 1;
    while (y != 0) {
        if (y & 1 == 1)
            ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}

bool isprime(int x) {
    if (x < 3) return x == 2;
    if (x % 2 == 0) return false;
    int s[] = {2, 3, 5, 7, 11, 13, 17};
    int d = x - 1, r = 0;
    while (d % 2 == 0) {
        d >>= 1;
        ++r;
    }
    for (int b : s) {
        long y = quickpow(b, d, x);
        if (y == 1 || y == 0 || y == x - 1) continue;
        for (int i = 0; i < r; ++i) {
            y = y * y % x;
            if (y == x - 1 && i != r - 1) {
                y = 1;
                break;
            }
            if (y == 1) return false;
        }
        if (y != 1) return false;
    }
    return true;
}

import Java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = sc.nextInt();
        }
        sc.close();
        System.out.println(new Main().Select(nums, k));
    }

    private int[] nums;
    private int n;

    int Select(int[] nums, int k) {
        this.nums = nums;
        this.n = nums.length;
        return dfs(0, k, 0);
    }

    int dfs(int i, int k, int s) {
        if (k == 0)
            return isprime(s) ? 1 : 0;
        if (i + k > n)
            return 0;
        return dfs(i + 1, k, s) + dfs(i + 1, k - 1, s + nums[i]);
    }

    boolean isprime(int x) {
        // 朴素检查 判断 x 是否是素数
        if (x < 3)
            return x == 2;
        if (x % 2 == 0)
            return false;
        int n = (int) Math.sqrt(x) + 1;
        for (int i = 3; i < n; i += 2) {
            if (x % i == 0)
                return false;
        }
        return true;
    }
}

---

P1464 Function

题目描述

对于一个递归函数\(w(a,b,c)\)

• 如果\(a \le 0\) or \(b \le 0\) or \(c \le 0\)就返回值\(1\).
• 如果\(a\gt 20\) or \(b\gt 20\) or \(c\gt 20\)就返回\(w(20,20,20)\)
• 如果\(a\lt b\)并且\(b\lt c\) 就返回\(w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)\)
• 其它的情况就返回\(w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)\)

这是个简单的递归函数，但实现起来可能会有些问题。当\(a,b,c\)均为15时，调用的次数将非常的多。你要想个办法才行.

absi2011 : 比如 \(w(30,-1,0)\)既满足条件1又满足条件2
这种时候我们就按最上面的条件来算
所以答案为1

输入格式

会有若干行。

并以\(-1,-1,-1\)结束。

保证输入的数在\([-9223372036854775808,9223372036854775807]\)之间，并且是整数。

输出格式

输出若干行，每一行格式：

w(a, b, c) = ans

注意空格。

输入输出样例

输入: #1

1 1 1
2 2 2
-1 -1 -1

输出: #1

w(1, 1, 1) = 2
w(2, 2, 2) = 4

说明&提示

记忆化搜索

解题思路

提示已经说明了记忆化搜索，套上cache即可

解答代码

#include <cstdio>
#include <string>
#include <unordered_map>
using namespace std;

typedef long long ll;
unordered_map<string, ll> cache;

ll w(ll a, ll b, ll c) {
    string key = to_string(a) + "_" + to_string(b) + "_" + to_string(c);
    if (cache.find(key) != cache.end()) return cache[key];

    ll ans;
    if (a <= 0 || b <= 0 || c <= 0)
        ans = 1;
    else if (a > 20 || b > 20 || c > 20)
        ans = w(20, 20, 20);
    else if (a < b && b < c)
        ans = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    else
        ans = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    cache[key] = ans;
    return ans;
}

int main() {
    ll a, b, c;
    scanf("%lld%lld%lld", &a, &b, &c);
    while (a != -1 || b != -1 || c != -1) {
        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
        scanf("%lld%lld%lld", &a, &b, &c);
    }
    return 0;
}

import Java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong(), c = sc.nextLong();
        Main s = new Main();
        while (a != -1 || b != -1 || c != -1) {
            System.out.printf("w(%d, %d, %d) = %d\n", a, b, c, s.w(a, b, c));
            a = sc.nextLong();
            b = sc.nextLong();
            c = sc.nextLong();
        }
        sc.close();
    }

    public Map<String, Long> cache = new HashMap<>();

    public long w(long a, long b, long c) {
        String s = Long.toString(a) + "-" + Long.toString(b) + "-" + Long.toString(c);
        if (cache.containsKey(s))
            return cache.get(s);
        long ans;
        if (a <= 0 || b <= 0 || c <= 0)
            ans = 1;
        else if (a > 20 || b > 20 || c > 20)
            ans = w(20, 20, 20);
        else if (a < b && b < c)
            ans = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        else
            ans = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
        cache.put(s, ans);
        return ans;
    }
}

from functools import lru_cache

@lru_cache(None)
def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    if a < b and b < c:
        return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
    return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)
    
while 1:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    print("w({}, {}, {}) = {}".format(a, b, c, w(a, b, c)))

---

P5534 【XR-3】等差数列

题目描述

小 X 给了你一个等差数列的前两项以及项数，请你求出这个等差数列各项之和。

等差数列：对于一个 \(n\) 项数列 \(a\)，如果满足对于任意 \(i \in [1,n)\)，有 \(a_{i+1} - a_i = d\)，其中 \(d\) 为定值，则称这个数列为一个等差数列。

输入格式

一行 \(3\) 个整数 \(a_1, a_2, n\)，表示等差数列的第 \(1,2\) 项以及项数。

输出格式

一行一个整数，表示答案。

输入输出样例

输入: #1

1 2 3

输出: #1

6

输入: #2

-5 -10 5

输出: #2

-75

说明&提示

【样例 \(1\) 说明】

这个等差数列为 1 2 3，其各项之和为 \(6\)。

数据范围：

• \(|a_1|,|a_2| \le 10^6\)。
• \(3 \le n \le 10^6\)。

解题思路

等差数列求和？套公式就好啦

\[ s=\sum^n_{i = 1}a_i=\frac{(a_1+a_n) \times n}{2}=\frac{(2a_1+(n-1)\times d) \times n}{2} \]

再估算下数据范围：由 \(a_1, a_2\)能推出公差 \(d\) 可以达到 \(2 \times 10^6\), 由此答案可能达到 \(10^{12}\), 要使用 long

解答代码

#include <cstdio>
using namespace std;
typedef long long ll;
int main() {
    ll a1, a2, n;
    scanf("%lld%lld%lld", &a1, &a2, &n);
    printf("%lld", ((2 * a1 + (n - 1) * (a2 - a1)) * n) / 2);
    return 0;
}

import Java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a1 = sc.nextLong(), a2 = sc.nextLong(), n = sc.nextLong();
        sc.close();
        System.out.println(((2 * a1 + (n - 1) * (a2 - a1)) * n) / 2);
    }
}

a1, a2, n = map(int, input().split())
d = a2 - a1
print(((2 * a1 + (n - 1) * d) * n) // 2)

---

P1192 台阶问题

题目描述

有\(N\)级的台阶，你一开始在底部，每次可以向上迈最多\(K\)级台阶（最少\(1\)级），问到达第\(N\)级台阶有多少种不同方式。

输入格式

两个正整数N，K。

输出格式

一个正整数，为不同方式数，由于答案可能很大，你需要输出\(ans \bmod 100003\)后的结果。

输入输出样例

输入: #1

5 2

输出: #1

8

说明&提示

对于\(20\%\)的数据,有\(N ≤ 10, K ≤ 3\);

对于\(40\%\)的数据，有\(N ≤ 1000\);

对于\(100\%\)的数据，有\(N ≤ 100000,K ≤ 100\)。

解题思路

经典动态规划了，或者记忆化搜索

状态转移方程：\(dp[i]=\sum^{k}_{j = 1}dp[i - j]\)

或者更进一步矩阵快速幂

\[ \begin{bmatrix} dp[n] \\ dp[n - 1] \\ \dots \\ dp[n - k + 2] \\ dp[n - k + 1] \end{bmatrix} = \begin{bmatrix} 1 & 1 & \dots & 1 & 1 \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \dots & \dots & \dots & \dots & \dots \\ 0 & 0 & \dots & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} dp[n - 1] \\ dp[n - 2] \\ \dots \\ dp[n - k + 1] \\ dp[n - k] \end{bmatrix} \]

解答代码

动态规划 + 滚动数组

#include <cstdio>
#include <vector>
using namespace std;

int mod = 100003;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    if (k == 1) {
        printf("1");
        return 0;
    }
    // dp[i] 表示到达 i 位置的方案数
    vector<int> dp(k, 0);
    dp[0] = 1;
    dp[1] = 1;
    // s 表示 dp 数组的和
    int s = 2;
    for (int i = 2; i < k; ++i) {
        dp[i] = s;
        s = (s + dp[i]) % mod;
    }
    // 转移方程为 dp[i] = \sum^{k}_{j=1}dp[i - j]
    for (int i = k; i < n; ++i) {
        int tmp = dp[i % k];
        dp[i % k] = s;
        s = (s + mod - tmp + s) % mod;
    }
    if (n < k) s = dp[n];
    printf("%d", s);
    return 0;
}

矩阵快速幂

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        sc.close();
        System.out.println(new Main().Step(n, k, 100003));
    }

    int Step(int n, int k, int mod) {
        if (n <= 1 || k == 1)
            return 1;
        if (n <= k)
            return qpow(n - 1, mod);
        int[][] b = new int[k][1];
        int[][] e = new int[k][k];
        b[k - 1][0] = 1;
        b[k - 2][0] = 1;
        for (int i = k - 3; i >= 0; --i) {
            b[i][0] = (b[i + 1][0] * 2) % mod;
        }
        Arrays.fill(e[0], 1);
        for (int i = 1; i < k; ++i) {
            e[i][i - 1] = 1;
        }
        int[][] ans = matrix_mul(quickpow(e, n - k + 1, mod), b, mod);
        return ans[0][0];
    }

    int qpow(int n, int mod) {
        long x = 2;
        long ans = 1;
        while (n != 0) {
            if ((n & 1) == 1)
                ans = (ans * x) % mod;
            x = (x * x) % mod;
            n >>= 1;
        }
        return (int)ans;

    }

    public int[][] matrix_mul(int[][] A, int[][] B, int mod) {
        int r = A.length, c = B[0].length, d = B.length;
        if (d != A[0].length) // 不合理的矩阵乘法
            return null;
        int[][] s = new int[r][c];
        for (int i = 0; i < r; ++i) {
            for (int k = 0; k < d; ++k) {
                long tmp = (long) A[i][k];
                for (int j = 0; j < c; ++j) {
                    s[i][j] = (int) ((tmp * B[k][j] + s[i][j]) % mod);
                }
            }
        }
        return s;
    }

    public int[][] quickpow(int[][] A, int n, int mod) {
        int r = A.length;
        int[][] s = new int[r][r];
        for (int i = 0; i < r; ++i)
            s[i][i] = 1;
        while (n != 0) {
            if ((n & 1) == 1)
                s = matrix_mul(s, A, mod);
            A = matrix_mul(A, A, mod);
            n >>= 1;
        }
        return s;
    }
}

Python 使用 记忆化搜索最方便, 超过最大递归深度了 >_< 下面代码看看就好

from functools import lru_cache
mod = 100003

@lru_cache(None)
def dfs(n: int, k: int) -> int:
    """返回到达第 n 阶台阶的方案数"""
    if n < 0: return 0
    if n == 0 or n == 1:
        return 1
    return sum(dfs(n - i, k) for i in range(1, k + 1)) % mod

n, k = map(int, input().split())
print(dfs(n, k))

---

P1025 [NOIP2001 提高组] 数的划分

题目描述

将整数 \(n\) 分成 \(k\) 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：\(n=7\)，\(k=3\)，下面三种分法被认为是相同的。

\(1,1,5\); \(1,5,1\); \(5,1,1\).

问有多少种不同的分法。

输入格式

\(n,k\) （\(6<n \le 200\)，\(2 \le k \le 6\)）

输出格式

\(1\) 个整数，即不同的分法。

输入输出样例

输入: #1

7 3

输出: #1

4

说明&提示

四种分法为：
\(1,1,5\);
\(1,2,4\);
\(1,3,3\);
\(2,2,3\).

解题思路

难点在于去重，可以限制数值必须按升序排列即可

好吧，DFS 解法确实不难，但 DP 难度不小

由 dfs 得到的 dp 解法：

1. \(dp[i][j]\) 表示将数 \(i\) 划分成 \(j\) 个数的方案数
2. 状态转移方程：\(dp[i][j] = \sum_{y = 1}^{i - 1} dp[i - y][j - 1]\)
3. 怎么防止重复呢？DFS解法中设置了第三个参数 limit 限制了划分的数是单调非减的，同理，将三重循环 \(i, j, y\) 中的划分拿到最外层 \(y, i, j\)，即可限制划分是单调非减的，即在计算大小为 \(y\) 的划分时，\(dp\) 数组中的划分方案划分大小都是不超过 \(y\) 的，由此可以保证划分的单调非减性

时间复杂度: \(O(n^2k)\)

看了评论区才做出的dp解法：换个角度，题目可以看做 \(n\) 个小球，放到 \(k\) 个盒子里面的方案数，要求盒子不能为空，小球和盒子没区别，设当前问题为 \(F(n, k)\)，那么子问题就是：

1. 至少有一个盒子里面放一个球，拿出那个盒子，把一个球放到盒子里面: \(F(n - 1, k - 1)\)
2. 所以盒子都有至少两个球，每个盒子里面都放一个球，\(F(n - k, k)\)
3. 推出状态转移方程：\(F(n, k) = F(n - 1, k - 1) + F(n - k, k)\)

时间复杂度: \(O(nk)\)

解答代码

动态规划方法二

#include <cstdio>
#include <vector>
using namespace std;

int NumberPartition(int n, int k) {
    // dp[i][j] 表示数 i 划分为 k 份
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    for (int i = 1; i <= n; ++i) dp[i][1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= k; ++j) {
            dp[i][j] = (i > j ? dp[i - j][j] : 0) + dp[i - 1][j - 1];
        }
    }
    return dp[n][k];
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d", NumberPartition(n, k));
    return 0;
}

动态规划方法一

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        sc.close();
        System.out.println(new Main().NumberPartition(n, k));
    }

    public int NumberPartition(int n, int k) {
        // dp[i][j] 表示将数 i 划分为 j 份
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;
        // i 划分为 x + y 
        // dp[i][j] = \sum_{y = 1}^{i} dp[y][j - 1]
        // 限制 划分只能由小到大，方法是调整循环顺序
        for (int y = 1; y <= n; ++y) {
            for (int i = y; i <= n; ++i) {
                for (int j = 1; j <= k; ++j) {
                    dp[i][j] += dp[i - y][j - 1];
                }
            }
        }
        return dp[n][k];
    }
}

这题数据量不大，应该不会递归栈溢出了吧~
成功通过 ^_^

from functools import lru_cache

@lru_cache(None)
def dfs(n: int, k: int, limit: int) -> int:
    """将整数 n 划分为 k 份 且每份要大于等于 limit"""
    if k == 1:
        return 1 if n >= limit else 0
    if limit * k > n:
        return 0
    return sum(dfs(n - i, k - 1, i) for i in range(limit, n))

n, k = map(int, input().split())
print(dfs(n, k, 1))

---

P4994 终于结束的起点

题目描述

广为人知的斐波拉契数列 \(\mathrm{fib}(n)\) 是这么计算的

也就是 \(0, 1, 1, 2, 3, 5, 8, 13 \cdots\)，每一项都是前两项之和。

小 F 发现，如果把斐波拉契数列的每一项对任意大于 \(1\) 的正整数 \(M\) 取模的时候，数列都会产生循环。

当然，小 F 很快就明白了，因为 (\(\mathrm{fib}(n - 1) \bmod M\)) 和 (\(\mathrm{fib}(n - 2) \bmod M)\) 最多只有 \(M ^ 2\) 种取值，所以在 \(M ^ 2\) 次计算后一定出现过循环。

甚至更一般地，我们可以证明，无论取什么模数 \(M\)，最终模 \(M\) 下的斐波拉契数列都会是 \(0, 1, \cdots, 0, 1, \cdots\)。

现在，给你一个模数 \(M\)，请你求出最小的 \(n \gt 0\)，使得 \(\mathrm{fib}(n) \bmod M = 0, \mathrm{fib}(n + 1) \bmod M = 1\)。

输入格式

输入一行一个正整数 \(M\)。

输出格式

输出一行一个正整数 \(n\)。

输入输出样例

输入: #1

2

输出: #1

3

输入: #2

6

输出: #2

24

说明&提示

样例 1 解释

斐波拉契数列为 \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots\)，在对 \(2\) 取模后结果为 \(0, 1, 1, 0, 1, 1, 0, 1, 1, 0, \cdots\)。

我们可以发现，当 \(n = 3\) 时，\(f(n) \bmod 2= 0, f(n + 1) \bmod 2 = 1\)，也就是我们要求的 \(n\) 的最小值。

数据范围

对于 \(30\%\) 的数据，\(M \leq 18\)；

对于 \(70\%\) 的数据，\(M \leq 2018\)；

对于 \(100\%\) 的数据，\(2 \leq M \leq 706150=\)0xAC666。

提示

如果你还不知道什么是取模 \((\bmod)\)，那我也很乐意告诉你，模运算是求整数除法得到的余数，也就是竖式除法最终「除不尽」的部分，也即 \[a \bmod M =k \iff a = bM + k\ (M \gt 0, 0 \leq k < M)\] 其中 \(a, b, k\) 都是非负整数。

如果你使用 C / C++，你可以使用 % 来进行模运算。

如果你使用 Pascal，你可以使用 mod 来进行模运算。

解题思路

把斐波那契数列的数一个个代入进去算即可, 据评论区大佬的找规律和数学推论，答案不会超过 \(7M\)，所以可以预估数组大小，但。。。这么简单的动态规划直接写成滚动数组的形式就好了吧~

解答代码

#include <cstdio>
using namespace std;

int main() {
    int M;
    scanf("%d", &M);

    // 计算斐波那契数
    int x = 1, y = 1;
    for (int i = 1;; ++i) {
        if (x % M == 0 && y % M == 1) {
            printf("%d", i);
            break;
        }
        else {
            int tmp = (x + y) % M;
            x = y;
            y = tmp;
        }
    }
    return 0;
}

import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        sc.close();
        int a = 1, b = 1;
        for (int i = 1;; ++i) {
            if (a % M == 0 && b % M == 1) {
                System.out.println(i);
                break;
            } else {
                int tmp = (a + b) % M;
                a = b;
                b = tmp;
            }
        }
    }
}

注意，虽然Python的整型可以无限大，但数字越大计算会越慢(尝试过数字大到一定程度一个简单的 a + b都需要计算数十分钟甚至数个小时)，所以必须时刻取余，否则最后三个会TLE

def fib() -> int:
    """产生由 1 开始的斐波那契数"""
    a, b = 0, 1
    while 1:
        a, b = b, (a + b) % M
        yield a


M = int(input())
i, pre = 0, 1
for n in fib():
    if pre % M == 0 and n % M == 1:
        print(i)
        break
    pre = n
    i += 1

---