結果

問題 No.829 成長関数インフレ中
ユーザー pekempeypekempey
提出日時 2019-05-03 23:12:25
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 703 ms / 2,000 ms
コード長 5,131 bytes
コンパイル時間 1,615 ms
コンパイル使用メモリ 96,704 KB
実行使用メモリ 61,892 KB
最終ジャッジ日時 2024-06-10 07:07:08
合計ジャッジ時間 5,783 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
38,892 KB
testcase_01 AC 44 ms
38,764 KB
testcase_02 AC 43 ms
38,888 KB
testcase_03 AC 43 ms
38,768 KB
testcase_04 AC 44 ms
38,764 KB
testcase_05 AC 44 ms
38,764 KB
testcase_06 AC 44 ms
38,760 KB
testcase_07 AC 44 ms
38,768 KB
testcase_08 AC 43 ms
38,888 KB
testcase_09 AC 42 ms
38,764 KB
testcase_10 AC 43 ms
38,760 KB
testcase_11 AC 43 ms
38,764 KB
testcase_12 AC 75 ms
39,276 KB
testcase_13 AC 46 ms
38,764 KB
testcase_14 AC 66 ms
39,020 KB
testcase_15 AC 186 ms
43,808 KB
testcase_16 AC 344 ms
48,540 KB
testcase_17 AC 439 ms
49,800 KB
testcase_18 AC 681 ms
61,892 KB
testcase_19 AC 472 ms
51,512 KB
testcase_20 AC 703 ms
59,204 KB
testcase_21 AC 62 ms
39,020 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

mint modpow(mint a, long long b) {
  mint res = 1;
  while (b > 0) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

mint F[200001] = {1, 1};
mint R[200001] = {1, 1};
mint I[200001] = {0, 1};

mint C(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return F[n] * R[n - r] * R[r];
}

void init() {
  for (int i = 2; i <= 200000; i++) {
    I[i] = I[MOD % i] * (MOD - MOD / i);
    F[i] = F[i - 1] * i;
    R[i] = R[i - 1] * I[i];
  }
}

mint modinv(mint a) {
  return modpow(a, MOD - 2);
}

template<int N>
struct FFT {
  complex<double> rots[N];

  FFT() {
    const double pi = acos(-1);
    for (int i = 0; i < N / 2; i++) {
      rots[i + N / 2].real(cos(2 * pi / N * i));
      rots[i + N / 2].imag(sin(2 * pi / N * i));
    }
    for (int i = N / 2 - 1; i >= 1; i--) {
      rots[i] = rots[i * 2];
    }
  }

  inline complex<double> mul(complex<double> a, complex<double> b) {
    return complex<double>(
        a.real() * b.real() - a.imag() * b.imag(),
        a.real() * b.imag() + a.imag() * b.real()
        );
  }

  void fft(vector<complex<double>> &a, bool rev) {
    const int n = a.size();
    int i = 0;
    for (int j = 1; j < n - 1; j++) {
      for (int k = n >> 1; k > (i ^= k); k >>= 1);
      if (j < i) {
        swap(a[i], a[j]);
      }
    }
    for (int i = 1; i < n; i *= 2) {
      for (int j = 0; j < n; j += i * 2) {
        for (int k = 0; k < i; k++) {
          auto s = a[j + k + 0];
          auto t = mul(a[j + k + i], rots[i + k]);
          a[j + k + 0] = s + t;
          a[j + k + i] = s - t;
        }
      }
    }
    if (rev) {
      reverse(a.begin() + 1, a.end());
      for (int i = 0; i < n; i++) {
        a[i] *= 1.0 / n;
      }
    }
  }

  vector<long long> convolution(vector<long long> a, vector<long long> b) {
    int t = 1;
    while (t < a.size() + b.size() - 1) t *= 2;
    vector<complex<double>> z(t);
    for (int i = 0; i < a.size(); i++) z[i].real(a[i]);
    for (int i = 0; i < b.size(); i++) z[i].imag(b[i]);
    fft(z, false);
    vector<complex<double>> w(t);
    for (int i = 0; i < t; i++) {
      auto p = (z[i] + conj(z[(t - i) % t])) * complex<double>(0.5, 0);
      auto q = (z[i] - conj(z[(t - i) % t])) * complex<double>(0, -0.5);
      w[i] = p * q;
    }
    fft(w, true);
    vector<long long> ans(a.size() + b.size() - 1);
    for (int i = 0; i < ans.size(); i++) {
      ans[i] = round(w[i].real());
    }
    return ans;
  }

  vector<mint> convolution(vector<mint> a, vector<mint> b) {
    int t = 1;
    while (t < a.size() + b.size() - 1) t *= 2;
    vector<complex<double>> A(t), B(t);
    for (int i = 0; i < a.size(); i++) A[i] = complex<double>(a[i].n & 0x7fff, a[i].n >> 15);
    for (int i = 0; i < b.size(); i++) B[i] = complex<double>(b[i].n & 0x7fff, b[i].n >> 15);
    fft(A, false);
    fft(B, false);
    vector<complex<double>> C(t), D(t);
    for (int i = 0; i < t; i++) {
      int j = (t - i) % t;
      auto AL = (A[i] + conj(A[j])) * complex<double>(0.5, 0);
      auto AH = (A[i] - conj(A[j])) * complex<double>(0, -0.5);
      auto BL = (B[i] + conj(B[j])) * complex<double>(0.5, 0);
      auto BH = (B[i] - conj(B[j])) * complex<double>(0, -0.5);
      C[i] = AL * BL + AH * BL * complex<double>(0, 1);
      D[i] = AL * BH + AH * BH * complex<double>(0, 1);
    }
    fft(C, true);
    fft(D, true);
    vector<mint> ans(a.size() + b.size() - 1);
    for (int i = 0; i < ans.size(); i++) {
      long long l = (long long)round(C[i].real()) % MOD;
      long long m = ((long long)round(C[i].imag()) + (long long)round(D[i].real())) % MOD;
      long long h = (long long)round(D[i].imag()) % MOD;
      ans[i] = (l + (m << 15) + (h << 30)) % MOD;
    }
    return ans;
  }
};
FFT<1 << 21> fft;

vector<mint> prod(const vector<mint> &A, const vector<mint> &B, int l, int r) {
  if (r - l == 1) return {A[l], B[l]};
  int m = (l + r) / 2;
  auto vl = prod(A, B, l, m);
  auto vr = prod(A, B, m, r);
  return fft.convolution(vl, vr);
}

int main() {
  init();
  int N, R;
  cin >> N >> R;
  vector<int> S(N);
  REP(i, N) cin >> S[i];
  sort(S.rbegin(), S.rend());
  int i = 0;
  vector<mint> A, B;
  while (i < N) {
    int j = i;
    while (i < N && S[i] == S[j]) i++;
    A.push_back(F[i - j] * C(i-j + j-1, i-j));
    B.push_back(F[i - j] * C(i-j-1 + j, j));
  }
  vector<mint> f = prod(A, B, 0, A.size());
  mint ans = 0;
  for (int i = 0; i < f.size(); i++) {
    ans += f[i] * i * modpow(R, i);
  }
  cout << ans.n << '\n';
}
0