Advertisement
kuroni

ICPC Vietnam National 2019 - H

Nov 12th, 2019
352
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define __lg(x) (x == 0 ? -1 : __lg(x))
  3. using namespace std;
  4.  
  5. const int MOD = 998244353, G = 3, LG = 23, MX = 1 << 21;
  6.  
  7. int n;
  8. long long rt[LG + 1];
  9.  
  10. long long pw(long long u, int p) {
  11.     long long ret = 1;
  12.     for (int i = __lg(p); i >= 0; i--) {
  13.         (ret *= ret) %= MOD;
  14.         if (p >> i & 1) {
  15.             (ret *= u) %= MOD;
  16.         }
  17.     }
  18.     return ret;
  19. }
  20.  
  21. int reverse_bit(int u) {
  22.     int ans = 0;
  23.     for (int i = 0; i < 21; i++) {
  24.         (ans <<= 1) ^= (u >> i & 1);
  25.     }
  26.     return ans;
  27. }
  28.  
  29. struct polynomial {
  30.     vector<long long> f;
  31.  
  32.     polynomial(int _sz = 0) {
  33.         f = vector<long long>(_sz, 0);
  34.     }
  35.  
  36.     polynomial ntt(bool inv = false) {
  37.         if (inv) {
  38.             reverse(f.begin() + 1, f.end());
  39.         }
  40.         polynomial ans(MX);
  41.         for (int i = 0; i < f.size(); i++) {
  42.             ans.f[reverse_bit(i)] = f[i];
  43.         }
  44.         for (int len = 1; len < MX; len += len) {
  45.             for (int i = 0; i < MX; i += 2 * len) {
  46.                 long long r = rt[__lg(len) + 1];
  47.                 long long w = 1;
  48.                 for (int j = 0; j < len; j++) {
  49.                     long long u = ans.f[i + j], v = ans.f[i + j + len];
  50.                     ans.f[i + j] = (u + w * v) % MOD;
  51.                     ans.f[i + j + len] = (u - w * v) % MOD;
  52.                     (w *= r) %= MOD;
  53.                 }
  54.             }
  55.         }
  56.         if (inv) {
  57.             reverse(f.begin() + 1, f.end());
  58.             long long iv = pw(MX, MOD - 2);
  59.             for (long long &v : ans.f) {
  60.                 (v *= iv) %= MOD;
  61.             }
  62.         }
  63.         return ans;
  64.     }
  65.  
  66.     polynomial operator*(const polynomial &oth) const {
  67.         polynomial ans(MX);
  68.         for (int i = 0; i < MX; i++) {
  69.             ans.f[i] = f[i] * oth.f[i] % MOD;
  70.         }
  71.         return ans;
  72.     }
  73. } bas, ini, row;
  74.  
  75. polynomial operator^(const polynomial &u, int p) {
  76.     polynomial ans = ini;
  77.     for (int i = __lg(p); i >= 0; i--) {
  78.         ans = ans * ans;
  79.         if (p >> i & 1) {
  80.             ans = ans * u;
  81.         }
  82.     }
  83.     return ans;
  84. }
  85.  
  86. void init() {
  87.     rt[LG] = pw(G, (MOD - 1) / (1 << LG));
  88.     for (int i = LG - 1; i >= 0; i--) {
  89.         rt[i] = rt[i + 1] * rt[i + 1] % MOD;
  90.     }
  91.     ini.f = {1};
  92.     for (int i = 0; i < 10; i++) {
  93.         bas.f.push_back(1);
  94.         row.f.push_back(i != 0);
  95.     }
  96.     bas = bas.ntt(); ini = ini.ntt(); row = row.ntt();
  97. }
  98.  
  99. int main() {
  100.     ios_base::sync_with_stdio(false);
  101.     cin.tie(nullptr);
  102.     cin >> n;
  103.     if (n == 1) {
  104.         return cout << 10, 0;
  105.     }
  106.     init();
  107.     polynomial ans = ((bas ^ (n - 1)) * row).ntt(true);
  108.     long long ret = 0;
  109.     for (long long &v : ans.f) {
  110.         (ret += v * v) %= MOD;
  111.     }
  112.     cout << (ret + MOD) % MOD;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement