按照大佬的思路 (网址:CSDN),使用了动态规划解题。
// (59条消息) 题目 1449: 蓝桥杯2014年第五届真题-波动数列_一只干饭猿的博客-CSDN博客
参考代码:
import java.util.Scanner;
public class Main{
static int MOD=100000007;
static long num = 0;
static long []dp=new long[500001];//numa可能的最大个数
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int s = scanner.nextInt();
int a = scanner.nextInt();
int b = scanner.nextInt();
long t = (long) n *(n-1)/2;//numa+numb = n*(n-1)/2
create(n);
for(long i=t;i>=0;i--) //i代表numa
{
long j = t-i;
long temp = s-i*a+j*b;
if (temp%n==0) //x=(s-numa*a+numb*b)/n,x是整数
{//+a的位置定下了,-b一定确定了
num = num+(dp[Math.toIntExact(i)]%MOD);//不损失精度的把long转换成int
num%=MOD;
}
}
System.out.println(num);
}
public static void create(int n){
int i,j;
dp[0] = 1;
for (i=1;i<n;i++)//位数
for (j=(i*(i+1)/2);j>=i;j--)//滚动数组,从后到前更新j>=i的部分
dp[j] = (dp[j-i]+dp[j])%MOD;//表示当numa=i的时候,n位数列+a的组合数目
}
}
0.0分
1 人评分
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:820 |
弟弟的作业 (C++代码)浏览:1304 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:542 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:544 |
DNA (C语言描述,数据结构)浏览:859 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:834 |
用筛法求之N内的素数。 (C语言代码)浏览:531 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:686 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:686 |
【魔板】 (C++代码)浏览:1161 |