結果

問題 No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
ユーザー pekempeypekempey
提出日時 2019-12-03 15:28:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 401 ms / 5,000 ms
コード長 3,225 bytes
コンパイル時間 1,594 ms
コンパイル使用メモリ 174,776 KB
実行使用メモリ 61,916 KB
最終ジャッジ日時 2024-05-06 08:15:18
合計ジャッジ時間 12,363 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 351 ms
50,208 KB
testcase_01 AC 336 ms
50,340 KB
testcase_02 AC 347 ms
50,216 KB
testcase_03 AC 333 ms
50,468 KB
testcase_04 AC 338 ms
50,340 KB
testcase_05 AC 343 ms
50,208 KB
testcase_06 AC 331 ms
50,208 KB
testcase_07 AC 341 ms
50,340 KB
testcase_08 AC 338 ms
50,212 KB
testcase_09 AC 331 ms
50,216 KB
testcase_10 AC 339 ms
50,212 KB
testcase_11 AC 337 ms
50,340 KB
testcase_12 AC 348 ms
50,208 KB
testcase_13 AC 341 ms
50,212 KB
testcase_14 AC 331 ms
50,212 KB
testcase_15 AC 343 ms
50,468 KB
testcase_16 AC 357 ms
51,368 KB
testcase_17 AC 373 ms
56,484 KB
testcase_18 AC 381 ms
58,400 KB
testcase_19 AC 370 ms
56,612 KB
testcase_20 AC 401 ms
60,964 KB
testcase_21 AC 395 ms
54,304 KB
testcase_22 AC 387 ms
59,300 KB
testcase_23 AC 347 ms
51,868 KB
testcase_24 AC 378 ms
59,172 KB
testcase_25 AC 399 ms
60,712 KB
testcase_26 AC 399 ms
61,916 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
 
#define rep(i, n)      for (int i = 0; i < (n); i++)
#define repr(i, n)     for (int i = (n) - 1; i >= 0; i--)
#define repe(i, l, r)  for (int i = (l); i < (r); i++)
#define reper(i, l, r) for (int i = (r) - 1; i >= (l); i--)
#define repi(i, l, r)  for (int i = (l); i <= (r); i++)
#define repir(i, l, r) for (int i = (r); i >= (l); i--)
#define range(a) a.begin(), a.end()
void initio() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

constexpr int MOD = 1000000007;

class mint {
  int n;
public:
  mint(int n_ = 0) : n(n_) {}
  explicit operator int() { return n; }
  friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
  friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
  friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
  friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
  friend mint &operator+=(mint &a, mint b) { return a = a + b; }
  friend mint &operator-=(mint &a, mint b) { return a = a - b; }
  friend mint &operator*=(mint &a, mint b) { return a = a * b; }
  friend bool operator==(mint a, mint b) { return a.n == b.n; }
  friend bool operator!=(mint a, mint b) { return a.n != b.n; }
  friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
  friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};

vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};

void check_fact(int n) {
  for (int i = I_.size(); i <= n; i++) {
    I_.push_back(I_[MOD % i] * (MOD - MOD / i));
    F_.push_back(F_[i - 1] * i);
    R_.push_back(R_[i - 1] * I_[i]);
  }
}

mint I(int n) { check_fact(n); return n < 0 ? 0 : I_[n]; }
mint F(int n) { check_fact(n); return n < 0 ? 0 : F_[n]; }
mint R(int n) { check_fact(n); return n < 0 ? 0 : R_[n]; }
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint RC(int n, int r) { return R(n) * F(n - r) * F(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }

mint alt(int n) {
  return n % 2 == 0 ? 1 : MOD - 1;
}

// https://yukicoder.me/submissions/404203 の解説が冗長だったので修正。コードは変わらない。
// 
// f = 1/(1-x)(1-y)(1-z) と置く。
// 十分おおきな M をとると求めたい値は
// [x^X y^Y z^Z] \sum_{k=0}^{M-1} (f-1)^k
// となる。これを f の多項式だと思って高速に展開したい。
// 
// 等比数列の和の公式より
// \sum_{k=0}^{M-1} (f-1)^k
// = ((f-1)^M - 1)/((f-1)-1)
// である。二項定理より分母は O(M) で展開できる。また分母を一次式で割るのも O(M) でできる。よって全体で O(M) で展開できる。
// 
// [x^X y^Y z^Z] f^i = H(i,X) H(i,Y) H(i,Z)
// なので解けた。

int main() {
  int X, Y, Z; cin >> X >> Y >> Z;
  const int M = 3000000;
  vector<mint> f(M + 2);
  for (int i = 0; i <= M; i++) {
    f[i] = C(M, i) * alt(M - i);
  }
  f[0] -= 1;
  for (int i = 0; i <= M - 1; i++) {
    f[i] *= -I(2);
    f[i + 1] -= f[i];
  }
  mint ans;
  rep(i, M) {
    ans += H(i, X) * H(i, Y) * H(i, Z) * f[i];
  }
  cout << ans << endl;
}
0