結果
問題 | No.1354 Sambo's Treasure |
ユーザー | Chanyuh |
提出日時 | 2021-01-20 17:15:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 463 ms / 2,000 ms |
コード長 | 8,645 bytes |
コンパイル時間 | 2,266 ms |
コンパイル使用メモリ | 148,836 KB |
実行使用メモリ | 110,268 KB |
最終ジャッジ日時 | 2024-12-23 07:03:04 |
合計ジャッジ時間 | 17,922 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
97,024 KB |
testcase_01 | AC | 77 ms
97,024 KB |
testcase_02 | AC | 78 ms
96,896 KB |
testcase_03 | AC | 78 ms
97,024 KB |
testcase_04 | AC | 79 ms
97,024 KB |
testcase_05 | AC | 77 ms
97,024 KB |
testcase_06 | AC | 79 ms
97,024 KB |
testcase_07 | AC | 80 ms
97,024 KB |
testcase_08 | AC | 79 ms
97,024 KB |
testcase_09 | AC | 77 ms
97,024 KB |
testcase_10 | AC | 77 ms
97,024 KB |
testcase_11 | AC | 77 ms
97,024 KB |
testcase_12 | AC | 79 ms
97,024 KB |
testcase_13 | AC | 79 ms
97,024 KB |
testcase_14 | AC | 78 ms
97,024 KB |
testcase_15 | AC | 79 ms
97,024 KB |
testcase_16 | AC | 79 ms
97,024 KB |
testcase_17 | AC | 77 ms
97,024 KB |
testcase_18 | AC | 81 ms
96,896 KB |
testcase_19 | AC | 79 ms
97,024 KB |
testcase_20 | AC | 80 ms
97,024 KB |
testcase_21 | AC | 78 ms
96,896 KB |
testcase_22 | AC | 78 ms
97,024 KB |
testcase_23 | AC | 460 ms
110,136 KB |
testcase_24 | AC | 460 ms
110,136 KB |
testcase_25 | AC | 462 ms
110,120 KB |
testcase_26 | AC | 458 ms
110,132 KB |
testcase_27 | AC | 462 ms
110,140 KB |
testcase_28 | AC | 462 ms
110,140 KB |
testcase_29 | AC | 460 ms
109,368 KB |
testcase_30 | AC | 457 ms
110,136 KB |
testcase_31 | AC | 458 ms
110,140 KB |
testcase_32 | AC | 460 ms
110,136 KB |
testcase_33 | AC | 458 ms
110,136 KB |
testcase_34 | AC | 457 ms
110,132 KB |
testcase_35 | AC | 459 ms
110,136 KB |
testcase_36 | AC | 463 ms
110,136 KB |
testcase_37 | AC | 457 ms
110,136 KB |
testcase_38 | AC | 457 ms
110,140 KB |
testcase_39 | AC | 460 ms
110,268 KB |
testcase_40 | AC | 459 ms
110,132 KB |
testcase_41 | AC | 460 ms
110,136 KB |
testcase_42 | AC | 457 ms
110,136 KB |
testcase_43 | AC | 81 ms
97,024 KB |
testcase_44 | AC | 82 ms
97,152 KB |
testcase_45 | AC | 82 ms
97,152 KB |
testcase_46 | AC | 82 ms
97,024 KB |
testcase_47 | AC | 83 ms
97,024 KB |
testcase_48 | AC | 83 ms
97,152 KB |
testcase_49 | AC | 80 ms
97,024 KB |
testcase_50 | AC | 83 ms
97,024 KB |
testcase_51 | AC | 82 ms
97,152 KB |
testcase_52 | AC | 83 ms
97,024 KB |
testcase_53 | AC | 83 ms
97,024 KB |
testcase_54 | AC | 81 ms
97,152 KB |
testcase_55 | AC | 81 ms
97,152 KB |
testcase_56 | AC | 80 ms
97,152 KB |
testcase_57 | AC | 80 ms
97,024 KB |
testcase_58 | AC | 82 ms
97,152 KB |
testcase_59 | AC | 83 ms
97,152 KB |
testcase_60 | AC | 83 ms
97,152 KB |
testcase_61 | AC | 80 ms
97,152 KB |
testcase_62 | AC | 83 ms
97,152 KB |
testcase_63 | AC | 458 ms
110,132 KB |
ソースコード
#include<iostream> #include<array> #include<string> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<ciso646> #include<random> #include<map> #include<set> #include<complex> #include<bitset> #include<stack> #include<unordered_map> #include<utility> #include<tuple> #include<cassert> using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 998244353; const ll INF = (ll)1000000007 * 1000000007; typedef pair<int, int> P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define Per(i,sta,n) for(int i=n-1;i>=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair<ll, ll> LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;} template<int mod> struct ModInt { long long x; static constexpr int MOD = mod; ModInt() : x(0) {} ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} explicit operator int() const {return x;} ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } ModInt operator%(const ModInt &p) const { return ModInt(0); } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const{ int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } ModInt power(long long n) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } ModInt power(const ModInt p) const{ return ((ModInt)x).power(p.x); } friend ostream &operator<<(ostream &os, const ModInt<mod> &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt<mod> &a) { long long x; is >> x; a = ModInt<mod>(x); return (is); } }; using modint = ModInt<mod>; struct ModFac{ public: vector<modint> f,i_f; int n; ModFac(int n_){ n=n_; f.resize(n+1,1); i_f.resize(n+1,1); for(int i=0;i<n;i++){ f[i+1]=f[i]*(modint)(i+1); } i_f[n]=f[n].power(mod-2); for(int i=n-1;i>=0;i--){ i_f[i]=i_f[i+1]*(modint)(i+1); } } ModFac(modint n_){ n=(int)n_; f.resize(n+1,1); i_f.resize(n+1,1); for(int i=0;i<n;i++){ f[i+1]=f[i]*(modint)(i+1); } i_f[n]=f[n].power(mod-2); for(int i=n-1;i>=0;i--){ i_f[i]=i_f[i+1]*(modint)(i+1); } } modint factorial(int x){ //cout << f.size() << endl; return f[x]; } modint inv_factorial(int x){ return i_f[x]; } modint comb(int m,int k){ if (m<0 or k<0) return 0; if (m<k) return 0; return f[m]*i_f[k]*i_f[m-k]; } }; template <typename Mint> struct NumberTheoreticTransformFriendlyModInt { vector<Mint> dw, idw; int max_base; Mint root; NumberTheoreticTransformFriendlyModInt() { const unsigned mod = Mint::MOD; assert(mod >= 3 && mod % 2 == 1); auto tmp = mod - 1; max_base = 0; while(tmp % 2 == 0) tmp >>= 1, max_base++; root = 2; while(root.power((mod - 1) >> 1) == 1) root += 1; assert(root.power(mod - 1) == 1); dw.resize(max_base); idw.resize(max_base); for(int i = 0; i < max_base; i++) { dw[i] = -root.power((mod - 1) >> (i + 2)); idw[i] = Mint(1) / dw[i]; } } void ntt(vector<Mint> &a) { const int n = (int)a.size(); assert((n & (n - 1)) == 0); assert(__builtin_ctz(n) <= max_base); for(int m = n; m >>= 1;) { Mint w = 1; for(int s = 0, k = 0; s < n; s += 2 * m) { for(int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j] * w; a[i] = x + y, a[j] = x - y; } w *= dw[__builtin_ctz(++k)]; } } } void intt(vector<Mint> &a, bool f = true) { const int n = (int)a.size(); assert((n & (n - 1)) == 0); assert(__builtin_ctz(n) <= max_base); for(int m = 1; m < n; m *= 2) { Mint w = 1; for(int s = 0, k = 0; s < n; s += 2 * m) { for(int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j]; a[i] = x + y, a[j] = (x - y) * w; } w *= idw[__builtin_ctz(++k)]; } } if(f) { Mint inv_sz = Mint(1) / n; for(int i = 0; i < n; i++) a[i] *= inv_sz; } } vector<Mint> multiply(vector<Mint> a, vector<Mint> b) { int need = a.size() + b.size() - 1; int nbase = 1; while((1 << nbase) < need) nbase++; int sz = 1 << nbase; a.resize(sz, 0); b.resize(sz, 0); ntt(a); ntt(b); Mint inv_sz = Mint(1) / sz; for(int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz; intt(a, false); a.resize(need); return a; } }; int n,m,l,k; vector<P> cs,ts; modint dp1[100010][110]; ModFac MF(500010); vector<modint> calc(int s){ vector<P> vec={cs[s]}; bool f=false; rep(i,l){ if(cs[s].first<=ts[i].first && ts[i].first<=cs[s+1].first){ if(cs[s].second<=ts[i].second && ts[i].second<=cs[s+1].second){ if(cs[s+1]==ts[i]) f=true; if(cs[s]==ts[i] || cs[s+1]==ts[i]) continue; vec.push_back(ts[i]); } } } vec.push_back(cs[s+1]); int z=vec.size(); vector<vector<modint>> r(z,vector<modint>(z)); per(i,z){ Rep(j,i+1,z){ r[i][j]=MF.comb(vec[j].first-vec[i].first+vec[j].second-vec[i].second,vec[j].first-vec[i].first); Rep(k,i+1,j){ r[i][j]-=MF.comb(vec[k].first-vec[i].first+vec[k].second-vec[i].second,vec[k].first-vec[i].first)*r[k][j]; } } } vector<vector<modint>> dp2(z,vector<modint>(z+1)); //cout << z << " " << f << endl; dp2[0][0]=1; Rep(i,1,z){ rep(j,i){ rep(k,i+1){ dp2[i][k+1]+=r[j][i]*dp2[j][k]; } } // rep(k,i+2){ // cout << i << " " << k << " " << dp2[i][k] << endl; // } } vector<modint> res(z+1,0); Rep(k,1,z+1){ //cout << k << " " << dp2[z-1][k] << endl; if(f)res[k]=dp2[z-1][k]; else res[k-1]=dp2[z-1][k]; } return res; } NumberTheoreticTransformFriendlyModInt<modint> NTT; vector<modint> mul(vector<vector<modint>> &fs,int l,int r){ if(r-l==0)return vector<modint>(1,1); if(r-l==1)return fs[l]; return NTT.multiply(mul(fs,l,(l+r)/2),mul(fs,(l+r)/2,r)); } void solve(){ cin >> n >> m >> l >> k;chmin(k,l); cs.resize(m+2);ts.resize(l); cs[0]=P(0,0);cs[m+1]=P(n,n); rep(i,m){ cin >> cs[i+1].first >> cs[i+1].second; } rep(i,l){ cin >> ts[i].first >> ts[i].second; } sort(ts.begin(),ts.end()); vector<vector<modint>> fs; rep(i,m+1){ fs.push_back(calc(i)); } vector<modint> F=mul(fs,0,m+1); modint ans=0; rep(i,min((int)F.size(),k)+1){ ans+=F[i]; } cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }