fork download
copy 
  1. // modified from submission 5652 (Author : Min)
  2.  
  3. #include <stdio.h>
  4. #include <string.h>
  5. #define maxd 10000000
  6. #define mod 1000000007
  7. typedef long long ll;
  8.  
  9. void swap(int *a, int *b)
  10. {
  11.     if ((*a) != (*b))
  12.         (*a) ^= (*b), (*b) ^= (*a), (*a) ^= (*b);
  13. }
  14. __attribute__((target("avx2"), optimize("O3")))
  15. int _inv(int a)
  16. {
  17.     int _a = a, _b = mod, u = 1, v = 0;
  18.     while (_b)
  19.     {
  20.         int t = _a / _b;
  21.         _a -= t * _b;
  22.         swap(&_a, &_b);
  23.         u -= t * v;
  24.         swap(&u, &v);
  25.     }
  26.     u += mod, u %= mod;
  27.     return u;
  28. }
  29.  
  30. int quick_pow(int x, ll p)
  31. {
  32.     ll ans = 1;
  33.     while (p)
  34.     {
  35.         if (p & 1)
  36.             ans = ans * x % mod;
  37.         x = 1ll * x * x % mod;
  38.         p >>= 1;
  39.     }
  40.     return ans;
  41. }
  42.  
  43. int inv[maxd + 10], cur_max_d;
  44. int s1[maxd + 10], s2[maxd + 10];
  45.  
  46. void init_all() { inv[1] = 1, cur_max_d = 1; }
  47. __attribute__((target("avx2"), optimize("O3")))
  48. void init_inv(int d)
  49. {
  50.     if (cur_max_d < d)
  51.         for (int i = cur_max_d + 1; i <= d + 1; ++i)
  52.             inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
  53.     cur_max_d = d;
  54. }
  55. void init_case_1(int d) { memset(s1, 0, sizeof(s1[0]) * (d + 1)); }
  56. void init_case_2(int d) { memset(s1, 0, sizeof(s1[0]) * (d + 1)), memset(s2, 0, sizeof(s2[0]) * (d + 1)); }
  57. // \sum_{i=0}^{n-1} {(r^i)*(i^d)}
  58. __attribute__((target("avx2"), optimize("O3")))
  59. int sum_of_exp_time_poly(int r, int d, char *n)
  60. {
  61.     init_inv(d);
  62.     int ans = 0;
  63.     int len = strlen(n);
  64.     ll mod_n = 0, pow_n = 0;
  65.         for (int i = 0; i < len; ++i)
  66.         {
  67.             mod_n = (mod_n << 1) + (mod_n << 3) + (n[i] ^ '0');
  68.             pow_n = (pow_n << 1) + (pow_n << 3) + (n[i] ^ '0');
  69.             // mod_n %= mod, pow_n %= (mod - 1);
  70.             mod_n = (mod_n >= mod) ? mod_n % mod : mod_n;
  71.             pow_n = (pow_n >= (mod - 1)) ? pow_n % (mod - 1) : pow_n;
  72.         }
  73.  
  74.     if (r == 1)
  75.     {
  76.         // vector<int> s1(d + 1);
  77.         init_case_1(d);
  78.         for (int i = 0, t = 0, b = 1; i <= d; ++i)
  79.         {
  80.             b = 1ll * b * (mod_n + mod - i) % mod * inv[i + 1] % mod;
  81.             t = (t + quick_pow(i, d)) % mod;
  82.             s1[i] = 1ll * t * b % mod;
  83.         }
  84.         for (int i = 0, b = 1; i <= d; ++i)
  85.         {
  86.             ans = (ans + 1ll * b * ((i & 1) ? mod - s1[d - i] : s1[d - i])) % mod;
  87.             b = 1ll * b * (mod_n + mod - 1 - (d - i)) % mod * inv[i + 1] % mod;
  88.         }
  89.     }
  90.     else
  91.     {
  92.         // vector<int> s1(d + 1), s2(d + 1);
  93.         init_case_2(d);
  94.         int t1 = 0, t2 = 0;
  95.         for (int i = 0, rpow = 1; i <= d; ++i, rpow = 1ll * rpow * r % mod)
  96.         {
  97.             s1[i] = t1 = (t1 + 1ll * quick_pow(i, d) * rpow) % mod;
  98.             s2[i] = t2 = (t2 + 1ll * quick_pow(i + mod_n, d) * rpow) % mod;
  99.         }
  100.         int ans1 = 0, ans2 = 0, b = 1, mr = mod - r;
  101.         for (int i = 0; i <= d; ++i)
  102.         {
  103.             ans1 = (ans1 + 1ll * b * s1[d - i]) % mod;
  104.             ans2 = (ans2 + 1ll * b * s2[d - i]) % mod;
  105.             b = 1ll * b * mr % mod * (d + 1 - i) % mod * inv[i + 1] % mod;
  106.         }
  107.         ans = ans1 + mod - 1ll * quick_pow(r, pow_n) * ans2 % mod;
  108.         ans = 1ll * ans * _inv(quick_pow(mod + 1 - r, d + 1)) % mod;
  109.     }
  110.     return ans;
  111. }
  112. int r, d;
  113. char n[100010];
  114. __attribute__((target("avx2"), optimize("O3")))
  115. int main()
  116. {
  117.     init_all();
  118.     while (~scanf("%d%d%s", &r, &d, n))
  119.         printf("%d\n", sum_of_exp_time_poly(r, d, n));
  120. }
Success #stdin #stdout 0.01s 5752KB
comments (?)
stdin
copy 
1 2 999998132
1 1 999998132
1 0 999998132
stdout
copy 
800976271
1758750
999998132
https://ideone.com/5Y9bZ1
language:
C++14 (gcc 8.3)
created:
2 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!