TLEOJ Contest #15 - F-Function

View as PDF

Submit solution

Points: 1300 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type

Ta định nghĩa một hàm F(n,k) với 1\le k\le n,n,k \in N như sau:

  • Nếu k=1 thì F(n,k)=1.
  • Ngược lại F(n,k)=\Sigma_{i=0}^{n}C_n^iF(n-i,k-1).

Yêu cầu: Cho biết nk, hãy tính F(n,k).

Input, Output và Subtasks

Input: (bàn phím)
  • Dòng đầu tiên gồm 2 số nguyên dương n,k (1\le k\le n\le 10^{18}).
Output: (màn hình)
  • In ra theo yêu cầu, có thể đáp án rất lớn nên hãy in F(n,k) sau khi chia lấy dư cho 10^9+7.
Subtasks
  • Subtask 1: 20% số điểm có n\le 10.
  • Subtask 2: 40% số điểm có n\le 2.10^2
  • Subtask 3: còn lại không có giới hạn gì thêm.

Sample

Input (bàn phím)
3 2
Output (màn hình)
8

Comments

There are no comments at the moment.