fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std; 
  4.  
  5. typedef long long ll; 
  6. typedef pair<int, int> ii; 
  7.  
  8. const ll LINF = 1e18; 
  9. const int INF = 1e9;
  10.  
  11. // Ta có n * m <= 30 
  12. // => min(n, m) <= sqrt(30) ~ 5
  13. // Do đó, ta luôn chọn chiều nhỏ hơn để làm trạng thái DP nhằm tối ưu độ phức tạp 
  14. int n, m; 
  15. ll dp[31][1 << 5]; // dp[i][mask] = Số cách xếp bò thoả mãn khi xét i hàng/cột đầu tiên 
  16. 				   //               với mask biểu diễn trạng thái của hàng/cột thứ i 
  17. 				   //               (0: ô đất trống, 1: ô có bò) 
  18.  
  19. int getBit(int mask, int i) {
  20. 	return ((mask >> i) & 1); 
  21. }
  22.  
  23. bool valid(int prev_mask, int mask) {
  24. 	for (int j = 0; j + 1 < m; j++) {
  25. 		int a = getBit(prev_mask, j); 
  26. 		int b = getBit(prev_mask, j + 1); 
  27. 		int c = getBit(mask, j); 
  28. 		int d = getBit(mask, j + 1); 
  29. 		if (a == b && b == c && c == d) return false; 
  30. 	}
  31. 	return true; 
  32. }
  33.  
  34. void solve() {
  35. 	cin >> n >> m;  
  36. 	if (n < m) swap(n, m); 
  37.  
  38. 	for (int i = 1; i <= n; i++) {
  39. 		for (int mask = 0; mask < (1 << m); mask++) {
  40. 			if (i == 1) {
  41. 				dp[i][mask] = 1;  
  42. 				continue; 
  43. 			}
  44. 			dp[i][mask] = 0;  
  45. 			for (int prev_mask = 0; prev_mask < (1 << m); prev_mask++) {
  46. 				if (!valid(prev_mask, mask)) continue;  
  47. 				dp[i][mask] += dp[i - 1][prev_mask]; 
  48. 			}
  49. 		}
  50. 	} // O(n * 2^2m * m)	
  51.  
  52. 	ll ans = 0; 
  53. 	for (int mask = 0; mask < (1 << m); mask++) {
  54. 		ans += dp[n][mask]; 
  55. 	} 
  56.  
  57. 	cout << ans << '\n'; 
  58. }
  59.  
  60. int main() {
  61. 	ios::sync_with_stdio(false); 
  62. 	cin.tie(nullptr); 
  63. 	int tt; 
  64. 	cin >> tt; 
  65. 	while (tt--) {
  66. 		solve(); 
  67. 	}
  68. }
  69.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1
1 1
stdout
copy 
2
https://ideone.com/DNVPDQ
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!