笔试时间：2025年9月21日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：序列的构成方案数

现在有一个长度为 n 的整数序列，其中每个数字范围在 1 到 m 之间。序列中除第一个数字外，其他位置上的数字需要满足下列条件之一：

• 和前一个数字相差不超过 k
• 或者是前一个数字的整数倍

现在问这个序列有几种构成方案。答案对 10^9+7 取模。

输入描述

一行三个正整数 n, m, k，以空格分开，分别表示序列的长度为 n；序列中每个数字的范围在 1 到 m 之间；数字间相差的阈值 k。

输出描述

一个正整数，表示答案。

样例输入

3 2 1

样例输出

8

样例说明 共8种：[1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1], [2,3,3]

参考题解

解题思路：

1. 状态定义：定义 dp[i][j] 表示长度为 i 且最后一个数字是 j 的合法序列有多少种。使用滚动数组优化空间。
2. 状态转移：计算新一层的结果 nextDp[j] 时，需要考虑所有可以构成合法序列的前一个数字 p： 条件一：数字之差不超过 k，即 |j - p| <= k条件二：j 是 p 的整数倍
3. 计算优化： 对于条件一，使用前缀和数组进行优化，可以在 O(1) 时间内求出区间和对于条件二，通过遍历到 sqrt(j) 来高效地找出所有约数
4. 去重处理：先通过前缀和计算满足条件一的方案总数，然后在遍历约数时，只加上不满足条件一的方案数
5. 最终结果：循环 n-1 次后，将 dp 数组中所有位置的值累加起来

C++：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int sequenceLength, numberRange, maxDifference;
    cin >> sequenceLength >> numberRange >> maxDifference;
    
    long long MODULO = 1000000007;
    vector<long long> prevSolutions(numberRange + 1, 1);
    prevSolutions[0] = 0;
    
    for (int len = 2; len <= sequenceLength; len++) {
        vector<long long> currentSolutions(numberRange + 1, 0);
        vector<long long> cumulativeSums(numberRange + 1, 0);
        
        for (int val = 1; val <= numberRange; val++) {
            cumulativeSums[val] = (cumulativeSums[val - 1] + prevSolutions[val]) % MODULO;
        }
        
        for (int val = 1; val <= numberRange; val++) {
            int left = max(1, val - maxDifference);
            int right = min(numberRange, val + maxDifference);
            long long sumFromDiff = (cumulativeSums[right] - cumulativeSums[left - 1] + MODULO) % MODULO;
            currentSolutions[val] = sumFromDiff;
            
            for (int div = 1; div * div <= val; div++) {
                if (val % div == 0) {
                    int factorA = div;
                    int factorB = val / div;
                    
                    if (factorA <= numberRange) {
                        if (abs(val - factorA) > maxDifference) {
                            currentSolutions[val] = (currentSolutions[val] + prevSolutions[factorA]) % MODULO;
                        }
                    }
                    
                    if (factorA != factorB && factorB <= numberRange) {
                        if (abs(val - factorB) > maxDifference) {
                            currentSolutions[val] = (currentSolutions[val] + prevSolutions[factorB]) % MODULO;
                        }
                    }
                }
            }
        }
        
        prevSolutions = currentSolutions;
    }
    
    long long totalCount = 0;
    for (int val = 1; val <= numberRange; val++) {
        totalCount = (totalCount + prevSolutions[val]) % MODULO;
    }
    
    cout << totalCount << endl;
    
    return 0;
}

Java：

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sequenceLength = scanner.nextInt();
        int numberRange = scanner.nextInt();
        int maxDifference = scanner.nextInt();
        scanner.close();
        
        long MODULO = 1_000_000_007;
        
        long[] prevSolutions = new long[numberRange + 1];
        Arrays.fill(prevSolutions, 1);
        prevSolutions[0] = 0;
        
        for (int len = 2; len <= sequenceLength; len++) {
            long[] currentSolutions = new long[numberRange + 1];
            long[] cumulativeSums = new long[numberRange + 1];
            
            for (int val = 1; val <= numberRange; val++) {
                cumulativeSums[val] = (cumulativeSums[val - 1] + prevSolutions[val]) % MODULO;
            }
            
            for (int val = 1; val <= numberRange; val++) {
                int left = Math.max(1, val - maxDifference);
                int right = Math.min(numberRange, val + maxDifference);
                long sumFromDiff = (cumulativeSums[right] - cumulativeSums[left - 1] + MODULO) % MODULO;
                currentSolutions[val] = sumFromDiff;
                
                for (int div = 1; div * div <= val; div++) {
                    if (val % div == 0) {
                        int factorA = div;
                        int factorB = val / div;
                        
                        if (factorA <= numberRange) {
                            if (Math.abs(val - factorA) > maxDifference) {
                                currentSolutions[val] = (currentSolutions[val] + prevSolutions[factorA]) % MODULO;
                            }
                        }
                        
                        if (factorA != factorB && factorB <= numberRange) {
                            if (Math.abs(val - factorB) > maxDifference) {
                                currentSolutions[val] = (currentSolutions[val] + prevSolutions[factorB]) % MODULO;
                            }
                        }
                    }
                }
            }
            
            prevSolutions = currentSolutions;
        }