結果

問題 No.1354 Sambo's Treasure
コンテスト
ユーザー Nachia
提出日時 2021-01-17 14:44:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 643 ms / 2,000 ms
コード長 2,042 bytes
コンパイル時間 2,632 ms
コンパイル使用メモリ 195,428 KB
最終ジャッジ日時 2025-01-18 00:56:48
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |   scanf("%d%d%d%d",&N,&Ch,&L,&K);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:57:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |   rep(i,Ch) scanf("%d%d",&Cx[i+1],&Cy[i+1]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:59:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |   rep(i,L) scanf("%d%d",&Tx[i],&Ty[i]);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

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