fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3.  
  4. #include <iostream>
  5. #include <cstring>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. const ll inf = 1000 * 1000 * 1000 + 7;
  13.  
  14. bool getBit(ll mask, ll index) {
  15. 	return mask&(1ll << index);
  16. }
  17. long long dp[20][5007][307];
  18. bool used[5007][5007];
  19. int main() {
  20. 	int n, m, k;
  21. 	scanf("%d%d%d", &n, &m, &k);
  22. 	memset(dp, 0, sizeof(dp));
  23. 	vector<ll> Tried,Tried_king;
  24. 	for (ll mask = 0; mask < 1 << n; ++mask) {
  25. 		ll index = 0;
  26. 		bool Cheak = true;
  27. 		for (ll index = 1; 1 << index <= mask; ++index) {
  28. 			if (getBit(mask, index - 1) == 1 && getBit(mask, index) == 1) {
  29. 				Cheak = false; break;
  30. 			}
  31. 		}
  32. 		if (Cheak == true)Tried.push_back(mask);
  33. 	}
  34. 	for (ll mask : Tried) {
  35. 		ll King = 0;
  36. 		for (ll index = 0; 1 << index <= mask; ++index) {
  37. 			King += getBit(mask, index);
  38. 		}
  39. 		Tried_king.push_back(King);
  40. 	}
  41. 	vector<pair<ll, ll>> Cur;
  42. 	Cur.resize(n + 1);
  43. 	vector<pair<ll, pair<ll, ll>>> Combination;
  44. 	for (ll mark = 0; mark < Tried.size(); ++mark) {
  45. 		ll i = Tried[mark];
  46. 		ll King = Tried_king[mark];
  47. 		for (ll j : Tried) {
  48. 			if (!used[i][j]) {
  49. 				for (ll ii = 0; ii < n; ++ii)Cur[ii].first = Cur[ii].second = 0;
  50. 				used[i][j] = true;
  51. 				ll t1 = 0, t2 = 0;
  52. 				ll index = 0;
  53. 				while ((1ll<<index)<=i) {
  54. 					Cur[t1++].first = getBit(i, index);
  55. 					++index;
  56. 				}
  57. 				index = 0;
  58. 				while ((1ll << index) <= j) {
  59. 					Cur[t2++].second = getBit(j, index);
  60. 					++index;
  61. 				}
  62. 				bool Cheak = true;
  63. 				for (ll d = 0; d < n; ++d) {
  64. 					ll p = 0;
  65. 					p += Cur[d].second; p += Cur[d].first;
  66. 					if (d != n - 1) {
  67. 						p += Cur[d + 1].first;
  68. 						p += Cur[d + 1].second;
  69. 					}
  70. 					if (d > 0) {
  71. 						p += Cur[d - 1].first; p += Cur[d - 1].second;
  72. 					}
  73. 					if (Cur[d].first == 1 && p > 1) {
  74. 						Cheak = false; break;
  75. 					}
  76. 					if (Cur[d].second == 1 && p > 1) {
  77. 						Cheak = false; break;
  78. 					}
  79. 				}
  80. 				if (Cheak == true) {
  81. 					Combination.push_back(make_pair(King, make_pair(j, i)));
  82. 				}
  83. 			}
  84. 		}
  85. 	}
  86. 	for (ll i = 0; i < Tried.size(); ++i) {
  87. 		dp[0][Tried[i]][Tried_king[i]]++;
  88. 	}
  89. 	for (ll i = 1; i < m; ++i) {
  90. 		for (ll King = 0; King <= k; ++King) {
  91. 			for (pair<ll, pair<ll, ll>>  cur:Combination) {
  92. 				dp[i][cur.second.second][cur.first + King] += dp[i - 1][cur.second.first][King];
  93. 				dp[i][cur.second.second][cur.first + King] %= inf;
  94. 			}
  95. 		}
  96. 	}
  97. 	ll ans = 0;
  98. 	for (ll i = 0; i < Tried.size(); ++i) {
  99. 		ans += dp[m - 1][Tried[i]][k];
  100. 		ans %= inf;
  101. 	}
  102. 	cout << ans << endl;
  103. 	return 0;
  104. }
Success #stdin #stdout 0.15s 280704KB
comments (?)
stdin
copy 
13 13 49
stdout
copy 
432609439
https://ideone.com/PCks5O
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!