fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <vector>
  4. #define maxd 10000000
  5. using namespace std;
  6. const int mod = 998244353;
  7. typedef long long ll;
  8. ll rd()
  9. {
  10.     ll k = 0;
  11.     char c = getchar();
  12.     while (c < '0' || c > '9')
  13.         c = getchar();
  14.     while (c >= '0' && c <= '9')
  15.     {
  16.         k = (k << 1) + (k << 3) + (c ^ 48);
  17.         c = getchar();
  18.     }
  19.     return k;
  20. }
  21. void wr(ll x)
  22. {
  23.     if (x > 9)
  24.         wr(x / 10);
  25.     putchar(x % 10 + '0');
  26. }
  27. void swap(int *a, int *b)
  28. {
  29.     if ((*a) != (*b))
  30.         (*a) ^= (*b), (*b) ^= (*a), (*a) ^= (*b);
  31. }
  32.  
  33. int _inv(int a)
  34. {
  35.     int _a = a, _b = mod, u = 1, v = 0;
  36.     while (_b)
  37.     {
  38.         int t = _a / _b;
  39.         _a -= t * _b;
  40.         swap(&_a, &_b);
  41.         u -= t * v;
  42.         swap(&u, &v);
  43.     }
  44.     u += mod, u %= mod;
  45.     return u;
  46. }
  47.  
  48. int quick_pow(int x, ll p)
  49. {
  50.     ll ans = 1;
  51.     while (p)
  52.     {
  53.         if (p & 1)
  54.             ans = ans * x % mod;
  55.         x = 1ll * x * x % mod;
  56.         p >>= 1;
  57.     }
  58.     return ans;
  59. }
  60.  
  61. int inv[maxd + 10], cur_max_d;
  62. int s1[maxd + 10], s2[maxd + 10];
  63.  
  64. void init_all() { inv[1] = 1, cur_max_d = 1; }
  65. void init_inv(int d)
  66. {
  67.     if (cur_max_d < d)
  68.         for (int i = cur_max_d + 1; i <= d + 1; ++i)
  69.             inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
  70.     cur_max_d = d;
  71. }
  72. void init_case_1(int d) { memset(s1, 0, sizeof(s1[0]) * (d + 1)); }
  73. void init_case_2(int d) { memset(s1, 0, sizeof(s1[0]) * (d + 1)), memset(s2, 0, sizeof(s2[0]) * (d + 1)); }
  74. void debug_print_status(int d)
  75. {
  76.     puts("current s : ");
  77.     for (int i = 0; i <= d; ++i)
  78.         wr(s1[i]), putchar(i == d ? '\n' : ' ');
  79. }
  80. // \sum_{i=0}^{n-1} {(r^i)*(i^d)}
  81. int sum_of_exp_time_poly(int r, int d, char *n)
  82. {
  83.     init_inv(d);
  84.     int ans = 0;
  85.     int len = strlen(n);
  86.     ll mod_n = 0, pow_n = 0;
  87.     if (len < 20)
  88.     {
  89.         for (int i = 0; i < len; ++i)
  90.             mod_n = (mod_n << 1) + (mod_n << 3) + (n[i] ^ '0');
  91.         pow_n = mod_n % (mod - 1), mod_n %= mod;
  92.     }
  93.     else
  94.     {
  95.         for (int i = 0; i < len; ++i)
  96.         {
  97.             mod_n = (mod_n << 1) + (mod_n << 3) + (n[i] ^ '0');
  98.             pow_n = (pow_n << 1) + (pow_n << 3) + (n[i] ^ '0');
  99.             mod_n = (mod_n >= mod) ? mod_n % mod : mod_n;
  100.             pow_n = (pow_n >= (mod - 1)) ? pow_n % (mod - 1) : pow_n;
  101.         }
  102.     }
  103.     if (r == 1)
  104.     {
  105.         /*
  106.         init_case_1(d);
  107.         for (int i = 0, t = 0, b = 1; i <= d; ++i)
  108.         {
  109.             b = 1ll * b * (mod_n + mod - i) % mod * inv[i + 1] % mod;
  110.             t = (t + quick_pow(i, d)) % mod;
  111.             s1[i] = 1ll * t * b % mod;
  112.         }
  113.         debug_print_status(d);
  114.         for (int i = 0, b = 1; i <= d; ++i)
  115.         {
  116.             ans = (ans + 1ll * b * ((i & 1) ? mod - s1[d - i] : s1[d - i])) % mod;
  117.             b = 1ll * b * (mod_n + mod - 1 - (d - i)) % mod * inv[i + 1] % mod;
  118.         }
  119.         */
  120.         vector<int> s(d + 1);
  121.         for (int i = 0, t = 0, b = 1; i <= d; ++i)
  122.         {
  123.             b = 1ll * b * (mod_n + mod - i) % mod * inv[i + 1] % mod;
  124.             t = (t + quick_pow(i, d)) % mod;
  125.             s[i] = 1ll * t * b % mod;
  126.         }
  127.         for (int i = 0, b = 1; i <= d; ++i)
  128.         {
  129.             ans = (ans + 1ll * b * ((i & 1) ? mod - s[d - i] : s[d - i])) % mod;
  130.             b = 1ll * b * (mod_n + mod - 1 - (d - i)) % mod * inv[i + 1] % mod;
  131.         }
  132.     }
  133.     else
  134.     {
  135.         init_case_2(d);
  136.         int t1 = 0, t2 = 0;
  137.         for (int i = 0, rpow = 1; i <= d; ++i, rpow = 1ll * rpow * r % mod)
  138.         {
  139.             s1[i] = t1 = (t1 + 1ll * quick_pow(i, d) * rpow) % mod;
  140.             s2[i] = t2 = (t2 + 1ll * quick_pow(i + mod_n, d) * rpow) % mod;
  141.         }
  142.         int ans1 = 0, ans2 = 0, b = 1, mr = mod - r;
  143.         for (int i = 0; i <= d; ++i)
  144.         {
  145.             ans1 = (ans1 + 1ll * b * s1[d - i]) % mod;
  146.             ans2 = (ans2 + 1ll * b * s2[d - i]) % mod;
  147.             b = 1ll * b * mr % mod * (d + 1 - i) % mod * inv[i + 1] % mod;
  148.         }
  149.         ans = ans1 + mod - 1ll * quick_pow(r, pow_n) * ans2 % mod;
  150.         ans = 1ll * ans * _inv(quick_pow(mod + 1 - r, d + 1)) % mod;
  151.     }
  152.     return ans;
  153. }
  154. int sum_of_exp_time_poly_limit(int r, int d)
  155. {
  156.     init_inv(d);
  157.     init_case_1(d);
  158.     int t = 0;
  159.     for (int i = 0; i <= d; ++i)
  160.         t = (t + 1ll * quick_pow(i, d) * quick_pow(r, i)) % mod, s1[i] = t;
  161.  
  162.     int ans = 0, b = 1, mr = mod - r;
  163.     for (int i = 0; i <= d; ++i)
  164.     {
  165.         ans = (ans + 1ll * b * s1[d - i]) % mod;
  166.         b = 1ll * b * mr % mod * (d + 1 - i) % mod * inv[i + 1] % mod;
  167.     }
  168.     ans = 1ll * ans * _inv(quick_pow(mod + 1 - r, d + 1)) % mod;
  169.     return ans;
  170. }
  171. int r, d;
  172. char n[100010];
  173. int main()
  174. {
  175.     init_all();
  176.     // while (~scanf("%d%d", &r, &d))
  177.         // printf("%d\n", sum_of_exp_time_poly_limit(r, d));
  178.     while (~scanf("%d%d%s", &r, &d, n))
  179.         printf("%d\n", sum_of_exp_time_poly(r, d, n));
  180. }
  181.  
Success #stdin #stdout 0s 5472KB
comments (?)
stdin
copy 
1 1 999998132
1 2 999998132
1 0 999998132
stdout
copy 
0
162643807
1753779
https://ideone.com/rmgf01
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!