結果
問題 |
No.3004 ヤング図形
|
ユーザー |
|
提出日時 | 2025-01-17 23:08:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,926 ms / 4,000 ms |
コード長 | 3,065 bytes |
コンパイル時間 | 2,256 ms |
コンパイル使用メモリ | 197,068 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-17 23:09:27 |
合計ジャッジ時間 | 34,558 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct Montgomery{ //2^62未満&奇数modのみ. //初めにsetmodする. using u64 = uint64_t; using u128 = __uint128_t; private: static u64 mod,N2,Rsq; //N*N2≡1(mod N); //Rsq = R^2modN; R=2^64. u64 v = 0; public: long long val(){return reduce(v);} static void setmod(u64 m){ assert(m<(1LL<<62)&&(m&1)); mod = m; N2 = mod; for(int i=0; i<5; i++) N2 *= 2-N2*mod; Rsq = (-u128(mod))%mod; } //reduce = T*R^-1modNを求める. u64 reduce(const u128 &T){ //T*R^-1≡(T+(T*(-N2))modR*N)/R 2N未満なので-N必要かだけで良い. u64 ret = (T+u128(((u64)T)*(-N2))*mod)>>64; if(ret >= mod) ret -= mod; return ret; } //初期値<mod. 初めにw*R modN...->reduce(R^2)でok. Montgomery(){v = 0;} Montgomery(long long w):v(reduce(u128(w)*Rsq)){} Montgomery& operator=(const Montgomery &b) = default; Montgomery operator-()const{return Montgomery()-Montgomery(*this);} Montgomery operator+(const Montgomery &b)const{return Montgomery(*this)+=b;} Montgomery operator-(const Montgomery &b)const{return Montgomery(*this)-=b;} Montgomery operator*(const Montgomery &b)const{return Montgomery(*this)*=b;} Montgomery operator/(const Montgomery &b)const{return Montgomery(*this)/=b;} Montgomery& operator+=(const Montgomery &b){ v += b.v; if(v >= mod) v -= mod; return (*this); } Montgomery& operator-=(const Montgomery &b){ v += mod-b.v; if(v >= mod) v -= mod; return (*this); } Montgomery& operator*=(const Montgomery &b){ v = reduce(u128(v)*b.v); return (*this); } Montgomery& operator/=(const Montgomery &b){ (*this) *= b.inv(); return (*this); } Montgomery pow(u64 b)const{ Montgomery ret = 1,p = (*this); while(b){ if(b&1) ret *= p; p *= p; b >>= 1; } return ret; } Montgomery inv()const{return pow(mod-2);} bool operator!=(const Montgomery &b){return v!=b.v;} bool operator==(const Montgomery &b){return v==b.v;} }; typename Montgomery::u64 Montgomery::mod,Montgomery::N2,Montgomery::Rsq; using mont = Montgomery; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int K; cin >> K; int sum = 0; using mint = Montgomery; mint::setmod(998244353); vector<pair<int,int>> LM(K); mint answer = 1; for(auto &[L,M] : LM){ cin >> L >> M; int now = L*M; sum += now; mint div = 1; for(int i=1; i<=L-1; i++) div *= i; div = div.inv(); while(now){ now--; mint mul = 1; for(int i=1; i<=L-1; i++) mul *= now--; mul *= div; answer *= mul; } div = 1; for(int i=1; i<=L*M; i++) div *= i; answer /= div; } for(int i=1; i<=sum; i++) answer *= i; cout << answer.val() << endl; }