fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define endl '\n'
  5. const int mod = 1e9+7;
  6. #define yes cout << "Yes" << endl;
  7. #define no cout << "No" << endl;
  8.  
  9. int binpow(int a, int b)
  10. {
  11.   int res = 1;
  12.   a = a % mod;
  13.   while (b != 0)
  14.   {
  15.     if (b & 1)
  16.     {
  17.       res = (res * a) % mod;
  18.     }
  19.     a = (a * a) % mod;
  20.     b = b >> 1;
  21.   }
  22.   return res;
  23. }
  24.  
  25. int n,m,k;
  26.  
  27. vector<int> a;
  28. vector<vector<int>> g;
  29. vector<vector<int>> gg;
  30.  
  31. int dp[10001][101][10];
  32.  
  33. int rec(int level,int mat,int k){
  34.   if(level==n){
  35.     return 1;
  36.   }
  37.  // cout<<level<<endl;
  38.   if(dp[level][mat][k]!=-1){
  39.     return dp[level][mat][k];
  40.   }
  41.  
  42.   int ans = 0;
  43.  
  44.   for(auto v : gg[k]){
  45.     int mm = g[mat][v];
  46.     if(mm!=m){
  47.       ans = (ans + rec(level+1,mm,v))%mod;
  48.     }
  49.   }
  50.  
  51.   dp[level][mat][k] = ans;
  52.   return ans;
  53. }
  54.  
  55. void solve()
  56. {
  57.   cin>>n>>m>>k;
  58.   string s;
  59.   cin>>s;
  60.   memset(dp,-1,sizeof(dp));
  61.   if(m==0){cout<<0<<endl; return;}
  62.   gg.resize(10);
  63.  
  64.   gg[0] = {4,6};
  65.   gg[1] = {6,8};
  66.   gg[2] = {7,9};
  67.   gg[3] = {8,4};
  68.   gg[4] = {3,9,0};
  69.   gg[6] = {1,7,0};
  70.   gg[7] = {2,6};
  71.   gg[8] = {1,3};
  72.   gg[9] = {4,2};
  73.  
  74.     g.assign(m + 1, vector<int>(10, 0));
  75.     for (int i = 0; i <= m; i++){
  76.         for (int j = 0; j < 10; j++){
  77.             string t = "";
  78.             for (int k = 0; k < i; k++) t += s[k];
  79.             t += (char)('0' + j);
  80.  
  81.             for (int len = 1; len <= (int)t.size(); len++){
  82.                 bool good = true;
  83.                 int start = (int)t.size() - len;
  84.                 for (int k = 0; k < len; k++) if (t[start + k] != s[k]) good = false;
  85.  
  86.                 if (good) g[i][j] = len;
  87.             }
  88.           //  cout<<i<<" "<<j<<" "<<g[i][j]<<endl;
  89.         }
  90.     } 
  91.  
  92.   //cout<<g[0][3]<<endl;
  93.   cout<<rec(0,0,k)<<endl;
  94.   return;
  95. }
  96.  
  97. signed main()
  98. {
  99.   ios::sync_with_stdio(false);
  100.   cout.tie(0);
  101.   cin.tie(0);
  102.   int t = 1;
  103.   // cin >> t;
  104.   while (t-- != 0)
  105.   {
  106.     //   cout<<t<<endl;
  107.     solve();
  108.   }
  109.   return 0;
  110. }
Success #stdin #stdout 0.02s 82424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/z4Gun0
language:
C++14 (gcc 8.3)
created:
4 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!