fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6.  
  7. void fio() {
  8.     ios_base::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.     cout.tie(nullptr);
  11. }
  12.  
  13. const int mod = 1000000007;
  14.  
  15. ll mul(ll a, ll b) {
  16.     return (((a % mod) * (b % mod)) % mod);
  17. }
  18.  
  19. ll fast_power(ll base, ll exponent) {
  20.     if (exponent == 0) return 1;
  21.  
  22.     ll half_power = fast_power(base, exponent / 2);
  23.     ll full_power = mul(half_power, half_power);
  24.  
  25.     if (exponent % 2 != 0) {
  26.         full_power = mul(full_power, base);
  27.     }
  28.     return full_power;
  29. }
  30.  
  31. ll mod_inverse(ll b) {
  32.     return fast_power(b, mod - 2);
  33. }
  34.  
  35. ll add(ll a, ll b) {
  36.     return (((a % mod) + (b % mod)) % mod);
  37. }
  38.  
  39. int main() {
  40.     fio();
  41.     string a;
  42.     cin >> a;
  43.  
  44.     int k;
  45.     cin >> k;
  46.  
  47.     int n = a.length();
  48.     ll ans = 0;
  49.  
  50.     for (int i = 0; i < n; i++) {
  51.         if (a[i] == '0' || a[i] == '5') {
  52.             ll ways = fast_power(2, i);
  53.  
  54.             if (k == 1) {
  55.                 ans = add(ans, ways);
  56.             } else {
  57.                 ll numerator = mul(ways, fast_power(2, (k-1) * n));
  58.                 ll sum_series = 0;
  59.  
  60.                 // (1 + 2^n + 2^2n + ... + 2^((k-1)n))
  61.                 ll geo_sum = (fast_power(2, k * n) - 1 + mod) % mod;
  62.                 ll divisor = (fast_power(2, n) - 1 + mod) % mod;
  63.                 sum_series = mul(geo_sum, mod_inverse(divisor));
  64.  
  65.                 ans = add(ans, mul(ways, sum_series));
  66.             }
  67.         }
  68.     }
  69.  
  70.     cout << ans << endl;
  71.     return 0;
  72. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/5kYS4Y
language:
C++ (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!