結果
問題 | No.2197 Same Dish |
ユーザー |
|
提出日時 | 2023-07-07 11:22:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 2,908 bytes |
コンパイル時間 | 951 ms |
コンパイル使用メモリ | 110,032 KB |
最終ジャッジ日時 | 2025-02-15 06:34:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include<iostream>#include<set>#include<algorithm>#include<vector>#include<string>#include<set>#include<map>#include<numeric>#include<queue>#include<cmath>using namespace std;typedef long long ll;const ll INF=1LL<<60;typedef pair<int,int> P;typedef pair<int,P> PP;const ll MOD=998244353;const double PI=acos(-1);//xのy乗ll mod_pow(ll x,ll y,ll mod){ll power=x;ll ret = 1;while(y>0){if(y&1){ret = ret*power%mod;}power = power*power%mod;y = y>>1;}return ret;}/*struct combination{typedef long long ll;std::vector<ll> fact,ifact;combination(ll n): fact(n+1),ifact(n+1){fact[0]=1;//0!=1通りfor(ll i=1;i<=n;i++) fact[i] = fact[i-1]*i%MOD;//ifact[n] = fact[n].inv();// n!の逆元がifact[n]ifact[n] = mod_pow(fact[n],MOD-2,MOD);// n!を(mod-2)乗した後でmodであまりをとったfor(ll i=n;i>=1;i--) ifact[i-1] = ifact[i]*i%MOD;}ll operator()(ll n,ll k){if(k<0 || k>n) return 0;// n!/( k!*(n-k)! )return (fact[n]*ifact[k])%MOD * ifact[n-k]%MOD;}};combination comb(2*100000);*/template<class Type> struct binary_indexed_tree{int N;vector<Type> bit;binary_indexed_tree(int n):N(n+1){bit = vector<Type>(n+1,0);N=n;}void add(int x,Type a){x++;//1から始めるための補正//for(int i=x; i<=N; i+=(i&-i)) bit[i] = addition(bit[i],a);while(x<=N){//bit[x] = addition(bit[x],a);bit[x] =bit[x]+a;x += x&-x;}}Type sum(int x){x++;//1から始まることに注意Type ret=0;//for(int i=x; i>0; i-=(i&-i)) ret = addition(ret,bit[i]);while(x>0){ret = ret+bit[x];x -= x&-x;}return ret;}//[l,r]の範囲// rはN-1以下Type get(int l,int r){if(r>N) return 0;//配列の外へのアクセスif(l>r) return 0;//本来は l<=r となるのでおかしいif(l==0) return sum(r);//[0,r]//ここでoutなわけかelse return (sum(r) - sum(l-1));}};int main(){int N,K;cin>>N>>K;vector<int> L(N),R(N);vector<P> range;for(int i=0;i<N;i++){cin>>L[i]>>R[i];range.emplace_back(L[i],i);}sort(range.begin(),range.end());int n=range.size();ll res=1;ll tot=mod_pow(K,N,MOD);//K^Nbinary_indexed_tree<ll> bit(200000+5);for(int i=0;i<N;i++){auto [x,id]=range[i];int m=bit.get(L[id]+1,200000+1);//(L[id])res*=max(0LL,1LL*(K-m));res%=MOD;bit.add(R[id],1);}ll ans=tot-res;ans+=MOD;ans%=MOD;cout<<ans<<endl;}