2153 . 開窗戶

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

67.4% (31/46)

Submission's AC Ratio

26.6% (63/237)

Tags

CKcon 2020-CKcon

Description

好熱啊
隨著地球暖化，現在夏天越來越熱
沒有開窗戶根本就受不了
在祕密的教室裡，有$N \times M$ 個窗戶形成 $N, (2 \leq N \leq 16) \times M, (2 \leq M \leq 16)$ 的平面
因為實在太熱了，所以你知道對於每一個 $2 \times 2$ 的窗戶們，至少要有兩個窗戶是打開的，不然全班都會熱死。
先不要管為什麼不全部打開，班上最軟的蛋餅忽然問你，有多少種開窗戶的方法能讓班上不熱死呢？
為了成功玩到蛋餅的肚子，你決定趕快告訴他有幾種方法。

由於可能的方法太多了，所以蛋餅希望你告訴它方法數量除以 $K (2 \leq K \leq 10^ 9 + 9)$ 的餘數就好了

Input Format

第一行有三個正整數 $N\ M\ K$ 以一個空白隔開，意義如題目所述

Output Format

請輸出一個介於 $[0, K)$ 的整數，代表答案

Sample Input 1

2 2 100

Sample Output 1

11

Hints

小心 overflow 喔 xddddd
記得模運算很慢喔 ><><><>

關於範測一
以xx方格表示關閉的窗戶，....方格表示開啟的窗戶
則下圖為所有合法的開窗戶方法

Problem Source

by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0 $N, M \leq 2$ 1
2 0~5 $N, M \leq 4$ 19
3 0~13 $N, M \leq 8$ 20
4 0~21 $N, M \leq 12$ 25
5 0~29 $N, M \leq 16$ 35

Testdata and Limits

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