結果
| 問題 |
No.829 成長関数インフレ中
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2018-12-06 17:40:14 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,884 bytes |
| コンパイル時間 | 1,522 ms |
| コンパイル使用メモリ | 102,208 KB |
| 最終ジャッジ日時 | 2025-01-06 18:27:35 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 18 TLE * 4 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using ll = long long;
using ull = unsigned long long;
constexpr ll MOD = 1000000007;
constexpr int MAX = 200000;
int R[MAX];
ll fact[2 * MAX + 1];
ll inv[2 * MAX + 1];
constexpr std::size_t PC(ull v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<std::size_t>(v * 0x0101010101010101ULL >> 56 & 0x7f); }
constexpr std::size_t LG(ull v) { return v == 0 ? 0 : (v--, v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PC(v)); }
constexpr ull SZ(const ull v) { return 1ULL << LG(v); }
template <typename T>
constexpr std::pair<T, T> extgcd(const T a, const T b)
{
if (b == 0) { return std::pair<T, T>{1, 0}; }
const auto p = extgcd(b, a % b);
return {p.second, p.first - p.second * (a / b)};
}
template <typename T>
constexpr T inverse(const T a, const T mod = MOD) { return (mod + extgcd(a, mod).first % mod) % mod; }
template <typename T, T mod = 924844033, T root = 5>
class NumberTheoreticTransformation
{
public:
static std::vector<T> convolute(const std::vector<T>& a, const std::vector<T>& b) // ans[i] = \sum_{A+B = i} a[A]*b[B]
{
const std::size_t size = a.size() + b.size() - 1, t = (std::size_t)SZ(size);
std::vector<T> A(t, 0), B(t, 0);
for (std::size_t i = 0; i < a.size(); i++) { A[i] = a[i]; }
for (std::size_t i = 0; i < b.size(); i++) { B[i] = b[i]; }
ntt(A), ntt(B);
for (std::size_t i = 0; i < t; i++) { A[i] = mul(A[i], B[i]); }
ntt(A, true);
A.resize(size);
return A;
}
private:
NumberTheoreticTransformation() = delete;
static T add(const T x, const T y) { return (x + y < mod) ? x + y : x + y - mod; }
static T mul(const T x, const T y) { return (x * y) % mod; }
static T power(const T x, const T n) { return n == 0 ? (T)1 : n % 2 == 1 ? mul(power(x, n - 1), x) : power(mul(x, x), n / 2); }
static T inverse(const T x) { return power(x, mod - 2); }
static void ntt(std::vector<T>& a, const bool rev = false)
{
const std::size_t size = a.size(), height = LG(size);
for (std::size_t i = 0, j = 0; i < size; i++, j = 0) {
for (std::size_t k = 0; k < height; k++) { j |= (i >> k & 1) << (height - 1 - k); }
if (i < j) { std::swap(a[i], a[j]); }
}
for (std::size_t i = 1; i < size; i <<= 1) {
T w = power(root, (mod - 1) / (i * 2));
if (not rev) { w = inverse(w); }
for (std::size_t j = 0; j < size; j += i * 2) {
T wn = 1;
for (std::size_t k = 0; k < i; k++, wn = mul(wn, w)) {
const T s = a[j + k + 0], t = mul(a[j + k + i], wn);
a[j + k + 0] = add(s, t), a[j + k + i] = add(s, mod - t);
}
}
}
if (not rev) { return; }
const T v = inverse(size);
for (std::size_t i = 0; i < size; i++) { a[i] = mul(a[i], v); }
}
};
template <typename T>
class GarnerNumberTheoreticTransformation
{
public:
static std::vector<T> convolute(const std::vector<T>& a, const std::vector<T>& b, const T mod) // ans[i] = \sum_{A+B = i} a[A]*b[B]
{
const auto x = NTT1::convolute(a, b), y = NTT2::convolute(a, b), z = NTT3::convolute(a, b);
const std::size_t size = x.size();
std::vector<T> ans(size);
const T mod1mod2_mod = mod1 * mod2 % mod;
for (std::size_t i = 0; i < size; i++) {
T v1 = (y[i] - x[i]) * mod1_inv_mod2 % mod2;
if (v1 < 0) { v1 += mod2; }
T v2 = (z[i] - (x[i] + mod1 * v1) % mod3) * mod1mod2_inv_mod3 % mod3;
if (v2 < 0) { v2 += mod3; }
T c = (x[i] + mod1 * v1 + mod1mod2_mod * v2) % mod;
if (c < 0) { c += mod; }
ans[i] = c;
}
return ans;
}
private:
static constexpr T mod1 = 167772161;
static constexpr T mod2 = 469762049;
static constexpr T mod3 = 1224736769;
static constexpr T mod1_inv_mod2 = inverse(mod1, mod2);
static constexpr T mod1mod2_inv_mod3 = inverse(mod1 * mod2, mod3);
using NTT1 = NumberTheoreticTransformation<T, mod1, 3>;
using NTT2 = NumberTheoreticTransformation<T, mod2, 3>;
using NTT3 = NumberTheoreticTransformation<T, mod3, 3>;
GarnerNumberTheoreticTransformation() = delete;
};
int main()
{
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N;
ll P;
std::cin >> N >> P;
std::fill(fact, fact + 2 * MAX + 1, 1), std::fill(inv, inv + 2 * MAX + 1, 1);
for (ll i = 2; i <= 2 * N; i++) { fact[i] = (fact[i - 1] * i) % MOD, inv[i] = ((MOD - MOD / i) * inv[MOD % i]) % MOD; }
for (int i = 1; i <= 2 * N; i++) { (inv[i] *= inv[i - 1]) %= MOD; }
for (int i = 0, a; i < N; i++) { std::cin >> a, R[a]++; }
using FP = std::pair<int, std::vector<ll>>;
std::multiset<FP> fs{{{1, {1}}}};
for (int i = N - 1, k = 0; i >= 0; k += R[i], i--) {
const int r = R[i];
if (r == 0) { continue; }
const ll alpha = (r * fact[r + k - 1] % MOD) * inv[k] % MOD;
const ll beta = (k * fact[r + k - 1] % MOD) * inv[k] % MOD;
fs.insert({2, {beta, alpha}});
}
while (fs.size() > 1) {
const auto f1 = fs.begin()->second;
fs.erase(fs.begin());
const auto f2 = fs.begin()->second;
fs.erase(fs.begin());
const auto f3 = GarnerNumberTheoreticTransformation<ll>::convolute(f1, f2, MOD);
fs.insert({(int)f3.size(), f3});
}
const auto f = fs.begin()->second;
ll ans = 0;
for (ll i = 0, p = 1; i < f.size(); i++, (p *= P) %= MOD) { (ans += (p * i % MOD) * f[i] % MOD) %= MOD; }
std::cout << ans << std::endl;
}