932.md (18041B)
1 Source: https://codeforces.com/blog/entry/57796 2 3 Tutorial is loading... 4 5 **Code** 6 7 ``` 8 #include<bits/stdc++.h> 9 using namespace std; 10 int main() 11 { 12 string s; 13 cin>>s; 14 cout<<s; 15 reverse(s.begin(),s.end()); 16 cout<<s; 17 return 0; 18 } 19 ``` 20 21 Tutorial is loading... 22 23 **Code** 24 25 ``` 26 #include "bits/stdc++.h" 27 28 #ifdef PRINTERS 29 #include "printers.hpp" 30 using namespace printers; 31 #define tr(a) cerr<<#a<<" : "<<a<<endl 32 #else 33 #define tr(a) 34 #endif 35 36 #define ll long long 37 #define pb push_back 38 #define mp make_pair 39 #define pii pair<int,int> 40 #define vi vector<int> 41 #define all(a) (a).begin(),(a).end() 42 #define F first 43 #define S second 44 #define sz(x) (int)x.size() 45 #define hell 1000000007 46 #define endl '\n' 47 #define rep(i,a,b) for(int i=a;i<b;i++) 48 using namespace std; 49 50 int x[10][1000005]; 51 52 int f(int x){ 53 if(x<10)return x; 54 int prod=1; 55 while(x){ 56 if(x%10)prod*=(x%10); 57 x/=10; 58 } 59 return f(prod); 60 } 61 62 void solve(){ 63 for(int i=1;i<=1000000;i++){ 64 x[f(i)][i]++; 65 } 66 for(int i=1;i<10;i++){ 67 for(int j=1;j<=1000000;j++){ 68 x[i][j]+=x[i][j-1]; 69 } 70 } 71 int Q; 72 cin>>Q; 73 while(Q--){ 74 int l,r,k; 75 cin>>l>>r>>k; 76 cout<<x[k][r]-x[k][l-1]<<endl; 77 } 78 } 79 80 int main(){ 81 ios_base::sync_with_stdio(false); 82 cin.tie(0); 83 cout.tie(0); 84 int t=1; 85 // cin>>t; 86 while(t--){ 87 solve(); 88 } 89 return 0; 90 } 91 ``` 92 93 Tutorial is loading... 94 95 **Code** 96 97 ``` 98 #include "bits/stdc++.h" 99 100 #define ll long long 101 #define pb push_back 102 #define mp make_pair 103 #define pii pair<int,int> 104 #define vi vector<int> 105 #define all(a) (a).begin(),(a).end() 106 #define F first 107 #define S second 108 #define sz(x) (int)x.size() 109 #define hell 1000000007 110 #define endl '\n' 111 #define rep(i,a,b) for(int i=a;i<b;i++) 112 using namespace std; 113 114 void solve(){ 115 int n,a,b; 116 cin>>n>>a>>b; 117 vector<int>v(n); 118 iota(all(v),1); 119 int i=0; 120 while(i<n){ 121 if((n-i)%b==0){ 122 if(b>1)rotate(v.begin()+i,v.begin()+i+1,v.begin()+i+b); 123 i+=b; 124 } 125 else{ 126 if(i+a>n){ 127 cout<<-1; 128 return; 129 } 130 if(a>1)rotate(v.begin()+i,v.begin()+i+1,v.begin()+i+a); 131 i+=a; 132 } 133 } 134 for(auto j:v)cout<<j<<" "; 135 } 136 137 int main(){ 138 ios_base::sync_with_stdio(false); 139 cin.tie(0); 140 cout.tie(0); 141 int t=1; 142 // cin>>t; 143 while(t--){ 144 solve(); 145 } 146 return 0; 147 } 148 ``` 149 150 Tutorial is loading... 151 152 Thanks to [radoslav11](/profile/radoslav11 "Master radoslav11") for nice and short editorial in comments. 153 154 **Code** 155 156 ``` 157 #include "bits/stdc++.h" 158 159 #ifdef PRINTERS 160 #include "printers.hpp" 161 using namespace printers; 162 #define tr(a) cerr<<#a<<" : "<<a<<endl 163 #else 164 #define tr(a) 165 #endif 166 #define ll long long 167 #define pb push_back 168 #define mp make_pair 169 #define pii pair<int,int> 170 #define vi vector<int> 171 #define all(a) (a).begin(),(a).end() 172 #define F first 173 #define S second 174 #define sz(x) (int)x.size() 175 #define hell 1000000007 176 #define endl '\n' 177 #define rep(i,a,b) for(int i=a;i<b;i++) 178 using namespace std; 179 180 int par[20][400000]; 181 ll par_sum[20][400000]; 182 int w[400000]; 183 184 void solve(){ 185 int Q; 186 cin>>Q; 187 w[0]=INT_MAX; 188 int last=0; 189 int cur=1; 190 for(int i=0;i<20;i++)par_sum[i][1]=1e16; 191 while(Q--){ 192 int ch; 193 cin>>ch; 194 if(ch==1){ 195 ll p,q; 196 cin>>p>>q; 197 p^=last; 198 q^=last; 199 cur++; 200 w[cur]=q; 201 if(w[p]>=w[cur]){ 202 par[0][cur]=p; 203 } 204 else{ 205 int from=p; 206 for(int i=19;i>=0;i--){ 207 if(w[par[i][from]]<w[cur]) 208 from=par[i][from]; 209 } 210 par[0][cur]=par[0][from]; 211 } 212 par_sum[0][cur]=(par[0][cur]==0?1e16:w[par[0][cur]]); 213 for(int i=1;i<20;i++){ 214 par[i][cur]=par[i-1][par[i-1][cur]]; 215 par_sum[i][cur]=(par[i][cur]==0?1e16:par_sum[i-1][cur]+par_sum[i-1][par[i-1][cur]]); 216 } 217 } 218 else{ 219 ll p,q; 220 cin>>p>>q; 221 p^=last; 222 q^=last; 223 if(w[p]>q){ 224 cout<<0<<endl; 225 last=0; 226 } 227 else{ 228 q-=w[p]; 229 int ans=1; 230 for(int i=19;i>=0;i--){ 231 if(par_sum[i][p]<=q){ 232 ans+=(1<<i); 233 q-=par_sum[i][p]; 234 p=par[i][p]; 235 } 236 } 237 cout<<ans<<endl; 238 last=ans; 239 } 240 } 241 } 242 } 243 244 int main(){ 245 ios_base::sync_with_stdio(false); 246 cin.tie(0); 247 cout.tie(0); 248 int t=1; 249 // cin>>t; 250 while(t--){ 251 solve(); 252 } 253 return 0; 254 } 255 ``` 256 257 Tutorial is loading... 258 259 **Code** 260 261 ``` 262 #include "bits/stdc++.h" 263 264 #define ll long long 265 #define pb push_back 266 #define mp make_pair 267 #define pii pair<int,int> 268 #define vi vector<int> 269 #define all(a) (a).begin(),(a).end() 270 #define F first 271 #define S second 272 #define sz(x) (int)x.size() 273 #define hell 1000000007 274 #define endl '\n' 275 #define rep(i,a,b) for(int i=a;i<b;i++) 276 using namespace std; 277 278 int dp[5001][5001]; 279 ll expo(ll base, ll exponent, ll mod) { 280 ll ans = 1; 281 while(exponent !=0 ) { 282 if((exponent&1) == 1) { 283 ans = ans*base ; 284 ans = ans%mod; 285 } 286 base = base*base; 287 base %= mod; 288 exponent>>= 1; 289 } 290 return ans%mod; 291 } 292 int fill(int diffs,int a,int tot){ 293 if(dp[diffs][a]>=0)return dp[diffs][a]; 294 int b=tot-a; 295 if(diffs==0){ 296 return dp[diffs][a]=expo(2,b,hell); 297 } 298 return dp[diffs][a]=((b?1LL*b*fill(diffs-1,a+1,tot):0LL)+(a?1LL*a*fill(diffs-1,a,tot):0LL))%hell; 299 } 300 301 void solve(){ 302 int N,k; 303 cin>>N>>k; 304 memset(dp,-1,sizeof dp); 305 cout<<fill(k,0,N)<<endl; 306 } 307 308 int main(){ 309 ios_base::sync_with_stdio(false); 310 cin.tie(0); 311 cout.tie(0); 312 int t=1; 313 // cin>>t; 314 while(t--){ 315 solve(); 316 } 317 return 0; 318 } 319 ``` 320 321 Tutorial is loading... 322 323 **Code** 324 325 ``` 326 #include "bits/stdc++.h" 327 328 #define ll long long 329 #define pb push_back 330 #define mp make_pair 331 #define pii pair<int,int> 332 #define vi vector<int> 333 #define all(a) (a).begin(),(a).end() 334 #define F first 335 #define S second 336 #define sz(x) (int)x.size() 337 #define hell 1000000007 338 #define endl '\n' 339 #define rep(i,a,b) for(int i=a;i<b;i++) 340 using namespace std; 341 342 bool Q; 343 struct Line { 344 mutable ll k, m, p; 345 bool operator<(const Line& o) const { 346 return Q ? p < o.p : k < o.k; 347 } 348 }; 349 struct LineContainer : multiset<Line> { 350 const ll inf = LLONG_MAX; 351 ll div(ll a, ll b){ 352 return a / b - ((a ^ b) < 0 && a % b); 353 } 354 bool isect(iterator x, iterator y) { 355 if (y == end()) { x->p = inf; return false; } 356 if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; 357 else x->p = div(y->m - x->m, x->k - y->k); 358 return x->p >= y->p; 359 } 360 void add(ll k, ll m) { 361 auto z = insert({k, m, 0}), y = z++, x = y; 362 while (isect(y, z)) z = erase(z); 363 if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); 364 while ((y = x) != begin() && (--x)->p >= y->p) 365 isect(x, erase(y)); 366 } 367 ll query(ll x) { 368 assert(!empty()); 369 Q = 1; auto l = *lower_bound({0,0,x}); Q = 0; 370 return l.k * x + l.m; 371 } 372 }; 373 374 vector<int> x,y; 375 vector<vi> adj; 376 vector<ll> ans; 377 vector<int> subsize; 378 void dfs1(int u,int v){ 379 subsize[u]=1; 380 for(auto i:adj[u]){ 381 if(i==v)continue; 382 dfs1(i,u); 383 subsize[u]+=subsize[i]; 384 } 385 } 386 387 void dfs2(int v, int p,LineContainer& cur){ 388 int mx=-1,bigChild=-1; 389 bool leaf=1; 390 for(auto u:adj[v]){ 391 if(u!=p and subsize[u]>mx){ 392 mx=subsize[u]; 393 bigChild=u; 394 leaf=0; 395 } 396 } 397 if(bigChild!=-1){ 398 dfs2(bigChild,v,cur); 399 } 400 for(auto u:adj[v]){ 401 if(u!=p and u!=bigChild){ 402 LineContainer temp; 403 dfs2(u,v,temp); 404 for(auto i:temp){ 405 cur.add(i.k,i.m); 406 } 407 } 408 } 409 if(!leaf)ans[v]=-cur.query(x[v]); 410 else ans[v]=0; 411 cur.add(-y[v],-ans[v]); 412 } 413 void solve(){ 414 int n; 415 cin>>n; 416 x.resize(n+1); 417 y.resize(n+1); 418 ans.resize(n+1); 419 subsize.resize(n+1); 420 adj.resize(n+1); 421 rep(i,1,n+1)cin>>x[i]; 422 rep(i,1,n+1)cin>>y[i]; 423 rep(i,1,n){ 424 int u,v; 425 cin>>u>>v; 426 adj[u].pb(v); 427 adj[v].pb(u); 428 } 429 dfs1(1,0); 430 LineContainer lc; 431 dfs2(1,0,lc); 432 rep(i,1,n+1)cout<<ans[i]<<" "; 433 } 434 435 int main(){ 436 ios_base::sync_with_stdio(false); 437 cin.tie(0); 438 cout.tie(0); 439 int t=1; 440 // cin>>t; 441 while(t--){ 442 solve(); 443 } 444 return 0; 445 } 446 ``` 447 448 Tutorial is loading... 449 450 **Code 1** 451 452 ``` 453 #include <bits/stdc++.h> 454 #define ll long long 455 #define pb push_back 456 #define mp make_pair 457 #define pii pair<int,int> 458 #define vi vector<int> 459 #define all(a) (a).begin(),(a).end() 460 #define F first 461 #define S second 462 #define sz(x) (int)x.size() 463 #define hell 1000000007 464 #define endl '\n' 465 using namespace std; 466 const int MAXN=1000005; 467 string s; 468 struct PalindromicTree{ 469 int N,cur; 470 vector<map<int,int>> next; 471 vector<int> link,start,len,diff,slink; 472 PalindromicTree(): N(0),cur(0){ 473 node(); 474 len[0]=-1; 475 node(); 476 } 477 int node(){ 478 next.emplace_back(); 479 link.emplace_back(0); 480 start.emplace_back(0); 481 len.emplace_back(0); 482 diff.emplace_back(0); 483 slink.emplace_back(0); 484 return N++; 485 } 486 void add_letter(int idx){ 487 while(true){ 488 if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]) 489 break; 490 cur=link[cur]; 491 } 492 if(next[cur].find(s[idx])!=next[cur].end()){ 493 cur=next[cur][s[idx]]; 494 return; 495 } 496 node(); 497 next[cur][s[idx]]=N-1; 498 len[N-1]=len[cur]+2; 499 start[N-1]=idx-len[N-1]+1; 500 if(len[N-1]==1){ 501 link[N-1]=diff[N-1]=slink[N-1]=1; 502 cur=N-1; 503 return; 504 } 505 while(true){ 506 cur=link[cur]; 507 if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]) 508 break; 509 } 510 link[N-1]=next[cur][s[idx]]; 511 diff[N-1]=len[N-1]-len[link[N-1]]; 512 if(diff[N-1]==diff[link[N-1]]) 513 slink[N-1]=slink[link[N-1]]; 514 else 515 slink[N-1]=link[N-1]; 516 cur=N-1; 517 } 518 }; 519 ll dp[MAXN],sans[MAXN]; 520 int main() 521 { 522 std::ios::sync_with_stdio(false); 523 cin.tie(0); 524 cout.tie(0); 525 PalindromicTree pt; 526 int i,cur; 527 string str; 528 cin>>str; 529 for(i=0;i<sz(str)/2;i++){ 530 s.pb(str[i]); 531 s.pb(str[sz(str)-i-1]); 532 } 533 dp[0]=1; 534 for(i=1;i<=sz(s);i++){ 535 pt.add_letter(i-1); 536 for(cur=pt.cur;cur>1;cur=pt.slink[cur]){ 537 sans[cur]=dp[i-pt.len[pt.slink[cur]]-pt.diff[cur]]; 538 if(pt.diff[cur]==pt.diff[pt.link[cur]]) 539 sans[cur]=(sans[cur]+sans[pt.link[cur]])%hell; 540 dp[i]=(dp[i]+sans[cur])%hell; 541 } 542 if(i&1) 543 dp[i]=0; 544 } 545 cout<<dp[sz(s)]; 546 return 0; 547 } 548 ``` 549 550 **Code 2** 551 552 ``` 553 #define NDEBUG 554 NDEBUG 555 556 #include <algorithm> 557 #include <array> 558 #include <bitset> 559 #include <cassert> 560 #include <cstring> 561 #include <cmath> 562 #include <functional> 563 #include <iomanip> 564 #include <iostream> 565 #include <map> 566 #include <set> 567 #include <sstream> 568 #include <string> 569 #include <tuple> 570 #include <unordered_map> 571 #include <unordered_set> 572 #include <vector> 573 #include <memory> 574 #include <queue> 575 #include <random> 576 577 #define forn(t, i, n) for (t i = 0; i < (n); ++i) 578 579 using namespace std; 580 581 // TC_REMOVE_BEGIN 582 /// caide keep 583 bool __hack = std::ios::sync_with_stdio(false); 584 /// caide keep 585 auto __hack1 = cin.tie(nullptr); 586 // TC_REMOVE_END 587 588 // Section with adoption of array and vector algorithms. 589 590 #define ENABLE_IF(e) typename enable_if<e>::type* = nullptr 591 592 namespace template_util { 593 594 595 constexpr int bytecount(uint64_t x) { 596 return x ? 1 + bytecount(x >> 8) : 0; 597 } 598 599 template<int N> 600 struct bytetype { 601 602 }; 603 604 template<> 605 struct bytetype<4> { 606 typedef uint32_t type; 607 }; 608 609 610 template<> 611 struct bytetype<1> { 612 typedef uint8_t type; 613 }; 614 615 616 /// caide keep 617 template<uint64_t N> 618 struct minimal_uint : bytetype<bytecount(N)> { 619 }; 620 } 621 622 template<class T> 623 T next(istream& in) { 624 T ret; 625 in >> ret; 626 return ret; 627 } 628 629 /* 630 TODOs: 631 primitive root 632 discrete log 633 634 tests!!! 635 */ 636 637 namespace mod_impl { 638 /// caide keep 639 template <class T> 640 constexpr inline T mod(T MOD) { 641 return MOD; 642 } 643 644 /// caide keep 645 template <class T> 646 constexpr inline T mod(T* MOD) { 647 return *MOD; 648 } 649 650 /// caide keep 651 template <class T> 652 constexpr inline T max_mod(T MOD) { 653 return MOD - 1; 654 } 655 656 /// caide keep 657 template <class T> 658 constexpr inline T max_mod(T*) { 659 return numeric_limits<T>::max() - 1; 660 } 661 662 663 constexpr inline uint64_t combine_max_sum(uint64_t a, uint64_t b) { 664 return a > ~b ? 0 : a + b; 665 } 666 667 668 /// caide keep 669 template <class T> 670 constexpr inline uint64_t next_divisible(T mod, uint64_t max) { 671 return max % mod == 0 ? max : combine_max_sum(max, mod - max % mod); 672 } 673 674 /// caide keep 675 template <class T> 676 constexpr inline uint64_t next_divisible(T*, uint64_t) { 677 return 0; 678 } 679 680 //caide keep 681 constexpr int IF_THRESHOLD = 2; 682 683 template <class T, T MOD_VALUE, uint64_t MAX, 684 class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type, 685 ENABLE_IF(MAX <= max_mod(MOD_VALUE) && !is_pointer<T>::value)> 686 inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) { 687 return value; 688 } 689 690 template <class T, T MOD_VALUE, uint64_t MAX, 691 class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type, 692 ENABLE_IF(max_mod(MOD_VALUE) < MAX && MAX <= IF_THRESHOLD * max_mod(MOD_VALUE) && !is_pointer<T>::value)> 693 inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) { 694 while (value >= mod(MOD_VALUE)) { 695 value -= mod(MOD_VALUE); 696 } 697 return (RET)value; 698 } 699 700 701 } 702 703 #define MAX_MOD mod_impl::max_mod(MOD_VALUE) 704 705 struct DenormTag {}; 706 707 template <class T, T MOD_VALUE, uint64_t MAX = MAX_MOD, ENABLE_IF(MAX_MOD >= 2)> 708 struct ModVal { 709 typedef typename template_util::minimal_uint<MAX>::type storage; 710 storage value; 711 712 /// caide keep 713 inline ModVal(): value(0) { 714 assert(MOD >= 2); 715 } 716 717 718 inline ModVal(storage v, DenormTag): value(v) { 719 assert(MOD >= 2); 720 assert(v <= MAX); 721 }; 722 723 inline operator ModVal<T, MOD_VALUE>() { 724 return {v(), DenormTag()}; 725 }; 726 727 728 typename template_util::minimal_uint<mod_impl::max_mod(MOD_VALUE)>::type v() const { 729 return mod_impl::smart_mod<T, MOD_VALUE, MAX>(value); 730 } 731 }; 732 733 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2, 734 uint64_t NEW_MAX = mod_impl::combine_max_sum(MAX1, MAX2), 735 ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>> 736 inline Ret operator+(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) { 737 return {typename Ret::storage(typename Ret::storage() + o1.value + o2.value), DenormTag()}; 738 } 739 740 template <class T, T MOD_VALUE, uint64_t MAX> 741 inline ModVal<T, MOD_VALUE>& operator+=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) { 742 lhs = lhs + rhs; 743 return lhs; 744 } 745 746 template <class T, T MOD_VALUE, class MOD_TYPE> 747 struct ModCompanion { 748 typedef MOD_TYPE mod_type; 749 typedef ModVal<mod_type, MOD_VALUE> type; 750 751 752 template <uint64_t C> 753 inline static constexpr ModVal<mod_type, MOD_VALUE, C> c() { 754 return {C, DenormTag()}; 755 }; 756 757 758 }; 759 760 #undef MAX_MOD 761 762 template <uint64_t MOD_VALUE> 763 struct Mod : ModCompanion<uint64_t, MOD_VALUE, typename template_util::minimal_uint<MOD_VALUE>::type> { 764 template<uint64_t VAL> 765 static constexpr uint64_t literal_builder() { 766 return VAL; 767 } 768 769 template<uint64_t VAL, char DIGIT, char... REST> 770 static constexpr uint64_t literal_builder() { 771 return literal_builder<(10 * VAL + DIGIT - '0') % MOD_VALUE, REST...>(); 772 } 773 }; 774 775 #define REGISTER_MOD_LITERAL(mod, suffix) \ 776 template <char... DIGITS> mod::type operator "" _##suffix() { \ 777 return mod::c<mod::literal_builder<0, DIGITS...>()>(); \ 778 } 779 780 template <class T, T MOD_VALUE, uint64_t MAX> 781 inline ostream& operator<<(ostream& s, ModVal<T, MOD_VALUE, MAX> val) { 782 s << val.v(); 783 return s; 784 } 785 786 using md = Mod<1000000007>; 787 using mt = md::type; 788 REGISTER_MOD_LITERAL(md, mod) 789 790 struct Triple { 791 int start, delta, count; 792 793 int end() { 794 return start + delta * (count - 1); 795 } 796 }; 797 798 // ostream& operator<<(ostream& out, const Triple& t) { 799 // out << "(" << t.start << ", " << t.delta << ", " << t.count << ")"; 800 // return out; 801 // } 802 803 void solve(istream& in, ostream& out) { 804 auto s = next<string>(in); 805 string s1; 806 s1.reserve(2 * s.length()); 807 forn (int, i, s.length() / 2) { 808 s1.push_back(s[i]); 809 s1.push_back(s[s.length() - i - 1]); 810 } 811 int n = s1.length(); 812 vector<Triple> g; 813 vector<mt> d(n + 1), cache(n + 1); 814 d[0] = 1_mod; 815 forn (int, i, n) { 816 vector<Triple> g1; 817 int prev = -i - 1; 818 auto push = [&](Triple t) { 819 if (g1.empty() || t.delta != g1.back().delta) { 820 g1.push_back(t); 821 } else { 822 g1.back().count += t.count; 823 } 824 }; 825 for (auto t : g) { 826 if (t.start > 0 && s1[t.start - 1] == s1[i]) { 827 t.start--; 828 if (prev != t.start - t.delta) { 829 push(Triple{t.start, t.start - prev, 1}); 830 t.start += t.delta; 831 t.count--; 832 } 833 if (t.count > 0) { 834 push(t); 835 } 836 prev = t.end(); 837 } 838 } 839 if (i >= 1 && s1[i - 1] == s1[i]) { 840 push(Triple{i - 1, i - 1 - prev, 1}); 841 } 842 g = move(g1); 843 for (auto& t : g) { 844 mt add = d[t.end()]; 845 if (t.count > 1) { 846 add += cache[t.start - t.delta]; 847 } 848 if (t.start - t.delta >= 0) { 849 cache[t.start - t.delta] = add; 850 } 851 d[i + 1] += add; 852 } 853 } 854 out << d[n] << endl; 855 } 856 857 int main() { 858 solve(cin, cout); 859 return 0; 860 } 861 ```