結果

問題 No.1354 Sambo's Treasure
ユーザー 👑 NachiaNachia
提出日時 2021-01-17 14:44:38
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 583 ms / 2,000 ms
コード長 2,042 bytes
コンパイル時間 2,148 ms
コンパイル使用メモリ 202,684 KB
実行使用メモリ 13,748 KB
最終ジャッジ日時 2023-08-22 08:11:04
合計ジャッジ時間 17,276 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,564 KB
testcase_01 AC 3 ms
7,564 KB
testcase_02 AC 2 ms
7,576 KB
testcase_03 AC 3 ms
7,724 KB
testcase_04 AC 3 ms
7,616 KB
testcase_05 AC 3 ms
7,804 KB
testcase_06 AC 3 ms
7,544 KB
testcase_07 AC 3 ms
7,568 KB
testcase_08 AC 3 ms
7,836 KB
testcase_09 AC 2 ms
7,696 KB
testcase_10 AC 2 ms
7,644 KB
testcase_11 AC 3 ms
7,576 KB
testcase_12 AC 2 ms
7,644 KB
testcase_13 AC 3 ms
7,644 KB
testcase_14 AC 2 ms
7,552 KB
testcase_15 AC 2 ms
7,644 KB
testcase_16 AC 2 ms
7,628 KB
testcase_17 AC 3 ms
7,616 KB
testcase_18 AC 3 ms
7,592 KB
testcase_19 AC 2 ms
7,580 KB
testcase_20 AC 3 ms
7,656 KB
testcase_21 AC 2 ms
7,700 KB
testcase_22 AC 2 ms
7,656 KB
testcase_23 AC 575 ms
13,644 KB
testcase_24 AC 576 ms
13,692 KB
testcase_25 AC 575 ms
13,656 KB
testcase_26 AC 577 ms
13,600 KB
testcase_27 AC 574 ms
13,672 KB
testcase_28 AC 574 ms
13,708 KB
testcase_29 AC 578 ms
13,624 KB
testcase_30 AC 583 ms
13,692 KB
testcase_31 AC 576 ms
13,588 KB
testcase_32 AC 577 ms
13,668 KB
testcase_33 AC 578 ms
13,696 KB
testcase_34 AC 576 ms
13,696 KB
testcase_35 AC 578 ms
13,692 KB
testcase_36 AC 578 ms
13,596 KB
testcase_37 AC 577 ms
13,748 KB
testcase_38 AC 578 ms
13,600 KB
testcase_39 AC 576 ms
13,712 KB
testcase_40 AC 577 ms
13,616 KB
testcase_41 AC 576 ms
13,600 KB
testcase_42 AC 577 ms
13,668 KB
testcase_43 AC 13 ms
12,988 KB
testcase_44 AC 13 ms
13,080 KB
testcase_45 AC 13 ms
12,928 KB
testcase_46 AC 13 ms
12,968 KB
testcase_47 AC 13 ms
12,932 KB
testcase_48 AC 13 ms
13,056 KB
testcase_49 AC 13 ms
13,064 KB
testcase_50 AC 13 ms
12,888 KB
testcase_51 AC 13 ms
12,996 KB
testcase_52 AC 13 ms
13,192 KB
testcase_53 AC 13 ms
12,996 KB
testcase_54 AC 13 ms
13,000 KB
testcase_55 AC 13 ms
13,056 KB
testcase_56 AC 13 ms
13,000 KB
testcase_57 AC 14 ms
12,996 KB
testcase_58 AC 13 ms
13,016 KB
testcase_59 AC 13 ms
12,996 KB
testcase_60 AC 13 ms
12,936 KB
testcase_61 AC 13 ms
12,988 KB
testcase_62 AC 13 ms
13,076 KB
testcase_63 AC 574 ms
13,648 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