Đếm hoán vị

View as PDF

Submit solution


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

Author:
Problem types

Cho hai số nguyên dương ~n, k~. Đếm xem có bao nhiêu hoán vị ~p_1, p_2, ..., p_n~ của ~1, 2, ..., n~ thỏa mãn ~p_i > p_{i / k}~ với mọi ~1\leq i\leq n~.

Trong đó, ~a/b~ là số nguyên lớn nhất không vượt quá ~\dfrac{a}{b}~ và quy ước ~p_0 = 0~.

Input

Gồm hai số nguyên dương ~n, k \ (1 \leq n, k \leq 10^6)~

Output

In ra số lượng hoán vị thỏa mãn điều kiện sau khi ~\mod (10^9+7)~

Sample Input 1

3 2

Sample Output 1

2

Sample Input 2

8 3

Sample Output 2

2520

Giải thích

Trong test 1, chúng ta cần tìm các hoán vị thỏa mãn ~p_3>p_1~ và ~p_2>p_1~. Có 2 hoán vị như vậy ~(1, 2, 3)~ và ~(1, 3, 2)~.

Giới hạn

  • ~20~% test có ~n \leq 10~
  • ~10~% test có ~k > n~
  • ~10~% test có ~k = n~
  • ~20~% test có ~k > \frac{n}{2}~
  • ~20~% test có ~n, k \leq 10^3~
  • ~20~% test có ~n, k \leq 10^6~

View comments (1)

Comments


  • -1
    mbfibat  commented on 6:36 p.m. 1 jun, 2020 edited

    Bài này hay phết :v