結果
| 問題 |
No.940 ワープ ε=ε=ε=ε=ε=│;p>д＜│
|
| コンテスト | |
| ユーザー |
 yosupot
|
| 提出日時 | 2019-12-03 12:18:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 109 ms / 5,000 ms |
| コード長 | 6,993 bytes |
| コンパイル時間 | 2,879 ms |
| コンパイル使用メモリ | 201,604 KB |
| 最終ジャッジ日時 | 2025-01-08 07:09:15 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 22 |
ソースコード
# 1 "main.cpp"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "main.cpp"
# 1 "/Users/yosupo/Programs/Algorithm/expander/dummy_include/bits/stdc++.h" 1
#include <bits/stdc++.h>
# 5 "main.cpp" 2
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
# 1 "/Users/yosupo/Programs/Algorithm/src/util/fast_io.h" 1
struct Scanner {
FILE* fp = nullptr;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) reread();
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T& ref) {
if (!succ()) return false;
while (true) {
succ();
size_t sz = 1;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (st != ed) break;
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T& ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) {
ref = 10 * ref + (line[st++] - '0');
}
if (neg) ref = -ref;
return true;
}
template <class T> bool read_single(V<T>& ref) {
for (auto& d : ref) {
if (!read_single(d)) return false;
}
return true;
}
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE* _fp) : fp(_fp) {}
};
struct Printer {
public:
template <bool F = false> void write() {}
template <bool F = false, class H, class... T>
void write(const H& h, const T&... t) {
if (F) write_single(' ');
write_single(h);
write<true>(t...);
}
template <class... T> void writeln(const T&... t) {
write(t...);
write_single('\n');
}
Printer(FILE* _fp) : fp(_fp) {}
~Printer() { flush(); }
private:
static constexpr size_t SIZE = 1 << 15;
FILE* fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write_single(const char& val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
void write_single(const T& val) {
for (char c : val) write_single(c);
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write_single(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write_single('0');
return;
}
if (val < 0) {
write_single('-');
val = -val;
}
size_t len = 0;
while (val) {
small[len++] = char('0' + (val % 10));
val /= 10;
}
reverse(small, small + len);
memcpy(line + pos, small, len);
pos += len;
}
template <class T> void write_single(const V<T>& val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write_single(' ');
write_single(val[i]);
}
}
};
# 15 "main.cpp" 2
# 40 "main.cpp"
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
return os << "P(" << p.first << ", " << p.second << ")";
}
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
os << "[";
for (auto d : v) os << d << ", ";
return os << "]";
}
# 1 "/Users/yosupo/Programs/Algorithm/src/math/modint.h" 1
template <uint MD> struct ModInt {
using M = ModInt;
const static M G;
uint v;
ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
M& set_v(uint _v) {
v = (_v < MD) ? _v : _v - MD;
return *this;
}
explicit operator bool() const { return v != 0; }
M operator-() const { return M() - *this; }
M operator+(const M& r) const { return M().set_v(v + r.v); }
M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
M operator/(const M& r) const { return *this * r.inv(); }
M& operator+=(const M& r) { return *this = *this + r; }
M& operator-=(const M& r) { return *this = *this - r; }
M& operator*=(const M& r) { return *this = *this * r; }
M& operator/=(const M& r) { return *this = *this / r; }
bool operator==(const M& r) const { return v == r.v; }
M pow(ll n) const {
M x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
M inv() const { return pow(MD - 2); }
friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
# 52 "main.cpp" 2
using Mint = ModInt<TEN(9) + 7>;
const int MN = 3 * 1100100;
V<Mint> fact(MN + 1), iFac(MN + 1), p2(MN + 1);
void first() {
fact[0] = Mint(1);
for (int i = 1; i <= MN; i++) {
fact[i] = fact[i - 1] * Mint(i);
}
iFac[MN] = fact[MN].inv();
for (int i = MN; i >= 1; i--) {
iFac[i - 1] = iFac[i] * Mint(i);
}
p2[0] = Mint(1);
for (int i = 1; i <= MN; i++) {
p2[i] = p2[i - 1] * Mint(2);
}
}
Mint C(int n, int k) {
if (n < k || k < 0) return Mint(0);
return fact[n] * iFac[k] * iFac[n - k];
}
int main() {
Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);
first();
int x, y, z;
sc.read(x, y, z);
if (x == 0 && y == 0 && z == 0) {
pr.writeln(1);
return 0;
}
int n = x + y + z + 10;
Mint ans = 0;
# 99 "main.cpp"
V<Mint> po(n + 1);
po[0] += Mint(1);
for (int i = 0; i <= n; i++) {
po[i] -= p2[n] * C(n, i);
}
for (int i = 0; i <= n; i++) po[i] *= Mint(-1);
Mint rem = po[n], i2 = Mint(2).inv();
po[n] = Mint(0);
for (int i = n - 1; i >= 0; i--) {
Mint nx = po[i];
po[i] = rem * i2;
rem = nx - po[i];
}
for (int l = 0; l < n; l++) {
ans += po[l] * (((l + x + y + z) % 2) ? Mint(-1) : Mint(1)) * C(l, x) * C(l, y) * C(l, z);
}
ans /= Mint(2);
pr.writeln(ans.v);
return 0;
}