fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1000000007;
  5.  
  6. long long modpow(long long a, long long e){
  7.     long long r = 1;
  8.     while(e){
  9.         if(e&1) r = (r*a)%MOD;
  10.         a = (a*a)%MOD;
  11.         e >>= 1;
  12.     }
  13.     return r;
  14. }
  15.  
  16. static int dp2[2005][2005];
  17. static int dp3[105][105][105];
  18.  
  19. int main(){
  20.     ios::sync_with_stdio(false);
  21.     cin.tie(nullptr);
  22.     int N, k;
  23.     if(!(cin >> N >> k)) return 0;
  24.     string S;
  25.     cin >> S;
  26.     if(k==1){
  27.         cout << modpow(2, N) % MOD;
  28.         return 0;
  29.     }
  30.     if(k==2){
  31.         for(int i=1;i<=N;i++){
  32.             for(int j=1;j<=N;j++){
  33.                 if(S[i-1]==S[j-1]){
  34.                     long long v = dp2[i-1][j] + dp2[i][j-1];
  35.                     v %= MOD;
  36.                     v = (v + 1) % MOD;
  37.                     dp2[i][j] = (int)v;
  38.                 }else{
  39.                     long long v = dp2[i-1][j] + dp2[i][j-1];
  40.                     v %= MOD;
  41.                     v = (v - dp2[i-1][j-1]) % MOD;
  42.                     if(v<0) v += MOD;
  43.                     dp2[i][j] = (int)v;
  44.                 }
  45.             }
  46.         }
  47.         int ans = dp2[N][N];
  48.         ans++;
  49.         if(ans>=MOD) ans-=MOD;
  50.         cout << ans;
  51.         return 0;
  52.     }
  53.     for(int i=1;i<=N;i++){
  54.         for(int j=1;j<=N;j++){
  55.             for(int k3=1;k3<=N;k3++){
  56.                 long long v = dp3[i-1][j][k3];
  57.                 v += dp3[i][j-1][k3];
  58.                 if(v>=MOD) v-=MOD;
  59.                 v += dp3[i][j][k3-1];
  60.                 v %= MOD;
  61.                 v -= dp3[i-1][j-1][k3];
  62.                 if(v<0) v+=MOD;
  63.                 v -= dp3[i-1][j][k3-1];
  64.                 if(v<0) v+=MOD;
  65.                 v -= dp3[i][j-1][k3-1];
  66.                 if(v<0) v+=MOD;
  67.                 v += dp3[i-1][j-1][k3-1];
  68.                 v %= MOD;
  69.                 if(S[i-1]==S[j-1] && S[i-1]==S[k3-1]){
  70.                     v += 1 + dp3[i-1][j-1][k3-1];
  71.                     v %= MOD;
  72.                 }
  73.                 dp3[i][j][k3] = (int)v;
  74.             }
  75.         }
  76.     }
  77.     int ans = dp3[N][N][N];
  78.     ans++;
  79.     if(ans>=MOD) ans-=MOD;
  80.     cout << ans;
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5260KB
comments (?)
stdin
copy 
12 3
whysoserious
stdout
copy 
8656
https://ideone.com/CRFDqq
language:
C++14 (gcc 8.3)
created:
14 days 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!