結果
問題 | No.1683 Robot Guidance |
ユーザー |
![]() |
提出日時 | 2021-09-18 11:36:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,283 bytes |
コンパイル時間 | 3,809 ms |
コンパイル使用メモリ | 230,668 KB |
実行使用メモリ | 50,524 KB |
最終ジャッジ日時 | 2024-06-30 08:48:49 |
合計ジャッジ時間 | 7,286 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 7 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 2000005 #define MOD 1000000007 //#define MOD 998244353 #define INF 1000000000 //#define INF 1000000000000000000 ll fac[MAX],finv[MAX],inv[MAX]; void COMinit(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i<MAX;i++){ fac[i]=(fac[i-1]*i)%MOD; inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; finv[i]=finv[i-1]*inv[i]%MOD; } } ll COM(int n,int k){ if(n<k){ return 0; } if(n<0||k<0){ return 0; } return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD; } int main(){ int A,B,X,Y; cin>>A>>B>>X>>Y; if(abs(X)+abs(Y)>A){ cout<<0<<'\n'; return 0; }else if((abs(X)+abs(Y))%2!=A%2){ cout<<0<<'\n'; return 0; } COMinit(); ll ans=0; for(int x=abs(X);x<=A-abs(Y);x+=2){ int y=A-x; int x_plus=1; int y_plus=0; int x_minus=0; int y_minus=0; if(B%4==0){ x_plus+=B/4; y_plus+=B/4; x_minus+=B/4; y_minus+=B/4; }else if(B%4==1){ x_plus+=B/4; y_plus+=B/4+1; x_minus+=B/4; y_minus+=B/4; }else if(B%4==2){ x_plus+=B/4; y_plus+=B/4+1; x_minus+=B/4+1; y_minus+=B/4; }else{ x_plus+=B/4; y_plus+=B/4+1; x_minus+=B/4+1; y_minus+=B/4+1; } ll ret=1; if(X>0){ if(X+(x-X)/2>0){ ret*=COM(X+(x-X)/2+x_plus-1,x_plus-1); ret%=MOD; } if((x-X)/2>0){ ret*=COM((x-X)/2+x_minus-1,x_minus-1); ret%=MOD; } }else{ X=-X; if(X+(x-X)/2>0){ ret*=COM(X+(x-X)/2+x_minus-1,x_minus-1); ret%=MOD; } if((x-X)/2>0){ ret*=COM((x-X)/2+x_plus-1,x_plus-1); ret%=MOD; } } if(Y>0){ if(Y+(y-Y)/2>0){ ret*=COM(Y+(y-Y)/2+y_plus-1,y_plus-1); ret%=MOD; } if((y-Y)/2>0){ ret*=COM((y-Y)/2+y_minus-1,y_minus-1); ret%=MOD; } }else{ Y=-Y; if(Y+(y-Y)/2>0){ ret*=COM(Y+(y-Y)/2+y_minus-1,y_minus-1); ret%=MOD; } if((y-Y)/2>0){ ret*=COM((y-Y)/2+y_plus-1,y_plus-1); ret%=MOD; } } ans+=ret; ans%=MOD; } cout<<ans<<'\n'; }