1106.md (6663B)
1 Source: https://codeforces.com/blog/entry/64928 2 3 Tutorial is loading... 4 5 **Code** 6 7 ``` 8 #include <bits/stdc++.h> 9 #define N 510 10 using namespace std; 11 12 char a[N][N]; 13 int n; 14 int main(){ 15 scanf("%d", &n); 16 for (int i = 1; i <= n; i++){ 17 scanf("%s", a[i] + 1); 18 } 19 20 int ans = 0; 21 for (int i = 2; i < n; i++){ 22 for (int j = 2; j < n; j++){ 23 if (a[i][j] == 'X' && a[i - 1][j - 1] == 'X' && a[i - 1][j + 1] == 'X' 24 && a[i + 1][j - 1] == 'X' && a[i + 1][j + 1] == 'X'){ 25 ans ++; 26 } 27 } 28 } 29 printf("%d\n", ans); 30 return 0; 31 } 32 ``` 33 34 Tutorial is loading... 35 36 **Code** 37 38 ``` 39 #include <bits/stdc++.h> 40 #define N 300010 41 #define PII pair<int, int> 42 using namespace std; 43 44 typedef long long LL; 45 46 int n, m, a[N], c[N], t, d; 47 LL ans = 0; 48 49 priority_queue<PII, vector<PII>, greater<PII> > Q; 50 51 int main(){ 52 scanf("%d%d", &n, &m); 53 for (int i = 1; i <= n; i++){ 54 scanf("%d", &a[i]); 55 } 56 57 for (int i = 1; i <= n; i++){ 58 scanf("%d", &c[i]); 59 Q.push(make_pair(c[i], i)); 60 } 61 62 for (int i = 1; i <= m; i++){ 63 scanf("%d%d", &t, &d); 64 if (d <= a[t]){ 65 a[t] -= d; 66 printf("%lld\n", 1LL * d * c[t]); 67 } else { 68 bool flag = false; 69 LL ans = 1LL * a[t] * c[t]; 70 d -= a[t]; 71 a[t] = 0; 72 while (!Q.empty()){ 73 while (!Q.empty() && a[Q.top().second] == 0) Q.pop(); 74 if (Q.empty()) break; 75 PII now = Q.top(); 76 if (d <= a[now.second]){ 77 a[now.second] -= d; 78 ans += 1LL * d * now.first; 79 flag = true; 80 printf("%lld\n", ans); 81 break; 82 } else { 83 ans += 1LL * a[now.second] * now.first; 84 d -= a[now.second]; 85 a[now.second] = 0; 86 Q.pop(); 87 } 88 } 89 90 if (!flag){ 91 puts("0"); 92 } 93 } 94 } 95 } 96 ``` 97 98 Tutorial is loading... 99 100 **Code** 101 102 ``` 103 #include <bits/stdc++.h> 104 #define N 300010 105 using namespace std; 106 107 typedef long long LL; 108 109 int n, a[N]; 110 LL ans = 0; 111 112 int main(){ 113 scanf("%d", &n); 114 for (int i = 1; i <= n; i++){ 115 scanf("%d", &a[i]); 116 } 117 sort(a + 1, a + n + 1); 118 for (int i = 1; i <= n / 2; i++){ 119 ans += 1LL * (a[i] + a[n - i + 1]) * (a[i] + a[n - i + 1]); 120 } 121 printf("%lld\n", ans); 122 return 0; 123 } 124 ``` 125 126 Tutorial is loading... 127 128 **Code** 129 130 ``` 131 #include <bits/stdc++.h> 132 #define N 300010 133 using namespace std; 134 135 typedef long long LL; 136 137 priority_queue<int, vector<int>, greater<int> > Q; 138 vector<int> e[N]; 139 vector<int> seq; 140 bool vis[N]; 141 int n, m; 142 143 int main(){ 144 scanf("%d%d", &n, &m); 145 for (int i = 1; i <= m; i++){ 146 int u, v; 147 scanf("%d%d", &u, &v); 148 e[u].push_back(v); 149 e[v].push_back(u); 150 } 151 152 vis[1] = true; 153 Q.push(1); 154 while (!Q.empty()){ 155 int now = Q.top(); 156 Q.pop(); 157 seq.push_back(now); 158 for (auto p : e[now]){ 159 if (!vis[p]){ 160 Q.push(p); 161 vis[p] = true; 162 } 163 } 164 } 165 166 for (auto p : seq){ 167 printf("%d ", p); 168 } 169 puts(""); 170 return 0; 171 } 172 ``` 173 174 Tutorial is loading... 175 176 **Code** 177 178 ``` 179 #include <bits/stdc++.h> 180 #define N 100010 181 using namespace std; 182 183 typedef long long LL; 184 185 struct Event{ 186 int d, w, t; 187 188 bool operator < (const Event &e) const { 189 return w > e.w || (w == e.w && d > e.d); 190 } 191 }; 192 193 vector<Event> e[N]; 194 Event a[N]; 195 map<Event, int> cur; 196 int n, m, k; 197 198 LL f[2][N], ans = 0x3f3f3f3f3f3f3f3fLL; 199 200 void insert(Event x){ 201 if (cur.count(x)){ 202 cur[x] ++; 203 } else { 204 cur[x] = 1; 205 } 206 } 207 208 void erase(Event x){ 209 cur[x] --; 210 if (cur[x] == 0){ 211 cur.erase(x); 212 } 213 } 214 215 int main(){ 216 scanf("%d%d%d", &n, &m, &k); 217 for (int i = 1; i <= k; i++){ 218 int s, t, d, w; 219 scanf("%d%d%d%d", &s, &t, &d, &w); 220 e[s].push_back((Event){d, w, 1}); 221 e[t + 1].push_back((Event){d, w, -1}); 222 } 223 224 for (int i = 1; i <= n; i++){ 225 for (auto p : e[i]){ 226 if (p.t == 1){ 227 insert(p); 228 } else { 229 erase(p); 230 } 231 } 232 233 if (cur.size()){ 234 a[i] = (*cur.begin()).first; 235 } else { 236 a[i] = (Event){i, 0, 0}; 237 } 238 } 239 240 memset(f, 0x3f, sizeof(f)); 241 f[0][1] = 0; 242 for (int j = 0; j <= m; j++){ 243 memset(f[(j ^ 1) & 1], 0x3f, sizeof(f[(j ^ 1) & 1])); 244 for (int i = 1; i <= n; i++){ 245 f[(j ^ 1) & 1][i + 1] = min(f[(j ^ 1) & 1][i + 1], f[j & 1][i]); 246 f[j & 1][a[i].d + 1] = min(f[j & 1][a[i].d + 1], f[j & 1][i] + a[i].w); 247 } 248 ans = min(ans, f[j & 1][n + 1]); 249 } 250 printf("%lld\n", ans); 251 return 0; 252 } 253 ``` 254 255 Tutorial is loading... 256 257 **Code** 258 259 ``` 260 #include <bits/stdc++.h> 261 #define N 210 262 using namespace std; 263 typedef long long LL; 264 265 const LL p = 998244353; 266 const LL g = 3; 267 268 int k; 269 LL n, m, b[N]; 270 271 struct Matrix{ 272 int n; 273 LL mat[N][N]; 274 275 Matrix(){ 276 n = 0; 277 memset(mat, 0, sizeof(mat)); 278 } 279 280 Matrix(int _n, LL diag){ 281 n = _n; 282 memset(mat, 0, sizeof(mat)); 283 for (int i = 1; i <= n; i++){ 284 mat[i][i] = diag; 285 } 286 } 287 288 Matrix(const Matrix &c){ 289 n = c.n; 290 for (int i = 1; i <= n; i++){ 291 for (int j = 1; j <= n; j++){ 292 mat[i][j] = c.mat[i][j]; 293 } 294 } 295 } 296 297 Matrix operator * (const Matrix &a) const { 298 Matrix ans = Matrix(n, 0); 299 for (int k = 1; k <= n; k++){ 300 for (int i = 1; i <= n; i++){ 301 for (int j = 1; j <= n; j++){ 302 ans.mat[i][j] += mat[i][k] * a.mat[k][j]; 303 ans.mat[i][j] %= (p - 1); 304 } 305 } 306 } 307 return ans; 308 } 309 310 Matrix mat_pow(LL t){ 311 Matrix base = Matrix(*this), ans = Matrix(n, 1); 312 while (t){ 313 if (t & 1){ 314 ans = ans * base; 315 } 316 base = base * base; 317 t >>= 1; 318 } 319 return ans; 320 } 321 322 }; 323 324 namespace GCD{ 325 LL gcd(LL a, LL b){ 326 if (!b) return a; 327 return gcd(b, a % b); 328 } 329 330 LL ex_gcd(LL a, LL b, LL &x, LL &y){ 331 if (!b){ 332 x = 1; y = 0; 333 return a; 334 } 335 336 LL q = ex_gcd(b, a % b, y, x); 337 y -= a / b * x; 338 return q; 339 } 340 } 341 342 namespace BSGS{ 343 LL qpow(LL a, LL b, LL p){ 344 LL ans = 1, base = a; 345 while (b){ 346 if (b & 1){ 347 (ans *= base) %= p; 348 } 349 (base *= base) %= p; 350 b >>= 1; 351 } 352 return ans; 353 } 354 355 LL inv(LL x, LL p){ 356 return qpow(x, p - 2, p); 357 } 358 359 map<LL, LL> tab; 360 LL bsgs(LL a, LL b, LL p){ 361 LL u = (LL) sqrt(p) + 1; 362 LL now = 1, step; 363 for (LL i = 0; i < u; i++){ 364 LL tmp = b * inv(now, p) % p; 365 if (!tab.count(tmp)){ 366 tab[tmp] = i; 367 } 368 (now *= a) %= p; 369 } 370 step = now; 371 now = 1; 372 for (LL i = 0; i < p; i += u){ 373 if (tab.count(now)){ 374 return i + tab[now]; 375 } 376 (now *= step) %= p; 377 } 378 throw; 379 return -1; 380 } 381 } 382 383 namespace SOL{ 384 LL solve(LL a, LL b, LL c){ 385 if (c == 0) return 0; 386 LL q = GCD::gcd(a, b); 387 if (c % q){ 388 return -1; 389 } 390 a /= q, b /= q, c /= q; 391 LL ans, _; 392 GCD::ex_gcd(a, b, ans, _); 393 (ans *= c) %= b; 394 while (ans < 0) ans += b; 395 return ans; 396 } 397 } 398 399 int main(){ 400 scanf("%d", &k); 401 for (int i = 1; i <= k; i++){ 402 scanf("%d", &b[i]); 403 b[i] %= (p - 1); 404 } 405 406 scanf("%lld%lld", &n, &m); 407 408 Matrix A = Matrix(k, 0); 409 for (int i = 1; i <= k; i++){ 410 A.mat[1][i] = b[i]; 411 } 412 413 for (int i = 2; i <= k; i++){ 414 A.mat[i][i - 1] = 1; 415 } 416 417 A = A.mat_pow(n - k); 418 419 LL ans = SOL::solve(A.mat[1][1], p - 1, BSGS::bsgs(g, m, p)); 420 if (ans >= 0){ 421 printf("%lld\n", BSGS::qpow(g, ans, p)); 422 } else { 423 puts("-1"); 424 } 425 return 0; 426 } 427 ```