結果
問題 | No.1549 [Cherry 2nd Tune] BANning Tuple |
ユーザー |
![]() |
提出日時 | 2021-06-11 22:53:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 387 ms / 4,000 ms |
コード長 | 1,307 bytes |
コンパイル時間 | 4,956 ms |
コンパイル使用メモリ | 271,392 KB |
最終ジャッジ日時 | 2025-01-22 06:41:05 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:30:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 30 | scanf("%lld %lld %lld %lld %lld",&K[i],&A[i],&B[i],&S[i],&T[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 100000000000000000 vector<mint> op(vector<mint> a,vector<mint> b){ a = convolution(a,b); while(a.size() > 3005)a.pop_back(); return a; } vector<mint> e(){ vector<mint> ret(3005,0); ret[0] = 1; return ret; } int main(){ long long N,Q; cin>>N>>Q; vector<long long> K(Q),A(Q),B(Q),S(Q),T(Q); map<long long,int> mp; rep(i,Q){ scanf("%lld %lld %lld %lld %lld",&K[i],&A[i],&B[i],&S[i],&T[i]); K[i]--; if(mp.count(K[i]))continue; int sz = mp.size(); mp[K[i]] = sz; } vector<vector<mint>> temp(mp.size()+1,e()); rep(i,mp.size())temp[i] = vector<mint>(3005,1); long long n = N - mp.size(); vector<mint> Inv(3006,0); rep(i,3006){ if(i!=0)Inv[i] = mint(i).inv(); } rep(i,3005){ mint cur = 1; rep(j,i){ cur *= Inv[j+1]; cur *= i+n-1 - j; } temp.back()[i] = cur; } segtree<vector<mint>,op,e> seg(temp); rep(i,Q){ K[i] = mp[K[i]]; vector<mint> t = seg.get(K[i]); for(int j=A[i];j<=B[i];j++)t[j] = 0; seg.set(K[i],t); t = seg.all_prod(); mint ans = 0; for(int j=S[i];j<=T[i];j++)ans += t[j]; cout<<ans.val()<<endl; } return 0; }