//Pawel Kura #include <cstdio> #include <iostream> #include <vector> #include "poszukiwania.h" #include "message.h" using namespace std; typedef long long LL; const int mods[] = {1410666193, (int)1e9+7, (int)1e9+9}; const int M = 2; const int X[] = {1993, 79378913, 1581839} ; struct { int total, id; } node; struct { int len; int from, to; } seq; struct { int len; int from, to; int sum[M]; } pat; void getinfo() { node.total = NumberOfNodes(); node.id = MyNodeId(); seq.len = SeqLength(); seq.from = node.id * ((seq.len + node.total - 1) / node.total); seq.to = min((node.id + 1) * ((seq.len + node.total - 1) / node.total), seq.len) - 1; pat.len = SignalLength(); pat.from = node.id * ((pat.len + node.total - 1) / node.total); pat.to = min((node.id + 1) * ((pat.len + node.total - 1) / node.total), pat.len) - 1; //cerr << "jestem " << node.id << " " << seq.from << " " << seq.to << " " << seq.len << " " << pat.from << " " << pat.to << " " << pat.len << "\n"; } int fastpot(int a, int b, int m) { if (b == 0) return 1; int r = fastpot(a, b/2, m); r = (1LL * r * r) % m; if (b%2 == 0) return r; else return (1LL * r * a) % m; } void calcpat() { int h[M]; int pot[M]; if (pat.from <= pat.to) { int z = SignalAt(pat.from + 1); for (int m = 0; m < M; m++) { h[m] = z % mods[m]; //pot[m] = X % mods[m]; } for (int i = pat.from + 1; i <= pat.to; i++){ int z = SignalAt(i + 1); for (int m = 0; m < M; m++) { h[m] = (1LL * h[m] * X[m] + z) % mods[m]; //pot[m] = (1LL * pot[m] * X) % mods[m]; } } // for (int i = pat.from; i <= pat.to; i++) cerr << "hasz" << i << " " << h[0][i-pat.from] << endl; } for (int m = 0; m < M; m++) pot[m] = fastpot(X[m], pat.to-pat.from+1, mods[m]); int sum[M]; if (node.id > 0) { Receive(node.id - 1); for (int m = 0; m < M; m++) sum[m] = GetInt(node.id - 1); } else { for (int m = 0; m < M; m++) sum[m] = 0; } //cerr << "sumA " << sum[0] << endl; if (pat.from <= pat.to) { for (int m = 0; m < M; m++) sum[m] = (1LL * sum[m] * pot[m] + h[m]) % mods[m]; } //cerr << "sumB " << sum[0] << endl; if (node.id + 1 < node.total) { for (int m = 0; m < M; m++) PutInt(node.id + 1, sum[m]); Send(node.id + 1); Receive(node.id + 1); for (int m = 0; m < M; m++) sum[m] = GetInt(node.id + 1); } //cerr << "sumC " << sum[0] << endl; if (node.id > 0) { for (int m = 0; m < M; m++) PutInt(node.id - 1, sum[m]); Send(node.id - 1); } for (int m = 0; m < M; m++) pat.sum[m] = sum[m]; //cerr << "patsum " << pat.sum[0] << endl; } void calcseq() { int h[M]; int pot[M]; if (seq.from <= seq.to) { for (int m = 0; m < M; m++) { //h[m].resize(seq.to - seq.from + 1); h[m] = SeqAt(seq.from + 1) % mods[m]; //pot[m] = X % mods[m]; } for (int i = seq.from + 1; i <= seq.to; i++){ int z = SeqAt(i + 1); for (int m = 0; m < M; m++) { h[m] = (1LL * h[m] * X[m] + z) % mods[m]; //pot[m] = (1LL * pot[m] * X) % mods[m]; } } //for (int i = seq.from; i <= seq.to; i++) cerr << "hasz2 " << i << " " << h[0][i-seq.from] << endl; } for (int m = 0; m < M; m++) pot[m] = fastpot(X[m], seq.to-seq.from+1, mods[m]); vector<int> allh[M]; for (int m = 0; m < M; m++) allh[m].resize(node.total); if (node.id > 0) { Receive(node.id - 1); } for (int i = 0; i < node.id; i++){ for (int m = 0; m < M; m++) allh[m][i] = GetInt(node.id - 1); } if (seq.from <= seq.to) { for (int m = 0; m < M; m++) allh[m][node.id] = h[m]; } else { for (int m = 0; m < M; m++) allh[m][node.id] = -1; } if (node.id + 1 < node.total) { for (int i = 0; i <= node.id; i++) { for (int m = 0; m < M; m++) PutInt(node.id + 1, allh[m][i]); } Send(node.id + 1); } if (node.id + 1 < node.total) { Receive(node.id + 1); for (int i = 0; i < node.total; i++) { for (int m = 0; m < M; m++) allh[m][i] = GetInt(node.id + 1); } } if (node.id > 0) { for (int i = 0; i < node.total; i++) { for (int m = 0; m < M; m++) PutInt(node.id - 1, allh[m][i]); } Send(node.id - 1); } //for (int i = 0; i < node.total; i++) //cerr << "allh " << i << " " << allh[0][i] << endl; int cnt = 0; if (seq.from + pat.len <= seq.len) { int hash[M] = {0}; int d = seq.to - seq.from + 1; int t = seq.from; int id = node.id; while (t + d < seq.from + pat.len) { for (int m = 0; m < M; m++) { hash[m] = (1LL * hash[m] * pot[m] + allh[m][id]) % mods[m]; } t += d; id++; } for (int i = t; i <= seq.from + pat.len - 1; i++) { for (int m = 0; m < M; m++) hash[m] = (1LL * hash[m] * X[m] + SeqAt(i+1)) % mods[m]; } //cerr << "prehasz " << hash[0] << endl; int bigpot[M] = {1}; for (int m = 0; m < M; m++) bigpot[m] = fastpot(X[m], pat.len, mods[m]); //cerr << "bigpot " << bigpot[0] << endl; int p = seq.from; int q = seq.from + pat.len - 1; while (p <= seq.to && q < seq.len) { bool ok = true; //cerr << "[" << p << ", " << q<< "] " << hash[0] << endl; for (int m = 0; m < M; m++) if (hash[m] != pat.sum[m]) { ok = false; break; } if (ok) cnt++; p++; q++; if (q == seq.len) break; for (int m = 0; m < M; m++){ hash[m] = (1LL * hash[m] * X[m] + SeqAt(q + 1)) % mods[m]; hash[m] = (hash[m] - 1LL * bigpot[m] * SeqAt(p-1 + 1)) % mods[m]; hash[m] = (hash[m] + mods[m]) % mods[m]; } } } //cerr << "cnt " << cnt << endl; PutInt(0, cnt); Send(0); if (node.id == 0) { int res = 0; for (int i = 0; i < node.total; i++) { res += GetInt(Receive(-1)); } cout << res << endl; } } int main() { getinfo(); calcpat(); calcseq(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 | //Pawel Kura #include <cstdio> #include <iostream> #include <vector> #include "poszukiwania.h" #include "message.h" using namespace std; typedef long long LL; const int mods[] = {1410666193, (int)1e9+7, (int)1e9+9}; const int M = 2; const int X[] = {1993, 79378913, 1581839} ; struct { int total, id; } node; struct { int len; int from, to; } seq; struct { int len; int from, to; int sum[M]; } pat; void getinfo() { node.total = NumberOfNodes(); node.id = MyNodeId(); seq.len = SeqLength(); seq.from = node.id * ((seq.len + node.total - 1) / node.total); seq.to = min((node.id + 1) * ((seq.len + node.total - 1) / node.total), seq.len) - 1; pat.len = SignalLength(); pat.from = node.id * ((pat.len + node.total - 1) / node.total); pat.to = min((node.id + 1) * ((pat.len + node.total - 1) / node.total), pat.len) - 1; //cerr << "jestem " << node.id << " " << seq.from << " " << seq.to << " " << seq.len << " " << pat.from << " " << pat.to << " " << pat.len << "\n"; } int fastpot(int a, int b, int m) { if (b == 0) return 1; int r = fastpot(a, b/2, m); r = (1LL * r * r) % m; if (b%2 == 0) return r; else return (1LL * r * a) % m; } void calcpat() { int h[M]; int pot[M]; if (pat.from <= pat.to) { int z = SignalAt(pat.from + 1); for (int m = 0; m < M; m++) { h[m] = z % mods[m]; //pot[m] = X % mods[m]; } for (int i = pat.from + 1; i <= pat.to; i++){ int z = SignalAt(i + 1); for (int m = 0; m < M; m++) { h[m] = (1LL * h[m] * X[m] + z) % mods[m]; //pot[m] = (1LL * pot[m] * X) % mods[m]; } } // for (int i = pat.from; i <= pat.to; i++) cerr << "hasz" << i << " " << h[0][i-pat.from] << endl; } for (int m = 0; m < M; m++) pot[m] = fastpot(X[m], pat.to-pat.from+1, mods[m]); int sum[M]; if (node.id > 0) { Receive(node.id - 1); for (int m = 0; m < M; m++) sum[m] = GetInt(node.id - 1); } else { for (int m = 0; m < M; m++) sum[m] = 0; } //cerr << "sumA " << sum[0] << endl; if (pat.from <= pat.to) { for (int m = 0; m < M; m++) sum[m] = (1LL * sum[m] * pot[m] + h[m]) % mods[m]; } //cerr << "sumB " << sum[0] << endl; if (node.id + 1 < node.total) { for (int m = 0; m < M; m++) PutInt(node.id + 1, sum[m]); Send(node.id + 1); Receive(node.id + 1); for (int m = 0; m < M; m++) sum[m] = GetInt(node.id + 1); } //cerr << "sumC " << sum[0] << endl; if (node.id > 0) { for (int m = 0; m < M; m++) PutInt(node.id - 1, sum[m]); Send(node.id - 1); } for (int m = 0; m < M; m++) pat.sum[m] = sum[m]; //cerr << "patsum " << pat.sum[0] << endl; } void calcseq() { int h[M]; int pot[M]; if (seq.from <= seq.to) { for (int m = 0; m < M; m++) { //h[m].resize(seq.to - seq.from + 1); h[m] = SeqAt(seq.from + 1) % mods[m]; //pot[m] = X % mods[m]; } for (int i = seq.from + 1; i <= seq.to; i++){ int z = SeqAt(i + 1); for (int m = 0; m < M; m++) { h[m] = (1LL * h[m] * X[m] + z) % mods[m]; //pot[m] = (1LL * pot[m] * X) % mods[m]; } } //for (int i = seq.from; i <= seq.to; i++) cerr << "hasz2 " << i << " " << h[0][i-seq.from] << endl; } for (int m = 0; m < M; m++) pot[m] = fastpot(X[m], seq.to-seq.from+1, mods[m]); vector<int> allh[M]; for (int m = 0; m < M; m++) allh[m].resize(node.total); if (node.id > 0) { Receive(node.id - 1); } for (int i = 0; i < node.id; i++){ for (int m = 0; m < M; m++) allh[m][i] = GetInt(node.id - 1); } if (seq.from <= seq.to) { for (int m = 0; m < M; m++) allh[m][node.id] = h[m]; } else { for (int m = 0; m < M; m++) allh[m][node.id] = -1; } if (node.id + 1 < node.total) { for (int i = 0; i <= node.id; i++) { for (int m = 0; m < M; m++) PutInt(node.id + 1, allh[m][i]); } Send(node.id + 1); } if (node.id + 1 < node.total) { Receive(node.id + 1); for (int i = 0; i < node.total; i++) { for (int m = 0; m < M; m++) allh[m][i] = GetInt(node.id + 1); } } if (node.id > 0) { for (int i = 0; i < node.total; i++) { for (int m = 0; m < M; m++) PutInt(node.id - 1, allh[m][i]); } Send(node.id - 1); } //for (int i = 0; i < node.total; i++) //cerr << "allh " << i << " " << allh[0][i] << endl; int cnt = 0; if (seq.from + pat.len <= seq.len) { int hash[M] = {0}; int d = seq.to - seq.from + 1; int t = seq.from; int id = node.id; while (t + d < seq.from + pat.len) { for (int m = 0; m < M; m++) { hash[m] = (1LL * hash[m] * pot[m] + allh[m][id]) % mods[m]; } t += d; id++; } for (int i = t; i <= seq.from + pat.len - 1; i++) { for (int m = 0; m < M; m++) hash[m] = (1LL * hash[m] * X[m] + SeqAt(i+1)) % mods[m]; } //cerr << "prehasz " << hash[0] << endl; int bigpot[M] = {1}; for (int m = 0; m < M; m++) bigpot[m] = fastpot(X[m], pat.len, mods[m]); //cerr << "bigpot " << bigpot[0] << endl; int p = seq.from; int q = seq.from + pat.len - 1; while (p <= seq.to && q < seq.len) { bool ok = true; //cerr << "[" << p << ", " << q<< "] " << hash[0] << endl; for (int m = 0; m < M; m++) if (hash[m] != pat.sum[m]) { ok = false; break; } if (ok) cnt++; p++; q++; if (q == seq.len) break; for (int m = 0; m < M; m++){ hash[m] = (1LL * hash[m] * X[m] + SeqAt(q + 1)) % mods[m]; hash[m] = (hash[m] - 1LL * bigpot[m] * SeqAt(p-1 + 1)) % mods[m]; hash[m] = (hash[m] + mods[m]) % mods[m]; } } } //cerr << "cnt " << cnt << endl; PutInt(0, cnt); Send(0); if (node.id == 0) { int res = 0; for (int i = 0; i < node.total; i++) { res += GetInt(Receive(-1)); } cout << res << endl; } } int main() { getinfo(); calcpat(); calcseq(); return 0; } |