fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename T>
  5. void out(T x) { cout << x << endl; exit(0); }
  6. #define watch(x) cout << (#x) << " is " << (x) << endl
  7.  
  8.  
  9.  
  10.  
  11.  
  12. using ll = long long;
  13. const ll mod = 1e9+7;
  14. const int maxn = 1e5 + 5;
  15.  
  16.  
  17. using matrix = vector<vector<ll>>;
  18.  
  19. void add(ll& x, ll y) {
  20.     if (x>=mod) x%=mod;
  21.     if (y>=mod) y%=mod;
  22.     x += y;
  23.     if (x>=mod) x%=mod;
  24. }
  25.  
  26. void mul(ll& x, ll y) {
  27.     if (x>=mod) x%=mod;
  28.     if (y>=mod) y%=mod;
  29.     long long tmp = 1ll*x*y;
  30.     tmp %= mod;
  31.     x = tmp;
  32. }
  33.  
  34. ll addr(ll x, ll y) {
  35.     if (x>=mod) x%=mod;
  36.     if (y>=mod) y%=mod;
  37.     x += y;
  38.     if (x>=mod) x%=mod;
  39.     return x;
  40. }
  41.  
  42. ll mulr(ll x, ll y) {
  43.     if (x>=mod) x%=mod;
  44.     if (y>=mod) y%=mod;
  45.     long long tmp = 1ll*x*y;
  46.     tmp %= mod;
  47.     return tmp;
  48. }
  49.  
  50.  
  51.  
  52. matrix mul(matrix a, matrix b) {
  53.     int n = a.size();
  54.     assert(n>0);
  55.     int m = a[0].size();
  56.     assert(m == int(b.size()));
  57.     int p = b[0].size();
  58.     matrix res(n, vector<ll>(p));
  59.     for (int i=0; i<n; i++) {
  60. 	for (int j=0; j<p; j++) {
  61. 	    for (int k=0; k<m; k++) {
  62. 		ll cur = mulr(a[i][k], b[k][j]);
  63. 		add(res[i][j], cur);
  64. 	    }
  65. 	}
  66.     }
  67.     return res;    
  68. }
  69.  
  70.  
  71. matrix matpw(matrix mat, int k) {
  72.     int n = mat.size();
  73.     assert(mat.size() && mat.size()==mat[0].size()); //nxn
  74.     matrix res(n,vector<ll>(n));
  75.     for (int i=0; i<n; i++) {
  76. 	res[i][i]=1;
  77.     }
  78.  
  79.  
  80.     while (k>0) {
  81. 	if (k%2) {
  82. 	    res=mul(res,mat);
  83. 	}
  84. 	mat=mul(mat,mat);
  85. 	k=k/2;
  86.     }
  87.  
  88.     return res;
  89. }
  90.  
  91.  
  92. matrix id2() {
  93.     vector<vector<ll>> mat(2,vector<ll>(2));
  94.     mat[0][0]=mat[1][1]=1;
  95.     return mat;
  96. }
  97.  
  98. matrix matA() {
  99.     vector<vector<ll>> mat(2,vector<ll>(2,1));
  100.     mat[1][0]=0;
  101.     // 1 1
  102.     // 0 1
  103.     return mat;
  104. }
  105.  
  106. matrix matB() {
  107.     vector<vector<ll>> mat(2,vector<ll>(2,1));
  108.     mat[0][1]=0;
  109.     // 1 0
  110.     // 1 1
  111.     return mat;
  112. }
  113.  
  114.  
  115. int n, q;
  116. string s;
  117.  
  118. using node = matrix;
  119.  
  120. node t[4*maxn];
  121. bool o[4*maxn];
  122.  
  123. node merge(node a, node b) {
  124.     return mul(b, a);
  125. }
  126.  
  127. void build(int v, int tl, int tr) {
  128.     if (tl==tr) {
  129. 	t[v] = s[tl] == 'A' ? matA() : matB();
  130.     } else {
  131. 	int tm=(tl+tr)/2;
  132. 	build(2*v,tl,tm);
  133. 	build(2*v+1,tm+1,tr);
  134. 	t[v] = merge(t[2*v], t[2*v+1]);
  135.     }
  136. }
  137.  
  138. void push(int v) {
  139.     if (!o[v]) return;
  140.  
  141.     swap(t[2*v][0], t[2*v][1]);
  142.     swap(t[2*v][0][0], t[2*v][0][1]);
  143.     swap(t[2*v][1][0], t[2*v][1][1]);
  144.  
  145.     swap(t[2*v+1][0], t[2*v+1][1]);
  146.     swap(t[2*v+1][0][0], t[2*v+1][0][1]);
  147.     swap(t[2*v+1][1][0], t[2*v+1][1][1]);
  148.     o[2*v]=!o[2*v];
  149.     o[2*v+1]=!o[2*v+1];
  150.     o[v]=false;
  151. }
  152.  
  153.  
  154. void flip(int v, int tl, int tr, int l, int  r) {
  155.     if (r<tl || l>tr) {
  156. 	return;
  157.     }
  158.     if (l<=tl && tr<=r) {
  159. 	// before
  160. 	// p q
  161. 	// r s
  162.  
  163. 	// after
  164. 	// s r
  165. 	// q p
  166.  
  167. 	swap(t[v][0], t[v][1]);
  168. 	swap(t[v][0][0], t[v][0][1]);
  169. 	swap(t[v][1][0], t[v][1][1]);
  170. 	o[v] = !o[v];
  171. 	return;
  172.     }
  173.     int tm=(tl+tr)/2;
  174.     push(v);
  175.     flip(2*v,tl,tm,l,r);
  176.     flip(2*v+1,tm+1,tr,l,r);
  177.     t[v]=merge(t[2*v],t[2*v+1]);
  178. }
  179.  
  180. matrix qry(int v, int tl, int tr, int l, int r) {
  181.     if (l>tr || r<tl) {
  182. 	return id2();
  183.     }
  184.     if (l<=tl && tr<=r) {
  185. 	return t[v];
  186.     }
  187.     int tm=(tl+tr)/2;
  188.     push(v);
  189.     return mul(qry(2*v+1,tm+1,tr,l,r), qry(2*v,tl,tm,l,r));
  190. }
  191.  
  192.  
  193.  
  194.  
  195. int main() {
  196.     ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  197.  
  198.     cin>>n>>q;
  199.     cin>>s;
  200.     s="."+s;
  201.     build(1,1,n);
  202.  
  203.     while (q--) {
  204. 	int typ;
  205. 	cin>>typ;
  206. 	if (typ==2) {
  207. 	    int l,r; ll a,b;
  208. 	    cin>>l>>r>>a>>b;
  209. 	    matrix M = qry(1,1,n,l,r);
  210. 	    ll resa = addr(mulr(M[0][0],a), mulr(M[0][1],b));
  211. 	    ll resb = addr(mulr(M[1][0],a), mulr(M[1][1],b));
  212. 	    cout<<resa<<" "<<resb<<"\n";
  213. 	}
  214. 	if (typ==1) {
  215. 	    int l,r;
  216. 	    cin>>l>>r;
  217. 	    flip(1,1,n,l,r);
  218. 	}
  219.     }
  220.  
  221.  
  222.     return 0;
  223. }
Internal error #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4rcI8i
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!