oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

binomial Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

binomial.html

Problem Description

The binomial coefficients are a very important group of numbers in mathematics and have many uses in pure mathematics and statistics.

In counting, they represent the number of ways of picking k unordered objects from n distinct objects, also known as a combination or combinatorial number. It is usually represented by the symbol nCk

In pure mathematics, it is appears as the coefficients of the binomial expansion as shown below using another form of representation commonly used. The explicit formula of the binomial coefficient is also given.

There is also a very interesting link between the binomial coefficients and the Pascal's Triangle. The Pascal's Triangle is the triangle formed by constructing each subsequent row with the sum of every two neighbouring numbers in the previous row. Here are the first 6 rows of the Pascal's Triangle.

The interesting thing is that all the numbers in the Pascal's Triangle are binomial coefficients. The relationship can be seen as shown.

Given all this information, all you need to do is code a program to calculate the value of a binomial coefficient.

Limits

Subtask 1(12%): 0 ≤ n, k ≤ 10

Subtask 2(23%): 0 ≤ n,k ≤ 100

Subtask 3(48%): 0 ≤ k ≤ 100, 0 ≤ n ≤ 100000

Subtask 4(27%): 0 ≤ k ≤ 100, 0 ≤ n ≤ 10000000

Subtask 5(0%): Sample

Input

The input will consist of two integers n and k

Output

The output should only contain one integer, the value of nCk. Since the number can be very large, output the number modulo 1000000007

Sample Input

5 2

Sample Output

10

BinomialTheorem.gif

BinomialPascal.gif

PascalTriangle.jpeg

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11251s64MBMinimum
22351s64MBMinimum
338101s64MBMinimum
427101s64MBMinimum
5011s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o binomial -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.