#PQJ1546x117. QOJ 1546_117

    ID: 2641 传统题 600ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训动态规划数学

QOJ 1546_117

The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 2 – Asceticism Asceticism One day, JOI-kun got a time machine. He decided to go to Japan in the 9th century. He met Kukai, one of the most famous priests in Japan at the moment. The priest wanted to develop the new way of training. His training is done in the following way: • Kukai reads the sutra with N sentences. These sentences are ordered, and he has to read in order. • Each sentence has one integer between 1 and N, inclusive. No two different sentences have the same number. • He has to read the sentence with the integer i (1 ≤i ≤N) in the i-th period among the N equally divided time periods in a day. Each sentence is so short that it is always possible for him to read a sentence in a period. Kukai wants to read the whole sutra as fast as possible. However, how many days it takes for him to finish depends on the integers on the sentences in the sutra. JOI-kun was asked by Kukai to count the number of possible ways of integers on the sentences that takes Kukai exactly K days to finish reading, if he reads optimally. Task Given the number of sentences N and an integer K, calculate the number of possible ways of integers on the sentences that takes Kukai exactly K days to finish reading, if he reads optimally, modulo 1 000 000 007. Input Read the following data from the standard input. • The first line of input contains N and K, separated by a single space. Output Print the number of possible ways of integers on the sentences that takes Kukai exactly K days to finish reading, if he reads optimally, modulo 1 000 000 007. Constraints All input data satisfy the following conditions. • 1 ≤N ≤100 000. • 1 ≤K ≤N. Asceticism– 1 / 2 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 2 – Asceticism Subtask There are 4 subtasks. The score and additional constraints of each subtask are as follows: Subtask 1 [4 points] • N ≤10. Subtask 2 [20 points] • N ≤300. Subtask 3 [25 points] • N ≤3 000. Subtask 4 [51 points] There are no additional constraints. Sample Input and Output Sample Input 1 Sample Output 1 3 2 4 There are 4 possible ways of integers on the sentences that takes him 2 days to finish reading. • The first sentence has 1, the next sentence has 3 and the last sentence has 2. He reads the first two sentences (numbered 1 and 3 each) on the first day, and the last sentence (numbered 2) on the second day. • The first sentence has 2, the next sentence has 1 and the last sentence has 3. • The first sentence has 2, the next sentence has 3 and the last sentence has 1. • The first sentence has 3, the next sentence has 1 and the last sentence has 2. Sample Input 2 Sample Output 2 10 5 1310354 Asceticism– 2 / 2