結果
問題 |
No.2975 単調増加部分積
|
ユーザー |
![]() |
提出日時 | 2024-11-29 23:13:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 10,000 ms |
コード長 | 3,824 bytes |
コンパイル時間 | 5,316 ms |
コンパイル使用メモリ | 271,780 KB |
最終ジャッジ日時 | 2025-02-26 09:29:17 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
/** author: shobonvip created: 2024.11.29 22:55:48 **/ #include<bits/stdc++.h> using namespace std; //* ATCODER #include<atcoder/all> using namespace atcoder; typedef dynamic_modint<0> mint; //*/ /* BOOST MULTIPRECISION #include<boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; //*/ typedef long long ll; #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template <typename T> T max(vector<T> &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]); return ret; } template <typename T> T min(vector<T> &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]); return ret; } template <typename T> T sum(vector<T> &a){ T ret = 0; for (int i=0; i<(int)a.size(); i++) ret += a[i]; return ret; } mint Garner(vector<long long> m,vector<long long> r){ int n = m.size(); vector<long long> t(n); for(int i=0; i<n; i++){ long long cur = 0LL; long long cm = 1LL; for(int j=0; j<i; j++){ cur += t[j] * cm; cur %= m[i]; cm *= m[j]; cm %= m[i]; } cur = r[i] - cur; cur %= m[i]; if(cur<0)cur += m[i]; if(i==1)cur *= 416537774; if(i==2)cur *= 429847628; //cur *= inv_mod(cm,m[i]); cur %= m[i]; t[i] = cur; } mint ret = 0; mint cm = 1; for(int i=0; i<n; i++){ ret += cm * t[i]; cm *= m[i]; } return ret; } template <class T> vector<T> convolution_mint(vector<T> a,vector<T> b){ static constexpr unsigned long long M0 = 998244353; static constexpr unsigned long long M1 = 754974721; static constexpr unsigned long long M2 = 469762049; vector<long long> aa(a.size()),bb(b.size()); for(int i=0; i<a.size(); i++)aa[i] = a[i].val(); for(int i=0; i<b.size(); i++)bb[i] = b[i].val(); auto c0 = convolution<M0>(aa,bb); auto c1 = convolution<M1>(aa,bb); auto c2 = convolution<M2>(aa,bb); vector<mint> ret(c0.size()); vector<long long> m = {M0,M1,M2}; for(int i=0; i<c0.size(); i++){ vector<long long> r = {c0[i],c1[i],c2[i]}; vector<long long> t(3); for(int j=0; j<3; j++){ long long cur = 0LL; long long cm = 1LL; for(int k=0; k<j; k++){ cur += t[k] * cm; cur %= m[j]; cm *= m[k]; cm %= m[j]; } cur = r[j] - cur; cur %= m[j]; if(cur<0)cur += m[j]; if(j==1)cur *= 416537774; if(j==2)cur *= 429847628; cur %= m[j]; t[j] = cur; } mint cm = 1; for(int j=0; j<3; j++){ ret[i] += cm * t[j]; cm *= m[j]; } } return ret; } // Product of Polynomial Sequences // O(N log^2 N) time, O(N) space template<typename T> std::vector<T> poly_prod(std::vector<std::vector<T>> f) { if ((int)f.size() == 0) return {1}; std::deque<std::vector<T>> p; for (int i=0; i<(int)f.size(); i++){ p.push_back(f[i]); } while((int)p.size() > 1) { std::vector<T> p1 = p.back(); p.pop_back(); std::vector<T> p2 = p.back(); p.pop_back(); p.push_front(convolution_mint(p1, p2)); } return p.back(); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll n, m, p; cin >> n >> m >> p; mint::set_mod(p); vector<mint> fact(n+1), factinv(n+1); fact[0] = 1; rep(i,1,n+1) fact[i] = fact[i-1] * i; factinv[n] = fact[n].inv(); rrep(i,0,n) factinv[i] = factinv[i+1] * (i + 1); vector<vector<mint>> ft; rep(i,0,n) ft.push_back({1, i+1}); vector<mint> f = poly_prod(ft); mint ans = 0; rep(k,1,m+1){ ans += fact[m]*factinv[k]*factinv[m-k]*factinv[k]*f[k]*fact[k]*fact[n-k]*factinv[n]; //cout << ans.val() << endl; } cout << ans.val() << endl; }