fork download
copy 
  1. ///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii; 
  7.  
  8. const int N = 1 << 20, M = N * 2; 
  9. const int mod = 998244353, g = 3;
  10.  
  11. int fact[N], inv[N]; 
  12.  
  13. inline int Pow(int a, int p) {
  14.     int ret = 1; while(p) {
  15.         if(p & 1) ret = (ll) ret * a % mod;
  16.         a = (ll) a * a % mod;
  17.         p >>= 1;
  18.     } return ret;
  19. }
  20.  
  21. inline void precalc() {
  22.     fact[0] = 1; 
  23.     for(int i = 1; i < N; ++i) {
  24.         fact[i] = (ll) fact[i - 1] * i % mod; 
  25.     }
  26.     inv[N - 1] = Pow(fact[N - 1], mod - 2); 
  27.     for(int i = N - 2; i >= 0; --i) {
  28.         inv[i] = (ll) inv[i + 1] * (i + 1) % mod; 
  29.     }
  30. }
  31.  
  32. int rev[M], w[M], inv_n;
  33.  
  34. inline void prepare(int &n) { 
  35.     int sz = 31 - __builtin_clz(n); sz = abs(sz);
  36.     int r = Pow(g, (mod - 1) / n); 
  37.     inv_n = Pow(n, mod - 2);
  38.     w[0] = w[n] = 1; 
  39.     for(int i = 1; i < n; ++i) w[i] = (ll)w[i - 1] * r % mod;
  40.     for(int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
  41. }
  42.  
  43. inline void ntt(int *a, int n, int dir = 0) { 
  44.     for(int i = 1; i < n - 1; ++i) 
  45.         if(i < rev[i]) swap(a[i], a[rev[i]]);
  46.     for(int m = 2; m <= n; m <<= 1) {
  47.         for(int i = 0; i < n; i += m) {
  48.             for(int j = 0; j < (m >> 1); ++j) {
  49.                 int &u = a[i + j], &v = a[i + j + (m >> 1)]; 
  50.                 int t = (ll)v * w[dir ? n - n / m * j : n / m * j] % mod;
  51.                 v = u - t < 0 ? u - t + mod : u - t;
  52.                 u = u + t >= mod ? u + t - mod : u + t;
  53.             }
  54.         }
  55.     } if(dir) for(int i = 0; i < n; ++i) a[i] = (ll)a[i] * inv_n % mod;
  56. }
  57.  
  58. int f[M], a[M], b[M]; 
  59.  
  60. inline void build(int n) {
  61.     if(n == 1) {
  62.         return void(f[1] = 1); 
  63.     }
  64.     if(n & 1) {
  65.         build(n - 1); 
  66.         for(int i = n; i >= 1; --i) {
  67.             f[i] = f[i - 1] - (ll) (n - 1) * f[i] % mod;
  68.             if(f[i] < 0) f[i] += mod; 
  69.         }
  70.         f[0] = -(ll) f[0] * (n - 1) % mod; 
  71.         if(f[0] < 0) f[0] += mod; 
  72.         return; 
  73.     }
  74.  
  75.     n >>= 1; 
  76.     build(n);
  77.  
  78.     int t = n + n + 1, sz = 1; 
  79.     while(sz < t) sz <<= 1; 
  80.     prepare(sz); 
  81.  
  82.     for(int i = 0; i <= n; ++i) {
  83.         a[i] = (ll) f[n - i] * fact[n - i] % mod; 
  84.     }
  85.  
  86.     int mul = (mod - n % mod) % mod; 
  87.     for(int i = 0, p = 1; i <= n; ++i) {
  88.         b[i] = (ll) p * inv[i] % mod; 
  89.         p = (ll) p * mul % mod;
  90.     }
  91.  
  92.     for(int i = n + 1; i < sz; i++) a[i] = b[i] = 0; 
  93.  
  94.     ntt(a, sz), ntt(b, sz); 
  95.     for(int i = 0; i < sz; ++i)
  96.         a[i] = (ll) a[i] * b[i] % mod;
  97.     ntt(a, sz, 1); 
  98.  
  99.     reverse(a, a + n + 1); 
  100.     for(int i = 0; i <= n; ++i)
  101.         a[i] = (ll) a[i] * inv[i] % mod; 
  102.     for(int i = n + 1; i < sz; i++) a[i] = f[i] = 0; 
  103.  
  104.     ntt(a, sz), ntt(f, sz); 
  105.     for(int i = 0; i < sz; ++i) 
  106.         f[i] = (ll) f[i] * a[i] % mod;
  107.     ntt(f, sz, 1);
  108. }
  109.  
  110. int main(int argc, char const *argv[]) {
  111.     precalc(); 
  112.     int t; scanf("%d", &t); while(t--) {
  113.         int n, p, r; 
  114.         scanf("%d %d %d", &n, &p, &r); 
  115.  
  116.         build(r);
  117.  
  118.         for(int i = 0; i <= r; ++i) {
  119.             f[i] = (ll) f[i] * inv[r] % mod;
  120.         }
  121.  
  122.         int ans = 0, mul;
  123.         for(int i = 1, q = p; i <= r; ++i, q = (ll) q * p % mod) {
  124.             if(q == 1) {
  125.                 mul = (n + 1) % mod; 
  126.             } else {
  127.                 mul = (ll) (Pow(q, n + 1) - 1) * Pow(q - 1, mod - 2) % mod; 
  128.                 if(mul < 0) mul += mod; 
  129.             }
  130.             ans += (ll) f[i] * mul % mod;
  131.             if(ans >= mod) ans -= mod; 
  132.         }
  133.  
  134.         printf("%d\n", ans);
  135.     }
  136. }
Success #stdin #stdout 0.04s 12676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/2k06jB
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!