dp-波动数列

按照大佬的思路 (网址：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的组合数目
       }
   }