cosenza987

Untitled

Nov 3rd, 2025
699
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e6 + 7, mod = 998244353;
  6.  
  7. long long binexp(long long a, long long n) {
  8.     long long res = 1;
  9.     while(n) {
  10.         if(n & 1) {
  11.             res = (res * a) % mod;
  12.         }
  13.         n >>= 1;
  14.         a = (a * a) % mod;
  15.     }
  16.     return res;
  17. }
  18.  
  19. namespace ntt {
  20.     long long w[N], k, nrev;
  21.     inline void init(int n, int root) {
  22.         w[0] = 1;
  23.         k = binexp(root, (mod - 1) / n);
  24.         nrev = binexp(n, mod - 2);
  25.         for(int i = 1; i <= n; i++) {
  26.             w[i] = (w[i - 1] * k) % mod;
  27.         }
  28.     }
  29.     inline void ntt(vector<long long> &a, int n, bool inv = false) {
  30.         a.resize(n);
  31.         for(int i = 0, j = 0; i < n; i++) {
  32.             if(i > j) swap(a[i], a[j]);
  33.             for(int l = n / 2; (j ^= l) < l; l >>= 1);
  34.         }
  35.         for(int i = 2; i <= n; i <<= 1) {
  36.             for(int j = 0; j < n; j += i) {
  37.                 for(int l = 0; l < i / 2; l++) {
  38.                     int x = j + l, y = j + l + (i / 2), z = (n / i) * l;
  39.                     long long tmp = (a[y] * w[(inv ? (n - z) : z)]) % mod;
  40.                     a[y] = (a[x] - tmp + mod) % mod;
  41.                     a[x] = (a[j + l] + tmp) % mod;
  42.                 }
  43.             }
  44.         }
  45.         if(inv) {
  46.             for(int i = 0; i < n; i++) {
  47.                 a[i] = (a[i] * nrev) % mod;
  48.             }
  49.         }
  50.     }
  51.     void multiply(vector<long long> &a, vector<long long> b, int root = 3) {
  52.         int n = (int)a.size() + (int)b.size() - 1;
  53.         while(n & (n - 1)) n++;
  54.         a.resize(n);
  55.         b.resize(n);
  56.         init(n, root);
  57.         ntt(a, n);
  58.         ntt(b, n);
  59.         for(int i = 0; i < n; i++) {
  60.             a[i] = (a[i] * b[i]) % mod;
  61.         }
  62.         ntt(b, n, true);
  63.         ntt(a, n, true);
  64.         while(a.back() == 0) a.pop_back();
  65.     }
  66. }
  67.  
  68. int main() {
  69.     ios_base::sync_with_stdio(false);
  70.     cin.tie(nullptr);
  71.     int n, m, s;
  72.     cin >> n >> m >> s;
  73.     // auto start = chrono::high_resolution_clock::now();
  74.     vector<long long> v(m + 1, 1), ans(1, 1);
  75.     while(n) {
  76.         if(n & 1) {
  77.             ntt::multiply(ans, v);
  78.             if(ans.size() > s + 1) ans.resize(s + 1);
  79.         }
  80.         ntt::multiply(v, v);
  81.         if(v.size() > s + 1) v.resize(s + 1);
  82.         n >>= 1;
  83.     }
  84.     ans.resize(s + 1);
  85.     cout << ans[s] << "\n";
  86.     // auto stop = chrono::high_resolution_clock::now();
  87.     // cerr << chrono::duration_cast<chrono::milliseconds>(stop - start).count() << "\n";
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment