結果

問題 No.1354 Sambo's Treasure
ユーザー 👑 NachiaNachia
提出日時 2021-01-17 14:40:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,036 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 203,904 KB
実行使用メモリ 13,168 KB
最終ジャッジ日時 2024-05-07 03:39:54
合計ジャッジ時間 5,270 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,752 KB
testcase_01 AC 3 ms
7,752 KB
testcase_02 AC 3 ms
7,884 KB
testcase_03 AC 3 ms
7,752 KB
testcase_04 AC 3 ms
7,752 KB
testcase_05 AC 2 ms
7,884 KB
testcase_06 AC 3 ms
7,760 KB
testcase_07 AC 3 ms
7,752 KB
testcase_08 AC 2 ms
7,756 KB
testcase_09 AC 2 ms
7,880 KB
testcase_10 AC 3 ms
7,756 KB
testcase_11 AC 3 ms
7,760 KB
testcase_12 AC 3 ms
7,884 KB
testcase_13 AC 2 ms
7,888 KB
testcase_14 AC 3 ms
7,756 KB
testcase_15 AC 3 ms
7,880 KB
testcase_16 AC 3 ms
7,880 KB
testcase_17 AC 2 ms
7,760 KB
testcase_18 AC 2 ms
7,756 KB
testcase_19 AC 3 ms
7,628 KB
testcase_20 AC 2 ms
7,756 KB
testcase_21 AC 3 ms
7,880 KB
testcase_22 AC 3 ms
7,760 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 13 ms
13,164 KB
testcase_44 AC 13 ms
13,020 KB
testcase_45 AC 14 ms
13,016 KB
testcase_46 AC 13 ms
13,036 KB
testcase_47 AC 14 ms
13,032 KB
testcase_48 AC 14 ms
13,000 KB
testcase_49 AC 13 ms
13,168 KB
testcase_50 AC 13 ms
13,032 KB
testcase_51 AC 15 ms
13,040 KB
testcase_52 AC 14 ms
13,012 KB
testcase_53 AC 14 ms
13,040 KB
testcase_54 AC 14 ms
13,036 KB
testcase_55 AC 13 ms
13,168 KB
testcase_56 AC 14 ms
13,020 KB
testcase_57 AC 13 ms
13,016 KB
testcase_58 AC 14 ms
13,040 KB
testcase_59 AC 14 ms
13,036 KB
testcase_60 AC 14 ms
13,012 KB
testcase_61 AC 15 ms
13,072 KB
testcase_62 AC 14 ms
13,164 KB
testcase_63 WA -
権限があれば一括ダウンロードができます

ソースコード

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[102],Cy[102];
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