Submission #4090099
Source Code Expand
#ifndef ___CLASS_MODINT #define ___CLASS_MODINT #include <cstdint> template<std::uint32_t mod> class modint { private: std::uint32_t n; public: modint() : n(0) {}; modint(std::uint64_t n_) : n(n_ % mod) {}; bool operator==(const modint& m) const { return n == m.n; } bool operator!=(const modint& m) const { return n != m.n; } std::uint32_t get() const { return n; } modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; } modint operator+(const modint& m) const { return modint(*this) += m; } modint operator-(const modint& m) const { return modint(*this) -= m; } modint operator*(const modint& m) const { return modint(*this) *= m; } modint binpow(std::uint64_t b) const { modint ans = 1, m = modint(*this); while (b) { if (b & 1) ans *= m; m *= m; b >>= 1; } return ans; } modint inv() { return (*this).binpow(mod - 2); } }; #endif // ___CLASS_MODINT #include <vector> #include <iostream> #include <functional> using namespace std; const int mod = 1000000007; using modulo = modint<mod>; vector<modulo> convolve(vector<modulo> v1, vector<modulo> v2) { int s1 = v1.size(), s2 = v2.size(); vector<modulo> ans(s1 + s2 - 1); for (int i = 0; i < s1; ++i) { for (int j = 0; j < s2; ++j) { ans[i + j] += v1[i] * v2[j]; } } return ans; } modulo solve(int A, int B, int C) { if (B % 2 == 1) return 0; B /= 2; vector<modulo> fact(A + B + C + 1), inv(A + B + C + 1), factinv(A + B + C + 1); fact[0] = 1; inv[1] = 1; factinv[0] = 1; for (int i = 1; i <= A + B + C; ++i) fact[i] = fact[i - 1] * i; for (int i = 2; i <= A + B + C; ++i) inv[i] = inv[mod % i] * (mod - mod / i); for (int i = 1; i <= A + B + C; ++i) factinv[i] = factinv[i - 1] * inv[i]; function<modulo(int, int)> comb = [&](int a, int b) { if (a < b || b < 0) return modulo(0); return fact[a] * factinv[b] * factinv[a - b]; }; vector<modulo> poly1(A + 1), poly2(C + 1); for (int i = 0; i <= A; ++i) poly1[i] = comb(A, i); for (int i = 0; i <= C; ++i) poly2[i] = comb(B + i - 1, B - 1); if (B == 0) poly2[0] = 1; vector<modulo> ans = convolve(poly1, poly2); modulo res = 0; for (int i = C; i >= 0; i -= 3) { modulo mul = fact[A + B + (C - i) / 3] * factinv[A] * factinv[B] * factinv[(C - i) / 3]; res += mul * ans[i]; } return res; } int main() { int A, B, C; cin >> A >> B >> C; modulo ans = solve(A, B, C); cout << ans.get() << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - 123 Pairs |
User | square1001 |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 2685 Byte |
Status | WA |
Exec Time | 56 ms |
Memory | 512 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 20 ms | 384 KB |
001.txt | WA | 1 ms | 256 KB |
002.txt | WA | 56 ms | 512 KB |
003.txt | WA | 1 ms | 256 KB |
004.txt | WA | 2 ms | 384 KB |
005.txt | WA | 56 ms | 512 KB |
006.txt | WA | 1 ms | 256 KB |
007.txt | WA | 1 ms | 256 KB |
008.txt | WA | 1 ms | 256 KB |
009.txt | WA | 3 ms | 512 KB |
010.txt | WA | 1 ms | 256 KB |
011.txt | WA | 54 ms | 512 KB |
012.txt | AC | 1 ms | 384 KB |
013.txt | WA | 2 ms | 256 KB |
014.txt | WA | 1 ms | 256 KB |
015.txt | WA | 1 ms | 256 KB |
016.txt | WA | 1 ms | 256 KB |
017.txt | WA | 6 ms | 384 KB |
018.txt | WA | 1 ms | 256 KB |
019.txt | WA | 1 ms | 256 KB |
020.txt | WA | 6 ms | 384 KB |
021.txt | WA | 1 ms | 256 KB |
022.txt | WA | 1 ms | 256 KB |
023.txt | WA | 1 ms | 256 KB |
024.txt | WA | 13 ms | 384 KB |
025.txt | WA | 1 ms | 256 KB |
026.txt | WA | 1 ms | 256 KB |
027.txt | WA | 1 ms | 256 KB |
028.txt | WA | 1 ms | 256 KB |
029.txt | WA | 24 ms | 384 KB |
030.txt | WA | 1 ms | 256 KB |
031.txt | WA | 18 ms | 384 KB |
032.txt | WA | 26 ms | 384 KB |
033.txt | WA | 37 ms | 448 KB |
034.txt | WA | 1 ms | 256 KB |
035.txt | WA | 1 ms | 256 KB |
036.txt | WA | 1 ms | 256 KB |
037.txt | WA | 1 ms | 256 KB |
038.txt | WA | 1 ms | 256 KB |
039.txt | WA | 5 ms | 384 KB |
040.txt | AC | 1 ms | 256 KB |
041.txt | WA | 13 ms | 384 KB |
042.txt | WA | 1 ms | 256 KB |
043.txt | WA | 1 ms | 256 KB |
044.txt | AC | 1 ms | 256 KB |
045.txt | WA | 1 ms | 256 KB |
046.txt | WA | 1 ms | 256 KB |
047.txt | WA | 1 ms | 256 KB |
048.txt | WA | 1 ms | 256 KB |
049.txt | WA | 1 ms | 256 KB |
example0.txt | WA | 1 ms | 256 KB |
example1.txt | WA | 2 ms | 256 KB |