結果
| 問題 | No.3450 Permutation of Even Scores |
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2026-05-12 03:24:19 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 852 ms / 2,000 ms |
| コード長 | 7,146 bytes |
| 記録 | |
| コンパイル時間 | 3,786 ms |
| コンパイル使用メモリ | 346,192 KB |
| 実行使用メモリ | 11,300 KB |
| 最終ジャッジ日時 | 2026-05-12 03:24:47 |
| 合計ジャッジ時間 | 26,719 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / tmp-judge_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 46 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back
template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
_() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;
constexpr int mod = 998244353;
struct mint {
int x;
mint(ll x_ = 0) : x(x_ % mod) {
if(x < 0) x += mod;
}
mint operator-() {
auto res = *this;
res.x = (x ? mod - x : 0);
return res;
}
mint& operator+=(mint r) {
if((x += r.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(mint r) {
if((x -= r.x) < 0) x += mod;
return *this;
}
mint& operator*=(mint r) {
x = 1LL * x * r.x % mod;
return *this;
}
mint& operator/=(mint r) { return *this *= r.inv(); }
friend mint operator+(mint a, mint b) { return a += b; }
friend mint operator-(mint a, mint b) { return a -= b; }
friend mint operator*(mint a, mint b) { return a *= b; }
friend mint operator/(mint a, mint b) { return a /= b; }
mint inv() const { return pow(mod - 2); }
mint pow(ll b) const {
mint a = *this, c = 1;
while(b) {
if(b & 1) c *= a;
a *= a;
b >>= 1;
}
return c;
}
};
using vm = vector<mint>;
mint g = 3; // 原始根
void fft(vm& a, bool inv = false) {
int n = sz(a), s = __lg(n);
static vm z, iz;
while(sz(z) <= s) {
z.eb(g.pow(mint(-1).x / (1 << sz(z))));
iz.eb(z.back().inv());
}
vm b(n);
rep(i, 1, s + 1) {
int w = 1 << s - i;
mint base = inv ? iz[i] : z[i], now = 1;
for(int y = 0; y < n / 2; y += w) {
rep(x, w) {
auto l = a[y << 1 | x], r = now * a[y << 1 | x | w];
b[y | x] = l + r, b[y | x | n >> 1] = l - r;
}
now *= base;
}
swap(a, b);
}
}
vm mul(vm a, vm b) {
int n = sz(a), m = sz(b);
if(!n or !m) return {};
if(min(n, m) <= 30) {
vm ans(n + m - 1);
rep(i, n) rep(j, m) ans[i + j] += a[i] * b[j];
return ans;
}
int N = n + m - 1;
int z = bit_ceil(unsigned(N));
a.resize(z), b.resize(z);
fft(a), fft(b);
rep(i, z) a[i] *= b[i];
fft(a, true);
a.resize(n + m - 1);
mint iz = mint(z).inv();
fore(e, a) e *= iz;
return a;
}
struct relaxed_multiplication {
vector<mint> f, g, h;
// fg_prefix_ntts[d] = (NTTs of first 2^d terms of f and g)
vector<pair<vector<mint>, vector<mint>>> fg_prefix_ntts;
const auto& get_fg_prefix_ntt(int d) {
while(int(fg_prefix_ntts.size()) <= d) {
int fftlen = 1 << fg_prefix_ntts.size();
vector<mint> vf(f.begin(), f.begin() + fftlen);
vector<mint> vg(g.begin(), g.begin() + fftlen);
fft(vf, false), fft(vg, false);
fg_prefix_ntts.emplace_back(vf, vg);
}
return fg_prefix_ntts[d];
}
relaxed_multiplication() {}
mint add(const mint& f_i, const mint& g_i) {
f.push_back(f_i), g.push_back(g_i);
const int n = f.size(), d = __builtin_ctz(n), D = 1 << d;
if(int gsz = n - 1 + D; h.size() < gsz) h.resize(gsz);
if(n == D) {
// Convolve f[0, D) * g[0, D) -> h[D - 1, D * 2 - 1)
const auto& [nttf, nttg] = get_fg_prefix_ntt(d);
vector<mint> tmp(nttf.size());
for(int i = 0; i < nttf.size(); ++i) tmp[i] = nttf[i] * nttg[i];
fft(tmp, true);
for(int i = 0; i < n - 1; ++i) h[n + i] += tmp[i] - h[i]; // 回り込みを削除
h[n - 1] += tmp[n - 1];
} else {
// Convolve f[0, 2 * D) * g[n - D, n) -> h[n - 1, n - 1 + D)
if(d <= 4) { // Bruteforce threshold
for(int i = n - D; i < n; ++i) {
for(int k = n - 1; k < n - 1 + D; ++k) { h[k] += f[i] * g[k - i] + f[k - i] * g[i]; }
}
} else {
vector<mint> tmpf{f.end() - D, f.end()}, tmpg{g.end() - D, g.end()};
tmpf.resize(D * 2), tmpg.resize(D * 2);
fft(tmpf, false), fft(tmpg, false);
const auto& [nttf, nttg] = get_fg_prefix_ntt(d + 1);
for(int i = 0; i < tmpf.size(); ++i) { tmpf[i] = tmpf[i] * nttg[i] + tmpg[i] * nttf[i]; }
fft(tmpf, true);
for(int i = 0; i < D; ++i) h[n - 1 + i] += tmpf[D - 1 + i];
}
}
return h[n - 1];
}
};
struct RelaxedConvolution {
mint push(const mint &x, const mint &y) {
++n;
f.emplace_back(x), g.emplace_back(y);
same &= (x.x == y.x);
for(int p = 1;; p <<= 1) {
int l1 = n - p, r1 = n, l2 = p - 1, r2 = l2 + p;
if(same) {
add(l1, r1, l2, r2, (l1 == l2 ? 1 : 2));
if(l1 == l2) break;
} else {
add(l1, r1, l2, r2);
if(l1 == l2) break;
add(l2, r2, l1, r1);
}
if(!(n & p)) break;
}
return h[n - 1];
}
const mint &operator[](int i) const { return h[i]; }
vector<mint> res() const { return h; }
private:
bool same = true;
int n = 0;
vector<mint> f, g, h;
void add(int l1, int r1, int l2, int r2, int coef = 1) {
auto k = mul(vector(f.begin() + l1, f.begin() + r1), vector(g.begin() + l2, g.begin() + r2));
int st = l1 + l2;
if((st + k.size()) > h.size()) h.resize(r1 + r2 - 1);
for(int i = 0; i < k.size(); i++) { h[st + i] += (coef == 1 ? k[i] : k[i] * coef); }
}
};
void solve() {
int n, m;cin >> n >> m;
vi f(n + 1, 0);
rep(m) {
int x;cin >> x;
f[x] = 1;
}
RelaxedConvolution rc;
vm fact(n + 2, 1);
rep(i, n + 1) fact[i+1] = fact[i] * (i + 1);
vm b(n + 1, 0);
b[0] = -4;
rep(i, n) b[i+1] = b[i] * (i + 3);
vm dp(n + 1, 0);
rc.push(dp[0], b[0]);
rep(i, 1, n + 1) {
if (f[i]) {
dp[i] = rc[i-1] + fact[i] * (-2);
}
else {
dp[i] = 0;
}
rc.push(dp[i], b[i]);
}
mint ans = fact[n];
mint inv2 = mint(2).inv();
rep(i, n + 1) ans += dp[i] * fact[n + 1 - i] * inv2;
// rep(i, n + 1) {
// cerr << (dp[i]).x << " ";
// }
// cerr << endl;
cout << ans.x << endl;
}
int main() {
// test();
// int T;cin >> T;
int T = 1;
while (T--) {
solve();
}
}