結果

問題 No.3450 Permutation of Even Scores
コンテスト
ユーザー こめだわら
提出日時 2026-02-21 00:04:57
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 427 ms / 2,000 ms
コード長 4,373 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,073 ms
コンパイル使用メモリ 387,860 KB
実行使用メモリ 13,108 KB
最終ジャッジ日時 2026-02-21 00:05:21
合計ジャッジ時間 23,811 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define rep(i,n) for(ll i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    if (a.empty()) return os;
    os << a.front();
    for (auto e : a | views::drop(1)){
        os << ' ' << e;
    }
    return os;
}

void dump(auto ...vs){
    ((cout << vs << ' '), ...) << endl;
}

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;

struct factorial{
    factorial(int MAX = 0){
        _fact_n.resize(1,1);
        _fact_i.resize(1,1);
        if (MAX>0){
            extend(MAX);
        }
    }
    void extend(ll n){
        int l=(int)_fact_n.size();
        if (l-1<n){
            int nn=(n/4096+1)*4096;
            for (int i=l;i<nn+1;i++){
                _fact_n.push_back(_fact_n.at(i-1)*i);
                _fact_i.push_back(0);
            }
            _fact_i.at(nn)=_fact_n.at(nn).inv();
            for (int i=nn;i>l;i--){
                _fact_i.at(i-1)=_fact_i.at(i)*i;
            }
        }
    }

    mint fact(ll n){
        assert (n>=0);
        if (n>(int)_fact_n.size()-1){
            extend(n);
        }
        return _fact_n.at(n);
    }

    mint fact_inv(ll n){
        assert (n>=0);
        if (n>(int)_fact_n.size()-1){
            extend(n);
        }
        return _fact_i.at(n);
    }

    mint perm(ll n,ll r){
        if (r<0){
            return 0;
        }
        if (n>=0){
            if (n<r){
                return 0;
            }
            return fact(n)*fact_inv(n-r);
        }
        else{
            mint ret=fact(-n+r-1)*fact_inv(-n-1);
            if (r%2==1){
                ret=-ret;
            }
            return ret;
        }
    }

    mint comb(ll n,ll r){
        if (r<0){
            return 0;
        }
        if (n>=0){
            if (n<r){
                return 0;
            }
            return fact(n)*fact_inv(n-r)*fact_inv(r);
        }
        else{
            mint ret=fact(-n+r-1)*fact_inv(-n-1)*fact_inv(r);
            if (r%2==1){
                ret=-ret;
            }
            return ret;
        }
    }
  private:
    vector<mint> _fact_n;
    vector<mint> _fact_i;
};
factorial f;



void solve() {
    ll N,M;
    cin>>N>>M;
    vector<bool> A(N,false);
    rep(i,M){
        ll a;
        cin>>a;
        a--;
        A[a]=true;
    }
    vector<mint> dp(N,0);
    dp[0]=1;
    vector<mint> F(N);
    rep(i,N){
        if (i==0)continue;
        F[i]=f.fact(i+1)*(-2);
    }
    auto calc=[&](auto self,ll left,ll right)->void {
        if (right-left==1){
            return;
        }
        ll mid=(left+right)/2;
        self(self,left,mid);
        vector<mint> leftres(mid-left);
        rep(i,mid-left){
            leftres[i]=dp[left+i];
        }
        vector<mint> resf(right-left);
        rep(i,right-left){
            resf[i]=F[i];
        }
        vector<mint> res=convolution(leftres,resf);
        rep(i,right-mid){
            if (A[mid+i]){
                dp[mid+i]+=res[mid-left+i];
            }
        }
        self(self,mid,right);
    };
    calc(calc,0,N);
    // for (ll i=1;i<N;i++){
    //     if (!A[i])continue;
    //     for (ll j=1;j<=i;j++){
    //         dp[i]+=dp[i-j]*F[j];
    //     }
    // }
    mint ans=f.fact(N);
    rep(i,N){
        ans+=dp[i]*f.fact(N-i);
        // if (dp[i].val()!=0){
        //     dump(i,dp[i].val());
        // }
        // dump(ans.val());
    }
    ans/=2;
    if (A[0]){
        ans=f.fact(N)-ans;
    }
    cout<<ans.val()<<'\n';
    return;
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T=1;
    while (T--){
        solve();
    }
    return 0;
}
0