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

发布时间:2023年12月20日

题目链接

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

题目描述

观察这个数列:

1 ? 3 ? 0 ? 2 ? ? 1 ? 1 ? ? 2 ? … 1\ 3\ 0\ 2\ -1\ 1\ -2\ … 1?3?0?2??1?1??2?

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

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

输入格式

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

输出格式

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

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

数据范围
  • 1 ≤ n ≤ 1000 1≤n≤1000 1n1000

  • ? 1 0 9 ≤ s ≤ 1 0 9 ?10^9≤s≤10^9 ?109s109

  • 1 ≤ a , b ≤ 1 0 6 1≤a,b≤10^6 1a,b106

输入样例:

4 10 2 3

输出样例:

2

样例解释

两个满足条件的数列分别是 2 ? 4 ? 1 ? 3 2\ 4\ 1\ 3 2?4?1?3 7 ? 4 ? 1 ? ? 2 7\ 4\ 1\ -2 7?4?1??2

解法:同余 + dp

我们可以列出数列的 n n n 项,这里假设 x x x 是第一项, d 1 , d 2 , . . . , d n ? 1 d_1,d_2,...,d_{n-1} d1?,d2?,...,dn?1?的值为 a a a 或者 b b b

s = ( x ) + ( x + d 1 ) + ( x + d 1 + d 2 ) + . . . + ( x + d 1 + d 2 + . . . + d n ? 1 ) s = (x) + (x + d_1) + (x + d_1 + d_2) + ... + (x + d_1 + d_2 + ... + d_{n - 1}) s=(x)+(x+d1?)+(x+d1?+d2?)+...+(x+d1?+d2?+...+dn?1?)

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

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

x = s ? [ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( d n ? 1 ) ] n x =\frac{ s -[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})]}{n} x=ns?[(n?1)d1?+(n?2)d2?+...+(dn?1?)]?

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

所以, n n 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})] s?[(n?1)d1?+(n?2)d2?+...+(dn?1?)],也就是 s ? [ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( d n ? 1 ) ] s -[ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})] s?[(n?1)d1?+(n?2)d2?+...+(dn?1?)] 除以 n n n 的余数为 0 0 0

我们能够进一步推导出 s s s , [ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( d n ? 1 ) ] [ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})] [(n?1)d1?+(n?2)d2?+...+(dn?1?)] 除以 n n n 的余数相等,也就是 s ? m o d ? n ≡ [ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( d n ? 1 ) ] m o d ?? n s\ mod\ n \equiv [ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})] \mod n s?mod?n[(n?1)d1?+(n?2)d2?+...+(dn?1?)]modn,即 s s s , [ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( d n ? 1 ) ] [ (n - 1)d_1 + (n - 2)d_2 + ... + (d_{n - 1})] [(n?1)d1?+(n?2)d2?+...+(dn?1?)] 同余 n n n

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

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

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

[ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( n ? ( i ? 1 ) ) d i ? 1 + ( n ? 1 ) a ] ? m o d ? n ≡ j [(n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1} + (n - 1)a] \ mod\ n \equiv j [(n?1)d1?+(n?2)d2?+...+(n?(i?1))di?1?+(n?1)a]?mod?nj

将其转换一下:

[ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( n ? ( i ? 1 ) ) d i ? 1 ] ? m o d ? n ≡ [ j ? ( n ? 1 ) a ] ? m o d ? n [ (n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1}] \ mod\ n \equiv [j - (n - 1)a] \ mod\ n [(n?1)d1?+(n?2)d2?+...+(n?(i?1))di?1?]?mod?n[j?(n?1)a]?mod?n

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

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

[ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( n ? ( i ? 1 ) ) d i ? 1 ? ( n ? 1 ) b ] ? m o d ? n ≡ j [(n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1} - (n - 1)b] \ mod\ n \equiv j [(n?1)d1?+(n?2)d2?+...+(n?(i?1))di?1??(n?1)b]?mod?nj

将其转换一下:

[ ( n ? 1 ) d 1 + ( n ? 2 ) d 2 + . . . + ( n ? ( i ? 1 ) ) d i ? 1 ] ? m o d ? n ≡ [ j + ( n ? 1 ) b ] ? m o d ? n [ (n - 1)d_1 + (n - 2)d_2 + ... + (n - (i - 1))d_{i - 1}] \ mod\ n \equiv [j + (n - 1)b] \ mod\ n [(n?1)d1?+(n?2)d2?+...+(n?(i?1))di?1?]?mod?n[j+(n?1)b]?mod?n

所以我们可以得到 f [ i ] [ j ] = f [ i ? 1 ] [ j + ( n ? 1 ) b ] f[i][j] = f[i - 1][j + (n - 1)b] 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 ] f[i][j] = f[i - 1][j + (n - 1)b] + f[i - 1][j - (n - 1)a] f[i][j]=f[i?1][j+(n?1)b]+f[i?1][j?(n?1)a]

注意:

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

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

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)]);
    }
}
文章来源:https://blog.csdn.net/m0_74396439/article/details/135032739
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。