結果
問題 | No.1683 Robot Guidance |
ユーザー |
![]() |
提出日時 | 2021-09-17 22:34:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 704 ms / 2,000 ms |
コード長 | 2,210 bytes |
コンパイル時間 | 3,411 ms |
コンパイル使用メモリ | 231,720 KB |
実行使用メモリ | 34,644 KB |
最終ジャッジ日時 | 2024-06-29 21:19:56 |
合計ジャッジ時間 | 29,801 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; const long nPrime = 1000000007; //const long nPrime = 998244353; typedef long long ll; long Inverse(const long &n){ if (n % nPrime == 0){ return 0; } long a = n, b = nPrime, u = 1, v = 0; while (b > 0) { long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= nPrime; if (u < 0){ u += nPrime; } return u; } int main() { vector<long> viTable(2000001,1), viInv(2000001,1); for(long i = 1; i <= 2000000; i++){ viTable[i] = (viTable[i-1] * i) % nPrime; viInv[i] = Inverse(viTable[i]); } long a,b,x,y; cin >> a >> b >> x >> y; if(((a+x+y)&1) == 1){ cout << 0 << endl; return 0; } long i1 = (b+4)/4; long i2 = (b+2)/4; long i3 = (b+3)/4; long i4 = (b+1)/4; long nAns = 0; for(long s = 0; s <= a; s++){ long t = s-x; long u = (a-2*s+x+y)/2; long v = u-y; if(t < 0 || u < 0 || v < 0){ continue; } if((i2 == 0 && t > 0) ||(i3 == 0 && u > 0) ||(i4 == 0 && v > 0) ){ continue; } long iThis = 1; iThis *= viTable[s+i1-1]; iThis %= nPrime; iThis *= viInv[s]; iThis %= nPrime; iThis *= viInv[i1-1]; iThis %= nPrime; if(i2 > 0){ iThis *= viTable[t+i2-1]; iThis %= nPrime; iThis *= viInv[t]; iThis %= nPrime; iThis *= viInv[i2-1]; iThis %= nPrime; } if(i3 > 0){ iThis *= viTable[u+i3-1]; iThis %= nPrime; iThis *= viInv[u]; iThis %= nPrime; iThis *= viInv[i3-1]; iThis %= nPrime; } if(i4 > 0){ iThis *= viTable[v+i4-1]; iThis %= nPrime; iThis *= viInv[v]; iThis %= nPrime; iThis *= viInv[i4-1]; iThis %= nPrime; } nAns += iThis; nAns %= nPrime; } cout << nAns << endl; return 0; }