Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define __lg(x) (x == 0 ? -1 : __lg(x))
- using namespace std;
- const int MOD = 998244353, G = 3, LG = 23, MX = 1 << 21;
- int n;
- long long rt[LG + 1];
- long long pw(long long u, int p) {
- long long ret = 1;
- for (int i = __lg(p); i >= 0; i--) {
- (ret *= ret) %= MOD;
- if (p >> i & 1) {
- (ret *= u) %= MOD;
- }
- }
- return ret;
- }
- int reverse_bit(int u) {
- int ans = 0;
- for (int i = 0; i < 21; i++) {
- (ans <<= 1) ^= (u >> i & 1);
- }
- return ans;
- }
- struct polynomial {
- vector<long long> f;
- polynomial(int _sz = 0) {
- f = vector<long long>(_sz, 0);
- }
- polynomial ntt(bool inv = false) {
- if (inv) {
- reverse(f.begin() + 1, f.end());
- }
- polynomial ans(MX);
- for (int i = 0; i < f.size(); i++) {
- ans.f[reverse_bit(i)] = f[i];
- }
- for (int len = 1; len < MX; len += len) {
- for (int i = 0; i < MX; i += 2 * len) {
- long long r = rt[__lg(len) + 1];
- long long w = 1;
- for (int j = 0; j < len; j++) {
- long long u = ans.f[i + j], v = ans.f[i + j + len];
- ans.f[i + j] = (u + w * v) % MOD;
- ans.f[i + j + len] = (u - w * v) % MOD;
- (w *= r) %= MOD;
- }
- }
- }
- if (inv) {
- reverse(f.begin() + 1, f.end());
- long long iv = pw(MX, MOD - 2);
- for (long long &v : ans.f) {
- (v *= iv) %= MOD;
- }
- }
- return ans;
- }
- polynomial operator*(const polynomial &oth) const {
- polynomial ans(MX);
- for (int i = 0; i < MX; i++) {
- ans.f[i] = f[i] * oth.f[i] % MOD;
- }
- return ans;
- }
- } bas, ini, row;
- polynomial operator^(const polynomial &u, int p) {
- polynomial ans = ini;
- for (int i = __lg(p); i >= 0; i--) {
- ans = ans * ans;
- if (p >> i & 1) {
- ans = ans * u;
- }
- }
- return ans;
- }
- void init() {
- rt[LG] = pw(G, (MOD - 1) / (1 << LG));
- for (int i = LG - 1; i >= 0; i--) {
- rt[i] = rt[i + 1] * rt[i + 1] % MOD;
- }
- ini.f = {1};
- for (int i = 0; i < 10; i++) {
- bas.f.push_back(1);
- row.f.push_back(i != 0);
- }
- bas = bas.ntt(); ini = ini.ntt(); row = row.ntt();
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- if (n == 1) {
- return cout << 10, 0;
- }
- init();
- polynomial ans = ((bas ^ (n - 1)) * row).ntt(true);
- long long ret = 0;
- for (long long &v : ans.f) {
- (ret += v * v) %= MOD;
- }
- cout << (ret + MOD) % MOD;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement