fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. # define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. # define cases cin >> tests; while(tests--)
  6. # define int long long
  7. # define ch cout << "no rest for the wicked\n\n";
  8. # define ch1(x) cout << '\n' << #x" : " << x << '\n';
  9. # define ch2(x, y) cout << '\n' <<  #x" : " << x << " || " << #y" : " << y << '\n';
  10. # define lcm(a, b) (((a) * (b))/__gcd(a, b))
  11. # define fore(i, n) for(auto i = 0; i < n; i++)
  12.  
  13. int powa(int x, int y, int p)
  14. {
  15.     int res = 1;      // Initialize result
  16.  
  17.     while (y > 0)
  18.     {
  19.         // If y is odd, multiply x with result
  20.         if (y & 1)
  21.             res = ((res % p) * (x % p)) % p;
  22.  
  23.         // y must be even now
  24.         y = y>>1; // y = y/2
  25.         x = ((x % p) * (x % p)) % p;
  26.     }
  27.     return res % p;
  28. }
  29.  
  30. void solve()
  31. {
  32.     int n, a, b, k;
  33.     cin >> n >> a >> b >> k;
  34.     string str;
  35.     cin >> str;
  36.     int ans = 0;
  37.     int jj = 1000000009;
  38.     for(int i = 0; i < min(k, n+1); i++)
  39.     {
  40.         // ch1(str[i])
  41.         if(str[i] == '+')
  42.         {
  43.             ans += ((powa(a, n-i, jj) % jj) * (powa(b, i, jj) % jj));
  44.         }
  45.         else
  46.         {
  47.             ans -= ((powa(a, n-i, jj) % jj) * (powa(b, i, jj) % jj));
  48.         }
  49.     }
  50.     // cout << ans << endl;
  51.     if(k == n+1)
  52.     {
  53.         int num = ans;
  54.         while(num < 0)
  55.         {
  56.             num += 1000000009;
  57.         }
  58.         cout << num % 1000000009;
  59.         return;
  60.     }
  61.     // ans += (((ans * pow(b, k)) / pow(a, k)) * ((n+1) / k));
  62.     int rat = powa(b, k, jj) / powa(a, k, jj);
  63.     int series = n+1;
  64.     series /= k;
  65.     ans = ((((ans % jj) * ((powa(rat, series, jj))%jj) % jj) - 1) / (rat - 1));
  66.     // cout << ans % (1000000009);
  67.     // cout << ans - (ans / 1000000009);
  68.     int num = ans;
  69.     while(num < 0)
  70.     {
  71.         num += 1000000009;
  72.     }
  73.     cout << num % 1000000009;
  74. }
  75.  
  76. signed main()
  77. {
  78.     fast;
  79.     int tests = 1;
  80.  
  81.     // cases
  82.     solve();
  83.  
  84.     return 0;
  85. }
Runtime error #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NqOR5J
language:
C++14 (gcc 8.3)
created:
6 years 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!