题目链接

[蓝桥杯 2014 省 A] 波动数列

题目描述

观察这个数列：

$1302-11-2\dots$

这个数列中后一项总是比前一项 增加$2$ 或者 减少$3$，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢？

输入格式

共一行，包含四个整数 $n,s,a,b$，含义如前面所述。

输出格式

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 $100000007$ 的余数。

数据范围

• $1\le n\le 1000$

• $-10^9\le s\le 10^9$

• $1\le a,b\le 10^6$

输入样例：

4 10 2 3

输出样例：

2

样例解释

两个满足条件的数列分别是 $2413$ 和 $741-2$。

解法：同余 + dp

我们可以列出数列的 $n$ 项，这里假设 $x$ 是第一项，$d_1,d_2,...,d_{n-1}$的值为 $a$ 或者 $b$ ：

$$s=(x)+(x+d_1)+(x+d_1+d_2)+...+(x+d_1+d_2+...+d_{n-1})$$

将其整理一下可以得到 :
$$s=n\times x+(n-1)d_1+(n-2)d_2+...+(d_{n-1})$$

由于 $x$ 可以是任意的整数，而 $s$ 是给定的，也就是确定的，于是我们可以通过 $s$ 得到 $x$ ：

$$x=\frac{s-[(n-1)d_1+(n-2)d_2+...+(d_{n-1})]}{n}$$

由于 $x$ ，也就是数列的第一项，必须是整数。

所以，$n$ 必须能够整除 $s-[(n-1)d_1+(n-2)d_2+...+(d_{n-1})]$，也就是 $s-[(n-1)d_1+(n-2)d_2+...+(d_{n-1})]$ 除以 $n$ 的余数为 $0$。

我们能够进一步推导出 $s$ , $[(n-1)d_1+(n-2)d_2+...+(d_{n-1})]$ 除以 $n$ 的余数相等，也就是 $smodn\equiv [(n-1)d_1+(n-2)d_2+...+(d_{n-1})]\mathrm{mod}n$，即 $s$ , $[(n-1)d_1+(n-2)d_2+...+(d_{n-1})]$ 同余 $n$。

所以我们将原问题转换为：求使得 $[(n-1)d_1+(n-2)d_2+...+(d_{n-1})]$ 和 $s$ 同余 $n$ 的方案数有多少种。

我们定义 $f[i][j]$ 为从前 $i$ 项中选，第 $i$ 项元素比前一个 增加$a$ 或者 减少$b$ ，且模 $n$ 余数是 $j$ 的方案数。

如果第 $i$ 项元素选的是 $+a$：

$$[(n-1)d_1+(n-2)d_2+...+(n-(i-1))d_{i-1}+(n-1)a]modn\equiv j$$

将其转换一下：

$$[(n-1)d_1+(n-2)d_2+...+(n-(i-1))d_{i-1}]modn\equiv [j-(n-1)a]modn$$

所以我们可以得到 $f[i][j]=f[i-1][j-(n-1)a]$

如果第 $i$ 项元素选的是 $-b$：

$$[(n-1)d_1+(n-2)d_2+...+(n-(i-1))d_{i-1}-(n-1)b]modn\equiv j$$

将其转换一下：

$$[(n-1)d_1+(n-2)d_2+...+(n-(i-1))d_{i-1}]modn\equiv [j+(n-1)b]modn$$

所以我们可以得到 $f[i][j]=f[i-1][j+(n-1)b]$

综上，我们可以得出：

$$f[i][j]=f[i-1][j+(n-1)b]+f[i-1][j-(n-1)a]$$

注意：

• 由于 $j-(n-1)a$ 可能小于 $0$，我们必须保证它模 $n$ 为正数。令 $t=j-(n-1)a$，那么我们最终得到的余数应该是 $(tmodn+n)modn$，这样就保证了最终的余数是正数。
• $f[0][0]$ 应该初始化为 $1$，因为他表示什么也不选也是一种方案，什么也不选那么就只有第一项 $x$。
• 我们最终返回的答案就是 $f[n-1][(smodn+n)modn]$，因为 $s$ 有可能是负数，所以我们也需要保证它模 $n$ 是一个正数。

时间复杂度：$O(n^2)$

C++代码：

#include <iostream>

using namespace std;

const int N = 1010 , MOD = 100000007;
int f[N][N];

int get_mod(int a , int b){
    return (a % b + b) % b;
}

int main(){
    int n , s, a, b;
    cin>>n>>s>>a>>b;
    
    f[0][0] = 1;
    for(int i = 1;i < n;i++){
        for(int j = 0;j < n;j++){
            int &val = f[i][j];
            val = (val + f[i - 1][get_mod(j - (n - i) * a , n)]) % MOD;
            val = (val + f[i - 1][get_mod(j + (n - i) * b , n)]) % MOD;
        }
    }
    
    cout<<f[n - 1][get_mod(s , n)]<<'\n';
}

Java代码：

import java.io.*;
import java.util.*;

public class Main{
    static final int N = 1010 , MOD = 100000007;
    static long[][] f = new long[N][N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    public static int get_mod(int a , int b){
        return (a % b + b) % b;
    }
    
    public static void main(String[] args) throws Exception{
        String[] s1 = in.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int s = Integer.parseInt(s1[1]);
        int a = Integer.parseInt(s1[2]);
        int b = Integer.parseInt(s1[3]);
        
        f[0][0] = 1;
        for(int i = 1;i < n;i++){
            for(int j = 0;j < n;j++){
                f[i][j] = (f[i][j] + f[i - 1][get_mod(j - (n - i) * a , n)]) % MOD;
                f[i][j] = (f[i][j] + f[i - 1][get_mod(j + (n - i) * b , n)]) % MOD;
            }
        }
        
        System.out.println(f[n - 1][get_mod(s,n)]);
    }
}