結果
問題 | No.2243 Coaching Schedule |
ユーザー |
![]() |
提出日時 | 2023-01-22 12:34:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 406 ms / 4,000 ms |
コード長 | 2,184 bytes |
コンパイル時間 | 4,751 ms |
コンパイル使用メモリ | 262,116 KB |
最終ジャッジ日時 | 2025-02-10 06:21:22 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,n) for (int i = 0; i < int(n); ++i)using namespace std;using namespace atcoder;void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);}using mint = modint998244353;template<typename T>struct Binom{Binom(int lim = 300000){ extend(lim); }static T fact(int x) {if (x < 0) return T(0);extend(x);return kaijo[x];}static T ifact(int x){if (x < 0) return T(0);extend(x);return kainv[x];}static T C(int n, int r){if (n < 0 || n < r || r < 0) return T(0);extend(n);return kaijo[n] * kainv[r] * kainv[n-r];}static T P(int n, int r){if (n < 0 || n < r || r < 0) return T(0);extend(n);return kaijo[n] * kainv[n-r];}private:static std::vector<T> kaijo, kainv;static void extend(int lim){int siz = kaijo.size();if (siz > lim) return ;int nsiz = siz * 2;kaijo.resize(nsiz+1), kainv.resize(nsiz+1);for (int i = siz; i <= nsiz; i++) kaijo[i] = kaijo[i-1] * T(i);kainv[nsiz] = kaijo[nsiz].inv();for (int i = nsiz-1; i >= siz; i--) kainv[i] = kainv[i+1] * T(i+1);extend(lim);}};template<typename T>std::vector<T>Binom<T>::kaijo = vector<T>(2,T(1));template<typename T>std::vector<T>Binom<T>::kainv = vector<T>(2,T(1));int main(){fast_io();int m, n; cin >> m >> n;vector<int> cnt(m,0);rep(i,n){int a; cin >> a;cnt[a-1]++;}vector<int> a(n+1,0);rep(i,m) a[cnt[i]]++;vector<pair<int,int>> b;rep(i,n+1) if (i > 0 && a[i] > 0) b.emplace_back(i,a[i]);Binom<mint> bnm;vector<mint> g(n+1,1);rep(k,n+1){for (auto p : b){g[k] *= (bnm.P(k,p.first)).pow(p.second);}}vector<mint> xs(n+1,0), ys(n+1,0);rep(i,n+1){xs[i] = bnm.ifact(i) * (i % 2 == 0 ? 1 : -1);ys[i] = g[i] * bnm.ifact(i);}vector<mint> xy = convolution(xs,ys);mint ans = 0;rep(i,n+1) ans += xy[i] * bnm.fact(i);cout << ans.val() << endl;}