fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 200005
  7. #define fi first
  8. #define se second
  9. #define i18 __int128_t
  10.  
  11.  
  12. using namespace std;
  13.  
  14. ll c[maxn],n,k;
  15.  
  16. struct matrix {
  17.     ll m,n;
  18.     vector<vector<ll>> mt;
  19.     matrix(int _m=0,int _n=0){
  20.         m=_m; n=_n;
  21.         mt.assign(m,vector<ll>(n,0));
  22.     }
  23.     matrix operator * (const matrix& other) const{
  24.         int x=m,y=n,z=other.n;
  25.        matrix ans(x,z);
  26.        for(int i=0;i<x;i++){
  27.           for(int k=0;k<y;k++){
  28.             if(mt[i][k]==0) continue;
  29.             for(int j=0;j<z;j++){
  30.                ans.mt[i][j]=(ans.mt[i][j]+mt[i][k]*other.mt[k][j])%3;
  31.             }
  32.           }
  33.        }
  34.        return ans;
  35.     }
  36. };
  37.  
  38. matrix power(matrix base, ll exp) {
  39.     matrix res(base.m, base.m);
  40.     for (int i = 0; i < base.m; i++) res.mt[i][i] = 1;
  41.     while (exp) {
  42.         if (exp & 1) res = res * base;
  43.         base = base * base;
  44.         exp >>= 1;
  45.     }
  46.     return res;
  47. }
  48.  
  49. int main()
  50. {
  51.     itachi
  52.     cin>>n>>k;
  53.     for(int i=0;i<n;i++) {
  54.         char x; cin>>x;
  55.         if(x=='R') c[i]=0;
  56.         else if(x=='G') c[i]=1;
  57.         else c[i]=2;
  58.     }
  59.     if(n*k<=1e6){
  60.         for(int i=0;i<k;i++){
  61.             for(int j=0;j<n;j++){
  62.                 int nxt=(j+1)%n;
  63.                 int val=(2*c[j]+2*c[nxt])%3;
  64.                 c[j]=val;
  65.                 c[nxt]=val;
  66.             }
  67.         }
  68.         for(int i=0;i<n;i++){
  69.             int x=c[i];
  70.             if(x==0) cout<<'R';
  71.             else if(x==1) cout<<'G';
  72.             else cout<<'B';
  73.         }
  74.         return 0;
  75.     }
  76.     matrix A=matrix(n,n);
  77.     for(int i=0;i<2;i++) for(int j=0;j<2;j++) A.mt[i][j]=2;
  78.     for(int i=2;i<n;i++) A.mt[i][i]=1;
  79.     matrix C=matrix(n,1);
  80.     for(int j=0;j<n;j++) C.mt[j][0]=c[j];
  81.     matrix B=matrix(n,n);
  82.     for(int i=1;i<n;i++) B.mt[i-1][i]=1;
  83.     B.mt[n-1][0]=1;
  84.     B=B*A;
  85.     B=power(B,n);
  86.     B=power(B,k);
  87.     C=B*C;
  88.     for(int i=0;i<n;i++){
  89.         int x=C.mt[i][0];
  90.         if(x==0) cout<<'R';
  91.         else if(x==1) cout<<'G';
  92.         else cout<<'B';
  93.     }
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U8ds8H
language:
C++14 (gcc 8.3)
created:
1 day 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!