結果
問題 | No.3123 Inversion |
ユーザー |
|
提出日時 | 2025-03-19 03:46:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,473 bytes |
コンパイル時間 | 3,689 ms |
コンパイル使用メモリ | 191,448 KB |
実行使用メモリ | 394,160 KB |
最終ジャッジ日時 | 2025-04-18 00:19:27 |
合計ジャッジ時間 | 124,598 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 1 |
other | WA * 3 RE * 18 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define ll long long const ll MAX_N = 10000000, mod = 998244353; ll dp1[MAX_N + 10], dp2[MAX_N + 10]; ll c2[MAX_N + 10]; ll pow2[MAX_N + 10]; //2^N ll fact[MAX_N + 10]; //N! void solve(){ pow2[0] = 1; fact[0] = 1; for(ll N = 1; N <= MAX_N; N++) { // 2^N pow2[N] = 2 * pow2[N - 1] % mod; // N! fact[N] = N * fact[N - 1] % mod; // dp1 if(N == 1) dp1[N] = 2; else if(N == 2) dp1[N] = 6; else dp1[N] = 2 * (dp1[N - 1] + (N - 1) * dp1[N - 2] % mod) % mod; // dp2 if(N == 1) dp2[N] = 1; else if(N == 2) dp2[N] = 2; else dp2[N] = (dp2[N - 1] + (N - 1) * dp2[N - 2] % mod) % mod; // c2 if(N == 1) c2[N] = 1; else if(N == 4) c2[N] = 2; else if(N % 4 == 0) c2[N] = (N - 2) * c2[N - 4] % mod; else if(N % 4 == 1) c2[N] = (N - 3) * c2[N - 4] % mod; else c2[N] = 0; } } int main(){ int T; cin >> T; solve(); while(T--){ int N; cin >> N; if(N == 1){ cout << 1 << "\n"; continue; } ll c3 = dp1[N / 2]; ll c4 = (pow2[N / 2] * fact[N / 2] % mod - c2[N] - c3 + mod * 2) % mod; ll c5 = (dp2[N] - c3 + mod) % mod; ll c6 = c5; ll c7 = (fact[N] - c2[N] - c3 - c4 - c5 - c6 + mod * 5) % mod; cout << (2 * (c2[N] + c3) + 4 * (c4 + c5 * 2) + 8 * c7) % mod << "\n"; } }