78 . 相鄰不同色

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Cheng0928
NLOJ 管理員，題目若有誤請至 Discord 私訊我！

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

16.7% (2/12)

Tags

Description

在一場色彩設計比賽中，參賽者要替一串裝飾燈球上色。
每顆燈球都必須從 $k$ 種顏色中選一種來塗，而評審最在意的條件只有一個：相鄰的兩顆燈球顏色不能相同。

不過這串燈球有兩種擺法：

直線排列：第 $i$ 顆只和第 $i-1$、$i+1$ 顆相鄰。
環狀排列：第 $1$ 顆和第 $n$ 顆也相鄰，形成一個圓圈。

請你計算有多少種合法塗色方式，答案對 $10$$9$ $+ 7$ 取餘數。

對於所有測試資料：
$1 \le ty \le 2$，若 $ty = 1$ 則燈球是直線排列，若 $ty = 2$ 則燈球是環狀排列。
$3 \le n \le 10$$18$
$1 \le k \le 10$$18$

Input Format

共輸入一行，
第一行輸入三個數字 $ty,\ n,\ k$。

Output Format

輸出一個數字代表答案。

Sample Input 1

2 5 3

Sample Output 1

30

Sample Input 2

2 3 2

Sample Output 2

0

Sample Input 3

1 3 3

Sample Output 3

12

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測試資料 0
2 0~19 $n \le 15$ 且 $k \le 3$ 10
3 2, 20~29 $ty = 1$ 且 $n,\ k \le 1000$ 10
4 2, 20~39 $ty = 1$ 且 $n \le 10$$6$ 15
5 2, 20~49 $ty = 1$ 5
6 0~1, 50~59 $ty = 2$ 且 $n,\ k \le 1000$ 15
7 0~1, 50~69 $ty = 2$ 且 $n \le 10$$6$ 35
8 0~1, 50~79 $ty = 2$ 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 6 7 8
1 1000 65536 65536 1 2 6 7 8
2 1000 65536 65536 1 2 3 4 5
3 1000 65536 65536 2
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2
10 1000 65536 65536 2
11 1000 65536 65536 2
12 1000 65536 65536 2
13 1000 65536 65536 2
14 1000 65536 65536 2
15 1000 65536 65536 2
16 1000 65536 65536 2
17 1000 65536 65536 2
18 1000 65536 65536 2
19 1000 65536 65536 2
20 1000 65536 65536 3 4 5
21 1000 65536 65536 3 4 5
22 1000 65536 65536 3 4 5
23 1000 65536 65536 3 4 5
24 1000 65536 65536 3 4 5
25 1000 65536 65536 3 4 5
26 1000 65536 65536 3 4 5
27 1000 65536 65536 3 4 5
28 1000 65536 65536 3 4 5
29 1000 65536 65536 3 4 5
30 1000 65536 65536 4 5
31 1000 65536 65536 4 5
32 1000 65536 65536 4 5
33 1000 65536 65536 4 5
34 1000 65536 65536 4 5
35 1000 65536 65536 4 5
36 1000 65536 65536 4 5
37 1000 65536 65536 4 5
38 1000 65536 65536 4 5
39 1000 65536 65536 4 5
40 1000 65536 65536 5
41 1000 65536 65536 5
42 1000 65536 65536 5
43 1000 65536 65536 5
44 1000 65536 65536 5
45 1000 65536 65536 5
46 1000 65536 65536 5
47 1000 65536 65536 5
48 1000 65536 65536 5
49 1000 65536 65536 5
50 1000 65536 65536 6 7 8
51 1000 65536 65536 6 7 8
52 1000 65536 65536 6 7 8
53 1000 65536 65536 6 7 8
54 1000 65536 65536 6 7 8
55 1000 65536 65536 6 7 8
56 1000 65536 65536 6 7 8
57 1000 65536 65536 6 7 8
58 1000 65536 65536 6 7 8
59 1000 65536 65536 6 7 8
60 1000 65536 65536 7 8
61 1000 65536 65536 7 8
62 1000 65536 65536 7 8
63 1000 65536 65536 7 8
64 1000 65536 65536 7 8
65 1000 65536 65536 7 8
66 1000 65536 65536 7 8
67 1000 65536 65536 7 8
68 1000 65536 65536 7 8
69 1000 65536 65536 7 8
70 1000 65536 65536 8
71 1000 65536 65536 8
72 1000 65536 65536 8
73 1000 65536 65536 8
74 1000 65536 65536 8
75 1000 65536 65536 8
76 1000 65536 65536 8
77 1000 65536 65536 8
78 1000 65536 65536 8
79 1000 65536 65536 8
Submit out of contest
Back to Top