usaco-camp

Short, concise solutions for problems from the USACO camp

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll p1 = 19, p2 = 29, p3 = 53;
constexpr ll MOD = 1e9+7;

template<int D, typename T> struct vec_nd : public vector<vec_nd<D - 1, T>> {
  static_assert(D >= 1, "Vector dimension must be greater than zero!");
  template<typename... Args> vec_nd(int n = 0, Args... args) : vector<vec_nd<D - 1, T>>(n, vec_nd<D - 1, T>(args...)) { }
};
template<typename T> struct vec_nd<1, T> : public vector<T> { vec_nd(int n = 0, const T& val = T()) : vector<T>(n, val) { } };

int pw(int base, int exp) {
	int res = 1;
	while (exp) {
		if (exp & 1) res = (ll)base * res % MOD;
		exp >>= 1, base = (ll)base * base % MOD;
	}
	return res;
}

int inv(int x) { return pw(x, MOD - 2); }

int main() {
	int T1, R1, C1; cin >> T1 >> R1 >> C1;
	vec_nd<3, ll> A(T1, R1, C1);
	for (int i = 0; i < T1; ++i) for (int j = 0; j < R1; ++j) for (int k = 0; k < C1; ++k) cin >> A[i][j][k];
	
	int T2, R2, C2; cin >> T2 >> R2 >> C2;
	vec_nd<3, ll> B(T2, R2, C2);
	for (int i = 0; i < T2; ++i) for (int j = 0; j < R2; ++j) for (int k = 0; k < C2; ++k) cin >> B[i][j][k];
	
	ll h = 0;
	ll pw1 = 1; for (int i = 0; i < T1; ++i) {
		ll pw2 = 1; for (int j = 0; j < R1; ++j) {
			ll pw3 = 1; for (int k = 0; k < C1; ++k) {
				h = (A[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 + h) % MOD;
			pw3 = p3 * pw3 % MOD; }
		pw2 = p2 * pw2 % MOD; }
	pw1 = p1 * pw1 % MOD; }

	vec_nd<3, ll> S(T2, R2, C2);
	pw1 = 1; for (int i = 0; i < T2; ++i) {
		ll pw2 = 1; for (int j = 0; j < R2; ++j) {
			ll pw3 = 1; for (int k = 0; k < C2; ++k) {
				S[i][j][k] = B[i][j][k] * pw1 % MOD * pw2 % MOD * pw3 % MOD;
				if (i) S[i][j][k] += S[i - 1][j][k];
				if (j) S[i][j][k] += S[i][j - 1][k];
				if (k) S[i][j][k] += S[i][j][k - 1];
				if (i && j) S[i][j][k] -= S[i - 1][j - 1][k];
				if (i && k) S[i][j][k] -= S[i - 1][j][k - 1];
				if (j && k) S[i][j][k] -= S[i][j - 1][k - 1];				
				if (i && j && k) S[i][j][k] += S[i - 1][j - 1][k - 1];
				S[i][j][k] = (S[i][j][k] + MOD * MOD) % MOD;
			pw3 = p3 * pw3 % MOD; }
		pw2 = p2 * pw2 % MOD; }
	pw1 = p1 * pw1 % MOD; }

	ll ans = 0;
	pw1 = 1; for (int i = 0; i <= T2 - T1; ++i) {
		ll pw2 = 1; for (int j = 0; j <= R2 - R1; ++j) {
			ll pw3 = 1;	for (int k = 0; k <= C2 - C1; ++k) {
				ll h2 = S[i + T1 - 1][j + R1 - 1][k + C1 - 1];
				if (i) h2 -= S[i - 1][j + R1 - 1][k + C1 - 1];
				if (j) h2 -= S[i + T1 - 1][j - 1][k + C1 - 1];
				if (k) h2 -= S[i + T1 - 1][j + R1 - 1][k - 1];
				if (i && j) h2 += S[i - 1][j - 1][k + C1 - 1];
				if (i && k) h2 += S[i - 1][j + R1 - 1][k - 1];
				if (j && k) h2 += S[i + T1 - 1][j - 1][k - 1];				
				if (i && j && k) h2 -= S[i - 1][j - 1][k - 1];
				h2 = (h2 + MOD * MOD) % MOD;
				h2 = h2 * inv(pw3) % MOD * inv(pw2) % MOD * inv(pw1) % MOD;
				if (h2 == h) ++ans;
			pw3 = p3 * pw3 % MOD; }
		pw2 = p2 * pw2 % MOD; }
	pw1 = p1 * pw1 % MOD; }
	cout << ans << '\n';
}