More actions
({CREATE}) |
No edit summary |
||
| Line 13: | Line 13: | ||
== 박인서 == | == 박인서 == | ||
#include <iostream> | |||
#include <cstring> | |||
int d[14 * 14][1 << 14]; | |||
int n, m; | |||
int go(int t, int s) { | |||
if (t >= n*m) { | |||
if(t == n*m && s == 0) return 1; | |||
return 0; | |||
} | |||
if (d[t][s] >= 0) return d[t][s] % 9901; | |||
int& res = d[t][s]; | |||
if (s % 2 == 1) res=go(t + 1, s >> 1); | |||
else { | |||
res = go(t + 1, (s >> 1) | (1 << m - 1)); | |||
if (s % 4 == 0 && t%m != (m - 1)) res+=go(t + 2, s >> 2); | |||
} | |||
return res % 9901; | |||
} | |||
int main() { | |||
std::cin >> n >> m; | |||
memset(d, -1, sizeof(d)); | |||
std::cout << go(0, 0); | |||
return 0; | |||
} | |||
== 곽정흠 == | == 곽정흠 == | ||
| Line 20: | Line 49: | ||
== 박인서 == | == 박인서 == | ||
* 비트마스크를 이용한 DP | |||
== 곽정흠 == | == 곽정흠 == | ||
Revision as of 07:58, 7 October 2016
오늘의 문제
참가자
- 15이원준
- 박인서
코드
15이원준
박인서
#include <iostream>
#include <cstring>
int d[14 * 14][1 << 14];
int n, m;
int go(int t, int s) {
if (t >= n*m) {
if(t == n*m && s == 0) return 1;
return 0;
}
if (d[t][s] >= 0) return d[t][s] % 9901;
int& res = d[t][s];
if (s % 2 == 1) res=go(t + 1, s >> 1);
else {
res = go(t + 1, (s >> 1) | (1 << m - 1));
if (s % 4 == 0 && t%m != (m - 1)) res+=go(t + 2, s >> 2);
}
return res % 9901;
}
int main() {
std::cin >> n >> m;
memset(d, -1, sizeof(d));
std::cout << go(0, 0);
return 0;
}
곽정흠
아이디어
15이원준
박인서
- 비트마스크를 이용한 DP