結果

問題 No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
ユーザー pekempeypekempey
提出日時 2019-12-03 02:30:44
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 479 ms / 5,000 ms
コード長 3,460 bytes
コンパイル時間 1,759 ms
コンパイル使用メモリ 170,208 KB
実行使用メモリ 62,372 KB
最終ジャッジ日時 2023-08-18 23:25:07
合計ジャッジ時間 14,853 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 368 ms
52,596 KB
testcase_01 AC 386 ms
53,748 KB
testcase_02 AC 370 ms
52,888 KB
testcase_03 AC 366 ms
52,092 KB
testcase_04 AC 377 ms
52,684 KB
testcase_05 AC 384 ms
52,336 KB
testcase_06 AC 376 ms
52,236 KB
testcase_07 AC 383 ms
53,028 KB
testcase_08 AC 387 ms
52,632 KB
testcase_09 AC 377 ms
53,564 KB
testcase_10 AC 388 ms
53,124 KB
testcase_11 AC 396 ms
52,540 KB
testcase_12 AC 393 ms
52,900 KB
testcase_13 AC 373 ms
55,956 KB
testcase_14 AC 382 ms
53,652 KB
testcase_15 AC 400 ms
53,652 KB
testcase_16 AC 408 ms
53,384 KB
testcase_17 AC 429 ms
58,624 KB
testcase_18 AC 442 ms
58,932 KB
testcase_19 AC 419 ms
59,076 KB
testcase_20 AC 458 ms
62,372 KB
testcase_21 AC 420 ms
54,372 KB
testcase_22 AC 455 ms
60,156 KB
testcase_23 AC 401 ms
53,720 KB
testcase_24 AC 479 ms
58,968 KB
testcase_25 AC 474 ms
60,568 KB
testcase_26 AC 466 ms
61,896 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;
}

// f = 1/(1-x)(1-y)(1-z) と置く。
// 十分おおきな M をとると求めたい値は
// [x^X y^Y z^Z] \sum_{k=0}^{M-1} (f-1)^k
// となる。
//
// \sum_{k=0}^{M-1} (f-1)^k
// = \sum_{k=0}^{M-1} \sum_{j=0}^{M-1} \binom{k}{j} (-1)^{k-j} f^j      (二項定理)
// = \sum_{j=0}^{M-1} f^j \sum_{k=0}^{M-1} \binom{k}{j} (-1)^{k-j}      (和の順番を入れ替えた)
//
// さらに
// \sum_{k=0}^{M-1} \binom{k}{j} (-1)^{k-j}
// = [x^j] \sum_{i=0}^{M-1} (x-1)^i
// = [x^j] ((x-1)^M - 1) / ((x-1)-1)
// なのでこの部分は計算できる。
// 
// [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;
  // (x-1)^M-1
  vector<mint> f(M + 2);
  for (int i = 0; i <= M; i++) {
    f[i] = C(M, i) * alt(M - i);
  }
  f[0] -= 1;

  // ((x-1)^M-1)/((x-1)-1)
  /*
  for (int i = M - 1; i >= 0; i--) {
    f[i + 1] += f[i];
    f[i] *= -mint(2);
  }
  */
  for (int i = 0; i <= M - 1; i++) {
    f[i] *= -I(2);
    f[i + 1] -= f[i];
  }
  // cout << f << endl;
  /*
  vector<mint> g(M);
  rep(i, M) {
    rep(k, M) {
      g[i] += C(k, i) * alt(k - i);
    }
  }
  cout << g << endl;
  */
  mint ans;
  rep(i, M) {
    ans += H(i, X) * H(i, Y) * H(i, Z) * f[i];
  }
  cout << ans << endl;
}
0