結果

問題 No.1354 Sambo's Treasure
ユーザー 👑 NachiaNachia
提出日時 2021-01-17 14:44:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 698 ms / 2,000 ms
コード長 2,042 bytes
コンパイル時間 2,177 ms
コンパイル使用メモリ 203,652 KB
実行使用メモリ 13,952 KB
最終ジャッジ日時 2024-12-16 03:50:50
合計ジャッジ時間 18,044 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 3 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 656 ms
13,824 KB
testcase_24 AC 671 ms
13,824 KB
testcase_25 AC 654 ms
13,800 KB
testcase_26 AC 648 ms
13,940 KB
testcase_27 AC 654 ms
13,932 KB
testcase_28 AC 652 ms
13,824 KB
testcase_29 AC 674 ms
13,812 KB
testcase_30 AC 664 ms
13,824 KB
testcase_31 AC 656 ms
13,808 KB
testcase_32 AC 698 ms
13,940 KB
testcase_33 AC 651 ms
13,812 KB
testcase_34 AC 662 ms
13,824 KB
testcase_35 AC 666 ms
13,952 KB
testcase_36 AC 652 ms
13,824 KB
testcase_37 AC 659 ms
13,824 KB
testcase_38 AC 647 ms
13,808 KB
testcase_39 AC 660 ms
13,932 KB
testcase_40 AC 665 ms
13,824 KB
testcase_41 AC 663 ms
13,824 KB
testcase_42 AC 662 ms
13,952 KB
testcase_43 AC 12 ms
13,184 KB
testcase_44 AC 12 ms
13,044 KB
testcase_45 AC 13 ms
13,056 KB
testcase_46 AC 12 ms
13,168 KB
testcase_47 AC 12 ms
13,172 KB
testcase_48 AC 12 ms
13,040 KB
testcase_49 AC 12 ms
13,184 KB
testcase_50 AC 12 ms
13,056 KB
testcase_51 AC 12 ms
13,164 KB
testcase_52 AC 13 ms
13,168 KB
testcase_53 AC 11 ms
13,056 KB
testcase_54 AC 10 ms
13,044 KB
testcase_55 AC 11 ms
13,056 KB
testcase_56 AC 12 ms
13,168 KB
testcase_57 AC 12 ms
13,040 KB
testcase_58 AC 11 ms
13,056 KB
testcase_59 AC 10 ms
13,056 KB
testcase_60 AC 12 ms
13,172 KB
testcase_61 AC 12 ms
13,184 KB
testcase_62 AC 11 ms
13,184 KB
testcase_63 AC 647 ms
13,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

const ULL M = 998244353;
const ULL ZF=400000;
ULL F[ZF+1],I[ZF+1],iF[ZF+1];
void initF(int zf){
  F[0]=I[1]=iF[0]=1;
  for(int i=1; i<=zf; i++) F[i]=F[i-1]*i%M;
  for(int i=2; i<=zf; i++) I[i]=M-M/i*I[M%i]%M;
  for(int i=1; i<=zf; i++) iF[i]=iF[i-1]*I[i]%M;
}
ULL C(int n,int r){ return F[n]*iF[r]%M*iF[n-r]%M;}

inline void addmod(ULL& l,ULL r){ l+=r; if(l>=M) l-=M; }

int tH,tW,tL;
int tTx[102],tTy[102];
ULL tdp[102][102];
ULL tans[101];

void loop(){
  rep(i,tL) rep(j,tL-1) if(make_pair(tTx[j],tTy[j])>make_pair(tTx[j+1],tTy[j+1])){ swap(tTx[j],tTx[j+1]); swap(tTy[j],tTy[j+1]); }
  for(int i=tL-1; i>=0; i--){ tTx[i+1]=tTx[i]; tTy[i+1]=tTy[i]; }
  tTx[0]=0; tTy[0]=0;
  tTx[tL+1]=tW; tTy[tL+1]=tH; tL+=2;
  rep(i,tL) rep(k,tL) tdp[i][k]=0;
  tdp[0][0]=1;
  rep(i,tL){
    rep(p,i){
      int dx=tTx[i]-tTx[p], dy=tTy[i]-tTy[p];
      if(dx<0 || dy<0) continue;
      ULL P = C(dx+dy,dx);
      rep(t,i) tdp[i][t+1]=(tdp[i][t+1]+tdp[p][t]*P)%M;
    }
  }
  rep(t,tL-1) tans[t]=tdp[tL-1][t+1];
  tL-=2;
  for(int i=tL; i>=0; i--) for(int j=i+1; j<=tL; j++){
    tans[i] = (tans[i]+(M-tans[j])*C(j,i))%M;
  }
}

int N,Ch,L,K;
int Cx[100002],Cy[100002];
int Tx[100],Ty[100];
ULL dp[101]={};

int main(){
  scanf("%d%d%d%d",&N,&Ch,&L,&K);
  initF(N*2);
  K=min(K,L);
  Cx[0]=0; Cy[0]=0;
  rep(i,Ch) scanf("%d%d",&Cx[i+1],&Cy[i+1]);
  Cx[Ch+1]=N; Cy[Ch+1]=N;
  rep(i,L) scanf("%d%d",&Tx[i],&Ty[i]);
  dp[0]=1;
  rep(ch,Ch+1){
    tH=Cy[ch+1]-Cy[ch]; tW=Cx[ch+1]-Cx[ch];
    tL=0;
    rep(i,L){
      int x=Tx[i], y=Ty[i];
      if(Cx[ch]<=x && x<=Cx[ch+1] && Cy[ch]<=y && y<=Cy[ch+1]) if(!(Cx[ch]==x && Cy[ch]==y)){
        tTx[tL]=x-Cx[ch]; tTy[tL]=y-Cy[ch]; tL++;
      }
    }
    loop();
    ULL buf[101]={};
    rep(i,101) rep(s,i+1) if(i-s<=tL) buf[i]=(buf[i]+dp[s]*tans[i-s])%M;
    rep(i,101) dp[i]=buf[i];
  }
  ULL ans=0;
  rep(i,K+1) ans+=dp[i]; ans%=M;
  printf("%llu\n",ans);
  return 0;
}
0