小Q的歌单

[编程题]小Q的歌单

热度指数：18600 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。
接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。

输出描述:

输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对1000000007取模的结果。

示例1

输入

5
2 3 3 3

输出

算法知识视频讲解

Java

Jaiken

import java.util.*;
public class Main {     static long mod = 1000000007l;     public static void main(String[] args) {         // TODO Auto-generated method stub                  long[][] c = new long[101][101];                  for (int i = 0; i <=100; i++) {             // 行头初始化             c[i][0] = 1;         }         for (int i = 1; i <= 100; i++) {             for (int j = 1; j <= 100; j++) {                 c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;             }         }         long result = 0;         Scanner scanner = new Scanner(System.in);         int k = scanner.nextInt();         int a = scanner.nextInt();         int x = scanner.nextInt();         int b = scanner.nextInt();         int y = scanner.nextInt();         for (int i = 0; i < x; i++) {             int temp = k - a * i;             if (temp >= 0)                 if (temp % b == 0)                     if (temp / b <= y){                         long temp_c= (c[x][i] * c[y][temp / b]) % mod;                         result+=temp_c;                         result%=mod;                     }         }         System.out.println(result);     }

}

	



	最后的结果一直
答案错误:您提交的程序没有通过所有的测试用例
case通过率为90.00%
测试用例:
100
1 100 2 100
对应输出应该为:
480218926
你的输出为:
480218925

求教为什么

发表于 2018-08-31 21:34:44 回复(1)

Java

newch

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int length = scan.nextInt();
        int A = scan.nextInt();
        int X = scan.nextInt();
        int B = scan.nextInt();
        int Y = scan.nextInt();
        System.out.println(qlist(length, A, X, B, Y));
    }

    public static long qlist(int length, int A, int X, int B, int Y) {
        long mod = 1000000007;
        // 构建杨辉三角
        int max = 101;
        long[][] tri = new long[max][max];
        tri[0][0] = 1;
        for (int i = 1; i < max; i++) {
            tri[i][0] = 1;
            for (int j = 1; j < max; j++) {
                tri[i][j] = (tri[i - 1][j - 1] + tri[i - 1][j]) % mod;
            }
        }
        long sum = 0;
        for (int value = 0; value <= length; value++) {
            if (value % A == 0 && (length - value) % B == 0 && value/A <= 100 && (length - value) / B <= 100) {
                sum += tri[X][value / A] * tri[Y][(length - value) / B] % mod;
            }
        }
        return sum % mod;
    }
}

杨辉三角 ac

编辑于 2018-07-23 21:57:12 回复(0)

Java

InseQM

 public class SongSheetForQ {
    public static long[][] arr = new long[101][101];
    public static long constituteMethod(int K, int A, int X, int B, int Y){
        long result = 0;
        int length;
        arr[0][0] = 1;
        for (int i = 1; i <= 100; i++){
            arr[i][0] = 1;
            for (int j = 1; j <= 100; j++) {
                arr[i][j] = (arr[i - 1][j] + arr[i - 1][j - 1]) % 1000000007;
            }
        }
        for (int i = 0; i <= X; i++){
            length = K - A * i;
            if (length >= 0 && length % B == 0 && length / B <= Y){
                result += (arr[X][i] * arr[Y][length / B]);
            }
        }
        return result % 1000000007;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int A = sc.nextInt();
        int X = sc.nextInt();
        int B = sc.nextInt();
        int Y = sc.nextInt();
        sc.close();
        System.out.println(constituteMethod(K, A, X, B, Y));
    }
}

发表于 2018-07-20 17:10:03 回复(0)