codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```