渴望学到知识的菜鸟

用户名：ldhskd

访问量：30303

签　名：

这小伙子人行，能处！

等　　级
排　　名	115
经　　验	7668
参赛次数	1
文章发表	48
年　　龄	18
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

暴力搜索！【C语言】
浏览：438

【C语言】简单的输出
浏览：77

【C语言】简单的排序问题
浏览：71

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C++代码（代码简洁）

　　作者: 渴望学到知识的菜鸟　　　　发表时间：2022-03-16 20:49:29 浏览：626　|　评论：0　

原题链接：蓝桥杯2014年第五届真题-波动数列

###解法
------------
#####S = x + (x + d1) + (x + d1 + d2) + (x + d1 + d2 + d3) +....
所以：
S = nx +(n-1)d1 + (n-2)d2 + (n-3)d3 + .... + dn-1

因为d1 ,d2 , d3 ... dn-1 只是变量， 将其含义交换，就是让dn-1叫d1 , dn-2 叫d2 以此类推
所以：
##### S = nx + d1 + 2d2 + 3d3 +.... + (n-1)dn-1
##### x = ( S - (d1 + 2d2 + ...)) / n
##### 因为x是整数 ， 所以  S % n == (d1 + 2d2 + ... ) % n

------------

我们可以定义一个数组f[i][j]
i :  （d1 + 2d2 + 3d3 +.... + (n-1)dn-1）  的前i项
j :   余数为j
f[i][j]:前i项中，余数为j的一共有f[i][j]个

而f[i][j] 可以通过前一项推导出来
##### 第i项就是由第i-1项 + a 或者是 -b 得来的
令前i-1项和为C ， 则 前i项和为 C + i * a 或 C -i * b
而 ( C + i * a) % n = j;
所以 C % n == (j - i*a) % n ;
所以，前 i - 1 项的和的余数是 (j - i * a ) % n;
另一种情况就是 (j + i*b) % n;

#####f[0][0] = 0 一项都不选的时候，总和是0，模n的余数显然是0

###对于取模，可能会模出负数，但是数组下标没有负数
所以，应避免出现负数情况
a % b 改成  (a % b + b) % b 这样结果就一定是正数了

------------

```
#include<iostream>
using namespace std;

const int N = 1005;
int n , s , a , b ;
int f[N][N];
int MOD = 100000007;

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

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

0.0分

10 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

渴望学到知识的菜鸟

TA的其他文章

你可能喜欢

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C++代码（代码简洁）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

【金明的预算方案】（C++代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1048题解（读入回车问题）

演讲大赛评分（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.3 （C++代码）

渴望学到知识的菜鸟

TA的其他文章

你可能喜欢

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C++代码（代码简洁）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

【金明的预算方案】 （C++代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1048题解（读入回车问题）

演讲大赛评分 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.3 （C++代码）

上车人数（C语言代码）

大神老白（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

【金明的预算方案】（C++代码）

用筛法求之N内的素数。（C++代码）

演讲大赛评分（C语言代码）