#344860 (C++17) No.829 成長関数インフレ中

提出ソース

結果

問題	No.829 成長関数インフレ中
ユーザー	kazuma
提出日時	2019-05-03 23:00:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	6,037 bytes
コンパイル時間	2,850 ms
コンパイル使用メモリ	227,236 KB
実行使用メモリ	37,864 KB
最終ジャッジ日時	2024-06-10 07:03:49
合計ジャッジ時間	7,480 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	26 ms 19,072 KB
testcase_01	AC	27 ms 19,072 KB
testcase_02	AC	26 ms 19,072 KB
testcase_03	AC	25 ms 19,072 KB
testcase_04	RE	-
testcase_05	AC	25 ms 19,200 KB
testcase_06	RE	-
testcase_07	AC	26 ms 19,072 KB
testcase_08	AC	24 ms 19,144 KB
testcase_09	AC	24 ms 18,944 KB
testcase_10	AC	26 ms 19,072 KB
testcase_11	AC	25 ms 18,944 KB
testcase_12	AC	54 ms 19,072 KB
testcase_13	AC	27 ms 19,072 KB
testcase_14	AC	46 ms 19,144 KB
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	AC	42 ms 19,072 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<int MOD>
struct mod_int {
	static const int mod = MOD;
	unsigned x;
	mod_int() : x(0) { }
	mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	mod_int &operator/=(mod_int that) { return *this *= that.inverse(); }

	mod_int operator+(mod_int that) const { return mod_int(*this) += that; }
	mod_int operator-(mod_int that) const { return mod_int(*this) -= that; }
	mod_int operator*(mod_int that) const { return mod_int(*this) *= that; }
	mod_int operator/(mod_int that) const { return mod_int(*this) /= that; }

	mod_int inverse() const {
		long long a = x, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		return mod_int(u);
	}
};

template<int MOD>
istream& operator >> (istream& is, mod_int<MOD>& val) {
	long long x;
	is >> x; val = x;
	return is;
}

template<int MOD>
ostream& operator << (ostream& os, const mod_int<MOD>& val) {
	os << val.get();
	return os;
}

const int mod = 1e9 + 7;
using mint = mod_int<mod>;

const int MAX = 2e6;

bool inited = false;
mint fac[MAX + 1];
mint rfac[MAX + 1];

void init() {
	inited = true;
	fac[0] = 1;
	for (int i = 1; i <= MAX; i++) {
		fac[i] = fac[i - 1] * i;
	}
	rfac[MAX] = fac[MAX].inverse();
	for (int i = MAX; i >= 1; i--) {
		rfac[i - 1] = rfac[i] * i;
	}
}

mint nPr(int n, int r) {
	if (!inited) init();
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r];
}

mint nCr(int n, int r) {
	if (!inited) init();
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r] * rfac[r];
}

mint nHr(int n, int r) {
	if (!inited) init();
	return r == 0 ? 1 : nCr(n + r - 1, r);
}

ll mod_inv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b > 0) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	return (u % m + m) % m;
}

ll garner(std::vector<ll> m, std::vector<ll> u, int md) {
	const int n = m.size();
	std::vector<ll> inv_prod(n);
	for (int i = 1; i < n; ++i) {
		ll prod = m[0] % m[i];
		for (int j = 1; j < i; ++j) {
			prod = (prod * m[j]) % m[i];
		}
		inv_prod[i] = mod_inv(prod, m[i]);
	}

	std::vector<ll> v(n);
	v[0] = u[0];
	for (int i = 1; i < n; ++i) {
		ll tmp = v[i - 1];
		for (int j = i - 2; j >= 0; --j) {
			tmp = (tmp * m[j] + v[j]) % m[i];
		}
		v[i] = ((u[i] - tmp) * inv_prod[i]) % m[i];
		if (v[i] < 0) v[i] += m[i];
	}

	ll res = v[n - 1];
	for (int i = n - 2; i >= 0; --i) {
		res = (res * m[i] + v[i]) % md;
	}
	return res;
}

ll mod_pow(ll x, ll n, int md) {
	ll res = 1;
	while (n) {
		if (n & 1) (res *= x) %= md;
		(x *= x) %= md; n >>= 1;
	}
	return res;
}

