[JAVA] AtCoder Beginner Contest 132 D Problem


This time, in the ABC132_D problem of the AtCoder content, the WA (incorrect answer) of what I thought was not covered, and why was the output incorrect in my implementation? I posted it because I wanted to solve the fundamental problem. In addition, the input examples 1 and 2 posted in the problem have been cleared.

Problem statement (quote)

Quote page: https://atcoder.jp/contests/abc132/tasks/abc132_d --- Start quoting --- There are K blue balls and N-K red balls. Balls of the same color are indistinguishable. Sunuke and Takahashi are playing with these balls.

First, Sunuke arranges N balls in a row from left to right.

Next, Mr. Takahashi, of these, K Collect only one blue ball. Takahashi can collect as many blue balls as he wants in a row with a single operation. Takahashi always acts to minimize the number of operations required to collect K blue balls.

How many ways can Takahashi arrange the balls that he needs to operate exactly i times to collect K blue balls? Calculate the answer for each of 1 ≤ i ≤ K and answer the remainder divided by 10 ^ 9 + 7.

Constraint 1≤K≤N≤2000

input Input is given from standard input in the following format.


output On line i (1 ≤ i ≤ K), output the remainder of the total number of ball arrangements that Takahashi needs to operate exactly i times divided by 10 ^ 9 + 7. --- End of quote ---

Implementation (WA judgment)


import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();

		for(int i = 1;i <= K;i++) {
			long combi1 = combination(N-K+1,i);
			long combi2 = combination(K-1,i-1);

	public static long combination(int i,int j) {
		if(j==0) {
			return 1;
		return combination(i-1,j-1)* i  / j;

I would be grateful if you could point out the above.

Recommended Posts

AtCoder Beginner Contest 132 D Problem
AtCoder Beginner Contest 168
AtCoder Beginner Contest 167 C Problem (Java)
atcoder ABC70 D problem
AtCoder Beginner Contest 182 Participation Article
Solve AtCoder Beginner Contest 151 in java
Solve AtCoder Beginner Contest 150 in java
Solve AtCoder Beginner Contest 153 in java
Solve AtCoder Beginner Contest 175 in java
Solve AtCoder Beginner Contest 152 in java
Solve AtCoder Beginner Contest 156 in java
AtCoder Beginner Contest 169 A, B, C with ruby
atcoder ABC113 C problem
atcoder ABC115 C problem
Solving with Ruby AtCoder ACL Beginner Contest C Union Find (DSU)
Learning Ruby with AtCoder 6 [Contest 168 Therefore]
[Beginner] Let's solve AtCoder problem with Ruby while looking at the article!