1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| #include <cstdio> using namespace std; template <class Type> void read (Type &x) { char c; bool flag = false; while ((c = getchar()) < '0' || c > '9') flag |= c == '-'; x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0'; if (flag) x = ~x + 1; } template <class Type, class ...Rest> void read (Type &x, Rest &...y) { read(x); read(y...); } template <class Type> void write (Type x) { if (x < 0) putchar('-'), x = ~x + 1; if (x > 9) write(x / 10); putchar('0' + x % 10); } typedef long long LL; const int N = 1e6 + 10, mod = 998244353; int binpow (int b, LL k) { k = (k % (mod - 1) + mod - 1) % (mod - 1); int res = 1; for (; k; k >>= 1, b = (LL)b * b % mod) if (k & 1) res = (LL)res * b % mod; return res; } int n; int inv[N], fact[N], ifact[N]; void init () { inv[1] = 1; for (int i = 2; i < N; ++i) inv[i] = -(LL)(mod / i) * inv[mod % i] % mod; fact[0] = ifact[0] = 1; for (int i = 1; i < N; ++i) { fact[i] = (LL)fact[i - 1] * i % mod; ifact[i] = (LL)ifact[i - 1] * inv[i] % mod; } } int C (int a, int b) { return a < b ? 0 : (LL)fact[a] * ifact[b] % mod * ifact[a - b] % mod; } int main () { init(); read(n); int res = 0; for (int i = 1; i <= n ;++i) res = (res - C(n, i) * (i & 1 ? -1ll : 1ll) * binpow(3, -(LL)i * n) % mod * (binpow(1 - binpow(3, i - n), n) - 1)) % mod; write((((LL)res * binpow(3, (LL)n * n + 1) - 2ll * binpow(3, (LL)n * n) * (binpow(1 - binpow(3, 1 - n), n) - 1)) % mod + mod) % mod); return 0; }
|
Gitalk 加载中 ...