2153 . 開窗戶

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

67.4% (31/46)

Submission's AC Ratio

26.6% (63/237)

Tags

CKcon 2020-CKcon

Description

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

由於可能的方法太多了，所以蛋餅希望你告訴它方法數量除以 K(2≤K≤109+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≤2 1
2 0~5 N,M≤4 19
3 0~13 N,M≤8 20
4 0~21 N,M≤12 25
5 0~29 N,M≤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