2286 . 數數大師

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

25.9% (7/27)

Submission's AC Ratio

22.7% (22/97)

Tags

CKcon 2022-CKcon

Description

今年的臺大電資學院二階筆試考題有一題是這樣的：

有 $1$ 到 $30$ 的數字各一個，有多少種選 $3$ 個數字的方法使得總和是 $30$ 的倍數？

想當然耳，不太會數學的 FHVirus 當然沒有成功做出正確答案。為了復仇，他決定在校內賽出一題這樣的題目來搞你：

有 $1$ 到 $N$ 的數字各一個，有多少種選 $K$ 個數字的方法使得總和是 $N$ 的倍數？

Input Format

第一行有一個數 $T$ ，接下來有 $T$ 行，每行有兩個整數 $N, K$ ，意義如題敘所述。

保證對於所有的測資， $1 \le K \le N \le 10 ^ 9, \sum K \le 100$ 。

Output Format

對於每一組 $(N, K)$ ，輸出一個整數，代表答案模 $10 ^ 9 + 7$ 的餘數。

Sample Input 1

6
10 1
20 2
30 3
40 4
998244353 71
7122 19

Sample Output 1

1
9
136
2289
26337995
634802955

Hints

特別注意，儘管範測會不會過也可以拿到一些分數。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~3 $K=1$ 1
3 4~6 $K=2$ 2
4 7~9 $K=3, \sum N \le 500$ 3
5 10~12 $K=4, \sum N \le 100$ 4
6 7~9, 13~15 $K=3, \sum N \le 3000$ 5
7 7~9, 13~18 $K=3$ 6
8 10~12, 19~21 $K=4, \sum N \le 3000$ 10
9 7~15, 19~24 $\sum N \le 3000$ 28
10 0~29 無額外限制 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 10
1 1000 262144 65536 2 10
2 1000 262144 65536 2 10
3 1000 262144 65536 2 10
4 1000 262144 65536 3 10
5 1000 262144 65536 3 10
6 1000 262144 65536 3 10
7 1000 262144 65536 4 6 7 9 10
8 1000 262144 65536 4 6 7 9 10
9 1000 262144 65536 4 6 7 9 10
10 1000 262144 65536 5 8 9 10
11 1000 262144 65536 5 8 9 10
12 1000 262144 65536 5 8 9 10
13 1000 262144 65536 6 7 9 10
14 1000 262144 65536 6 7 9 10
15 1000 262144 65536 6 7 9 10
16 1000 262144 65536 7 10
17 1000 262144 65536 7 10
18 1000 262144 65536 7 10
19 1000 262144 65536 8 9 10
20 1000 262144 65536 8 9 10
21 1000 262144 65536 8 9 10
22 1000 262144 65536 9 10
23 1000 262144 65536 9 10
24 1000 262144 65536 9 10
25 1000 262144 65536 10
26 1000 262144 65536 10
27 1000 262144 65536 10
28 1000 262144 65536 10
29 1000 262144 65536 10
Submit
Back to Top