笔试时间：2023年9月16日 秋招

第一题

题目：TuTu的子数列

TuTu得到了一个长度为n的数列a1,a2,...,an。现在TuTu希望从原数列中挑出一个子数列(被挑出的子数列需要按照原来的顺序排列，但不一定要连续)。但是TuTu同时提出了一个要求，对于数列a1,a2,...,中任意连续的k个数，它们中应该有x个数被包含在挑出的子数列中，其中x需要满足x属于[L,R]。当然满足这个要求的子数列有很多个，TuTu认为一个被挑出的子数列的值是这个数列中的每个数之和。现在TuTu想让你计算所有可能被挑出的子数列的价值和是多少？

输入描述

第一行四个数n,k,L,R。

第二行n个数，表示数列a1,a2,...,an。

n <= 1000, 1 <= L <= R <= k <= 10, 0 <= ai <= 10^9

输出描述

输出一行一个数，表示答案。由于这个数可能会很大，你需要输出它对10^9 + 7取模后的结果。

样例输入

示例一：

3 2 1 2

8 3 4

示例二：

5 3 1 2

6 1 7 9 7

样例输出

示例一：

48

示例二：

240

参考题解

参考状态压缩动态规划的模版解决。

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int l = scanner.nextInt();
        int r = scanner.nextInt();
        long[] a = new long[n + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextLong();
        }

        int N = 1024;
        long[][] f = new long[N][N];
        long[][] s = new long[N][N];
        long mod = 1000000007;
        int[] ok = new int[N];
        int[][] g = new int[N][2];

        for (int st = 0; st < (1 << n); st++) {
            int count = Integer.bitCount(st);
            if (count >= 1 && count <= r) {
                ok[st] = 1;
            }
        }

        int msk = (1 << k) - 1;

        for (int st = 0; st < (1 << k); st++) {
            if (ok[st] != 0) {
                int s0 = (st << 1) & msk;
                int s1 = (st << 1 | 1) & msk;
                if (ok[s0] != 0) g[st][0] = s0;
                if (ok[s1] != 0) g[st][1] = s1;
                f[k][st] = 1;
                for (int j = 0; j < k; j++) {
                    if ((st & (1 << j)) != 0) {
                        s[k][st] += a[k - j];
                    }
                }
                s[k][st] %= mod;
            }
        }

        for (int i = k; i < n; i++) {
            for (int st = 0; st < (1 << k); st++) {
                if (ok[st] != 0) {
                    if (g[st][0] != 0) {
                        int su = g[st][0];
                        f[i + 1][su] = (f[i + 1][su] + f[i][st]) % mod;
                        s[i + 1][su] = (s[i + 1][su] + s[i][st]) % mod;
                    }
                    if (g[st][1] != 0) {
                        int su = g[st][1];
                        f[i + 1][su] = (f[i + 1][su] + f[i][st]) % mod;
                        s[i + 1][su] = (s[i + 1][su] + s[i][st] + f[i][st] * a[i + 1]) % mod;
                    }
                }
            }
        }

        long ans = 0;
        for (int st = 0; st < (1 << k); st++) {
            if (ok[st] != 0) {
                ans = (ans + s[n][st]) % mod;
            }
        }

        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n, k, l, r = m