Submission #1005439
Source Code Expand
#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll; template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; } template<int MOD> struct ModInt { static const int Mod = MOD; unsigned x; ModInt() : x(0) {} ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } int get() const { return (int)x; } ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; } ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; } ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; } ModInt &operator/=(ModInt that) { return *this *= that.inverse(); } ModInt operator+(ModInt that) const { return ModInt(*this) += that; } ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt inverse() const { signed a = x, b = MOD, u = 1, v = 0; while(b) { signed t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } if(u < 0) u += Mod; ModInt res; res.x = (unsigned)u; return res; } }; typedef ModInt<1000000007> mint; vector<mint> fact, factinv; void nCr_computeFactinv(int N) { N = min(N, mint::Mod - 1); fact.resize(N + 1); factinv.resize(N + 1); fact[0] = 1; rer(i, 1, N) fact[i] = fact[i - 1] * i; factinv[N] = fact[N].inverse(); for(int i = N; i >= 1; i --) factinv[i - 1] = factinv[i] * i; } mint nCr(int n, int r) { if(n >= mint::Mod) return nCr(n % mint::Mod, r % mint::Mod) * nCr(n / mint::Mod, r / mint::Mod); return r > n ? 0 : fact[n] * factinv[n - r] * factinv[r]; } int main() { int N; int A; int B; int C; while(~scanf("%d%d%d%d", &N, &A, &B, &C)) { nCr_computeFactinv(N); mint ans; rer(p, 0, N) rer(q, 0, N) { int a = A - p, b = B / 2, c = C - p - q * 3; if(a < 0 || c < 0 || B % 2 != 0) continue; int groups = a + b + p + q; mint cnt = 1; cnt *= fact[groups]; cnt *= factinv[a]; cnt *= factinv[b]; cnt *= factinv[p]; cnt *= factinv[q]; cnt *= b == 0 ? (c == 0 ? 1 : 0) : nCr(c + b - 1, b - 1); ans += cnt; } printf("%d\n", ans.get()); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - 123 Pairs |
User | anta |
Language | C++14 (GCC 5.4.1) |
Score | 1500 |
Code Size | 2883 Byte |
Status | AC |
Exec Time | 45 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt |
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, example0.txt, example1.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | AC | 37 ms | 256 KB |
001.txt | AC | 27 ms | 256 KB |
002.txt | AC | 27 ms | 256 KB |
003.txt | AC | 36 ms | 256 KB |
004.txt | AC | 27 ms | 256 KB |
005.txt | AC | 27 ms | 256 KB |
006.txt | AC | 35 ms | 256 KB |
007.txt | AC | 27 ms | 256 KB |
008.txt | AC | 27 ms | 256 KB |
009.txt | AC | 36 ms | 256 KB |
010.txt | AC | 35 ms | 256 KB |
011.txt | AC | 27 ms | 256 KB |
012.txt | AC | 27 ms | 256 KB |
013.txt | AC | 3 ms | 256 KB |
014.txt | AC | 3 ms | 256 KB |
015.txt | AC | 38 ms | 256 KB |
016.txt | AC | 6 ms | 256 KB |
017.txt | AC | 16 ms | 256 KB |
018.txt | AC | 6 ms | 256 KB |
019.txt | AC | 18 ms | 256 KB |
020.txt | AC | 19 ms | 256 KB |
021.txt | AC | 39 ms | 256 KB |
022.txt | AC | 25 ms | 256 KB |
023.txt | AC | 34 ms | 256 KB |
024.txt | AC | 40 ms | 256 KB |
025.txt | AC | 35 ms | 256 KB |
026.txt | AC | 37 ms | 256 KB |
027.txt | AC | 41 ms | 256 KB |
028.txt | AC | 35 ms | 256 KB |
029.txt | AC | 35 ms | 256 KB |
030.txt | AC | 38 ms | 256 KB |
031.txt | AC | 40 ms | 256 KB |
032.txt | AC | 32 ms | 256 KB |
033.txt | AC | 27 ms | 256 KB |
034.txt | AC | 19 ms | 256 KB |
035.txt | AC | 31 ms | 256 KB |
036.txt | AC | 16 ms | 256 KB |
037.txt | AC | 3 ms | 256 KB |
038.txt | AC | 45 ms | 256 KB |
039.txt | AC | 34 ms | 256 KB |
040.txt | AC | 31 ms | 256 KB |
041.txt | AC | 31 ms | 256 KB |
042.txt | AC | 30 ms | 256 KB |
043.txt | AC | 3 ms | 256 KB |
044.txt | AC | 3 ms | 256 KB |
045.txt | AC | 3 ms | 256 KB |
046.txt | AC | 3 ms | 256 KB |
047.txt | AC | 3 ms | 256 KB |
048.txt | AC | 3 ms | 256 KB |
049.txt | AC | 3 ms | 256 KB |
example0.txt | AC | 3 ms | 256 KB |
example1.txt | AC | 3 ms | 256 KB |