fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. #define endl '\n'
  6. #define all(v) (v).begin(), (v).end()
  7. #define len(v) (int)(v).size()
  8. #define loop(i, l, r)                                                          \
  9.   for (int(i) = (l); (r) > (l) ? (i) < (r) : (i) > (r);                        \
  10.        (r) > (l) ? (i)++ : (i)--)
  11. #define SuperSonic ios::sync_with_stdio(false), cin.tie(nullptr)
  12.  
  13. const int MOD = 1e9 + 7;
  14.  
  15. ll add(ll a, ll b) { return (a % MOD + b % MOD) % MOD; }
  16.  
  17. ll mult(ll a, ll b) { return (a % MOD * b % MOD) % MOD; }
  18.  
  19. ll sub(ll a, ll b) { return (a % MOD - b % MOD + MOD) % MOD; }
  20.  
  21. ll fp(ll base, ll power) {
  22.   if (power == 0)
  23.     return 1;
  24.  
  25.   ll hp = fp(base, power / 2);
  26.   ll fullPower = mult(hp, hp);
  27.  
  28.   if (power % 2 != 0)
  29.     fullPower = mult(fullPower, base);
  30.  
  31.   return fullPower;
  32. }
  33.  
  34. ll divi(ll a, ll b) { return mult(a, fp(b, MOD - 2)); }
  35.  
  36. void solve() {
  37.   ll n, k;
  38.   cin >> n >> k;
  39.  
  40.   string s;
  41.   cin >> s;
  42.  
  43.   vector<int> zf;
  44.   ll ans{}, series = divi(sub(fp(2, k * n), 1), sub(fp(2, n), 1)), ZFCurBlock{},
  45.             ZFNextBlock{};
  46.   loop(i, 0, n) {
  47.     if (s[i] == '0' || s[i] == '5') {
  48.       ans = add(ans, mult(fp(2, i), series));
  49.       zf.push_back(i);
  50.       ZFCurBlock = add(ZFCurBlock, fp(2, i));
  51.     }
  52.   }
  53.  
  54.   ll kSeries = divi(sub(mult(series, fp(2, n)), k), sub(fp(2, n), 1)),
  55.      prevKSeries = sub(kSeries, series);
  56.   for (int i : zf) {
  57.     ZFCurBlock = sub(ZFCurBlock, fp(2, i));
  58.     ZFNextBlock = add(ZFNextBlock, fp(2, i + n));
  59.  
  60.     if (s[i] == '0') {
  61.       ans = sub(ans, mult(kSeries, divi(ZFCurBlock, fp(2, i + 1))));
  62.       ans = sub(ans, mult(prevKSeries, divi(ZFNextBlock, fp(2, i + 1))));
  63.     }
  64.   }
  65.  
  66.   cout << ans;
  67. }
  68.  
  69. int main() {
  70.   SuperSonic;
  71.  
  72.   int t = 1;
  73.   // cin >> t;
  74.   while (t--) {
  75.     solve();
  76.   }
  77. }
  78.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eqpfeH
language:
C++14 (gcc 8.3)
created:
13 hours 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!