結果
問題 | No.2230 Good Omen of White Lotus |
ユーザー |
![]() |
提出日時 | 2023-02-24 22:37:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 181 ms / 2,000 ms |
コード長 | 1,471 bytes |
コンパイル時間 | 523 ms |
コンパイル使用メモリ | 56,816 KB |
実行使用メモリ | 7,580 KB |
最終ジャッジ日時 | 2024-09-13 05:47:47 |
合計ジャッジ時間 | 5,327 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
#include <stdio.h> #include <vector> #include <algorithm> #define MOD 998244353 struct segTree{ int value[800010]; void setValue(int ind, int val, int l=1, int r=200000, int v=1) { if(l==r) value[v] = val; else { int h = (l+r)/2; if(ind<=h) setValue(ind,val,l,h,2*v); else setValue(ind,val,h+1,r,2*v+1); value[v] = value[2*v]>value[2*v+1]?value[2*v]:value[2*v+1]; } } int getMax(int L, int R,int l=1, int r=200000, int v=1) { if(L<=l&&r<=R) return value[v]; else if(r<L) return 0; else if(R<l) return 0; else { int h = (l+r)/2; int s1 = getMax(L,R,l,h,2*v); int s2 = getMax(L,R,h+1,r,2*v+1); return s1>s2?s1:s2; } } }T; long long int power(long long int a, long long int b) { long long int ans = 1; long long int k = a; while(b) { if(b%2==1) ans*=k, ans%=MOD; b/=2; k*=k, k%=MOD; } return ans; } long long int inv(long long int k) { return power(k,MOD-2); } std::pair<int,int> x[200010]; int main() { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); for(int i=1;i<=c;i++) { int e,f; scanf("%d%d",&e,&f); x[i] = std::make_pair(e,f); } std::sort(x+1,x+c+1); int ans = 0; for(int i=1;i<=c;i++) { int t = T.getMax(1,x[i].second) + 1; ans = ans>t?ans:t; T.setValue(x[i].second,t); } long long int P = 1; for(int i=1;i<=a+b-3;i++) P *= inv(d), P %= MOD; for(int i=1;i<=ans;i++) P *= (d-2), P %= MOD; for(int i=1;i<=a+b-3-ans;i++) P *= (d-1), P %= MOD; printf("%lld",(MOD-P+1)%MOD); }