template <int Mod, int PrimitiveRoot>
class NTT {
public:
	// assertion: v.size() == 2 ^ m
	static std::vector<int> fft(std::vector<int> v, bool inv) {
		const int n = v.size();
		assert((n ^ (n & -n)) == 0);
		int ww = mod_pow(PrimitiveRoot, (Mod - 1) / n, Mod);
		if (inv) ww = mod_inv(ww, Mod);
		for (int m = n; m >= 2; m >>= 1) {
			const int mh = m >> 1;
			int w = 1;
			for (int i = 0; i < mh; ++i) {
				for (int j = i; j < n; j += m) {
					const int k = j + mh;
					int x = v[j] - v[k];
					if (x < 0) x += Mod;
					v[j] += -Mod + v[k];
					if (v[j] < 0) v[j] += Mod;
					v[k] = (1LL * w * x) % Mod;
				}
				w = (1LL * w * ww) % Mod;
			}
			ww = (1LL * ww * ww) % Mod;
		}

		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(v[i], v[j]);
		}
		if (inv) {
			const int inv_n = mod_inv(n, Mod);
			for (auto& x : v) {
				x = (1LL * x * inv_n) % Mod;
				assert(0 <= x && x < Mod);
			}
		}
		return v;
	}
	static std::vector<int> convolution(std::vector<int> f, std::vector<int> g) {
		int sz = 1;
		const int m = f.size() + g.size() - 1;
		while (sz < m) sz *= 2;
		f.resize(sz), g.resize(sz);
		f = NTT::fft(std::move(f), false); g = NTT::fft(std::move(g), false);
		for (int i = 0; i < sz; ++i) {
			f[i] = (1LL * f[i] * g[i]) % Mod;
		}

		return NTT::fft(std::move(f), true);
	}

	static int get_mod() {
		return Mod;
	}
};

using NTT_1 = NTT<167772161, 3>;  // 5 * 2^25 + 1
using NTT_2 = NTT<469762049, 3>;  // 7 * 2^26 + 1
using NTT_3 = NTT<1224736769, 3>; // 73 * 2^24 + 1

std::vector<int> mod_convolution(std::vector<int> f, std::vector<int> g, const int md) {
	for (auto& x : f) x %= md;
	for (auto& y : g) y %= md;
	const auto v1 = NTT_1::convolution(f, g);
	const auto v2 = NTT_2::convolution(f, g);
	const auto v3 = NTT_3::convolution(f, g);

	vector<int> res(v1.size());
	vector<ll> m = { NTT_1::get_mod(), NTT_2::get_mod(), NTT_3::get_mod() };
	for (int i = 0; i < (int)v1.size(); ++i) {
		vector<ll> u = { v1[i], v2[i], v3[i] };
		res[i] = garner(m, u, md);
	}

	return res;
}

vector<int> calc(int lb, int ub, const vector<vector<int>>& a) {
	if (ub - lb == 1) return a[lb];
	int m = (lb + ub) / 2;
	auto v1 = calc(lb, m, a);
	auto v2 = calc(m, ub, a);
	auto v = mod_convolution(v1, v2, mod);
	while (!v.empty() && v.back() == 0) v.pop_back();
	while (v.size() & (v.size() - 1)) v.push_back(0);
	return v;
}

int main()
{
	init();
	int N;
	mint B;
	cin >> N >> B;
	map<int, int> cnt;
	for (int i = 0; i < N; i++) {
		int S;
		cin >> S;
		cnt[S]++;
	}
	int size = N;
	vector<vector<int>> aa;
	for (auto p : cnt) {
		mint all = nCr(size, p.second) * fac[p.second];
		mint x0 = nCr(size - 1, p.second) * fac[p.second];
		vector<int> vec;
		vec.push_back(x0.get());
		vec.push_back(((all - x0) * B).get());
		aa.emplace_back(vec);
		size -= p.second;
	}
	auto v = calc(0, aa.size(), aa);
	mint res = 0;
	for (int i = 0; i < (int)v.size(); i++) {
		res += mint(v[i]) * i;
	}
	cout << res << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード