#592023 (C++17) No.1321 塗るめた

提出ソース

結果

問題	No.1321 塗るめた
ユーザー	polylogK
提出日時	2020-12-11 06:18:24
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	475 ms / 2,000 ms
コード長	15,098 bytes
コンパイル時間	3,436 ms
コンパイル使用メモリ	234,544 KB
実行使用メモリ	32,232 KB
最終ジャッジ日時	2024-09-19 21:14:38
合計ジャッジ時間	16,375 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	14 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	239 ms 18,888 KB
testcase_13	AC	461 ms 30,816 KB
testcase_14	AC	220 ms 16,768 KB
testcase_15	AC	227 ms 17,548 KB
testcase_16	AC	239 ms 18,508 KB
testcase_17	AC	14 ms 6,944 KB
testcase_18	AC	473 ms 31,132 KB
testcase_19	AC	116 ms 10,928 KB
testcase_20	AC	222 ms 16,848 KB
testcase_21	AC	465 ms 30,312 KB
testcase_22	AC	472 ms 31,856 KB
testcase_23	AC	472 ms 31,588 KB
testcase_24	AC	473 ms 31,716 KB
testcase_25	AC	473 ms 31,452 KB
testcase_26	AC	472 ms 32,232 KB
testcase_27	AC	473 ms 31,852 KB
testcase_28	AC	468 ms 31,460 KB
testcase_29	AC	474 ms 31,848 KB
testcase_30	AC	471 ms 31,728 KB
testcase_31	AC	470 ms 31,724 KB
testcase_32	AC	236 ms 18,888 KB
testcase_33	AC	220 ms 16,412 KB
testcase_34	AC	237 ms 18,892 KB
testcase_35	AC	220 ms 16,544 KB
testcase_36	AC	467 ms 31,592 KB
testcase_37	AC	470 ms 31,600 KB
testcase_38	AC	470 ms 31,844 KB
testcase_39	AC	470 ms 32,228 KB
testcase_40	AC	475 ms 31,588 KB
testcase_41	AC	471 ms 31,580 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	238 ms 19,020 KB
testcase_44	AC	221 ms 16,420 KB
testcase_45	AC	239 ms 19,016 KB
testcase_46	AC	56 ms 6,968 KB

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

ソースコード

raw source code

#line 1 "main.cpp"
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/math/number_theoritic_transform.hpp"



#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/math/modint.hpp"



#line 5 "/home/ecasdqina/cpcpp/libs/library_cpp/math/modint.hpp"

namespace cplib {
template <std::uint_fast64_t Modulus>
class modint {
	using u32 = std::uint_fast32_t;
	using u64 = std::uint_fast64_t;
	using i32 = std::int_fast32_t;
	using i64 = std::int_fast64_t;

	inline u64 apply(i64 x) { return (x < 0 ? x + Modulus : x); };

public:
	u64 a;
	static constexpr u64 mod = Modulus;

	constexpr modint(const i64& x = 0) noexcept: a(apply(x % (i64)Modulus)) {}

	constexpr modint operator+(const modint& rhs) const noexcept { return modint(*this) += rhs; }
	constexpr modint operator-(const modint& rhs) const noexcept { return modint(*this) -= rhs; }
	constexpr modint operator*(const modint& rhs) const noexcept { return modint(*this) *= rhs; }
	constexpr modint operator/(const modint& rhs) const noexcept { return modint(*this) /= rhs; }
	constexpr modint operator^(const u64& k) const noexcept { return modint(*this) ^= k; }
	constexpr modint operator^(const modint& k) const noexcept { return modint(*this) ^= k.value(); }
	constexpr modint operator-() const noexcept { return modint(Modulus - a); }
	constexpr modint operator++() noexcept { return (*this) = modint(*this) + 1; }
	constexpr modint operator--() noexcept { return (*this) = modint(*this) - 1; }
	const bool operator==(const modint& rhs) const noexcept { return a == rhs.a; };
	const bool operator!=(const modint& rhs) const noexcept { return a != rhs.a; };
	const bool operator<=(const modint& rhs) const noexcept { return a <= rhs.a; };
	const bool operator>=(const modint& rhs) const noexcept { return a >= rhs.a; };
	const bool operator<(const modint& rhs) const noexcept { return a < rhs.a; };
	const bool operator>(const modint& rhs) const noexcept { return a > rhs.a; };
	constexpr modint& operator+=(const modint& rhs) noexcept {
		a += rhs.a;
		if (a >= Modulus) a -= Modulus;
		return *this;
	}
	constexpr modint& operator-=(const modint& rhs) noexcept {
		if (a < rhs.a) a += Modulus;
		a -= rhs.a;
		return *this;
	}
	constexpr modint& operator*=(const modint& rhs) noexcept {
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint& operator/=(modint rhs) noexcept {
		u64 exp = Modulus - 2;
		while (exp) {
			if (exp % 2) (*this) *= rhs;

			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}
	constexpr modint& operator^=(u64 k) noexcept {
		auto b = modint(1);
		while(k) {
			if(k & 1) b = b * (*this);
			(*this) *= (*this);
			k >>= 1;
		}
		return (*this) = b;
	}
	constexpr modint& operator=(const modint& rhs) noexcept {
		a = rhs.a;
		return (*this);
	}

	const modint inverse() const {
		return modint(1) / *this;
	}
	const modint power(i64 k) const {
		if(k < 0) return modint(*this).inverse() ^ (-k);
		return modint(*this) ^ k;
	}

	explicit operator bool() const { return a; }
	explicit operator u64() const { return a; }
	constexpr u64& value() noexcept { return a; }
	constexpr const u64& value() const noexcept { return a; }

	friend std::ostream& operator<<(std::ostream& os, const modint& p) {
		return os << p.a;
	}
	friend std::istream& operator>>(std::istream& is, modint& p) {
		u64 t;
		is >> t;
		p = modint(t);
		return is;
	}
};
}


#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/math/polynomial.hpp"



#line 8 "/home/ecasdqina/cpcpp/libs/library_cpp/math/polynomial.hpp"

namespace cplib {
template<class T>
class polynomial: public std::vector<T> {
public:
	using std::vector<T>::vector;
	using value_type = typename std::vector<T>::value_type;
	using reference = typename std::vector<T>::reference;
	using const_reference = typename std::vector<T>::const_reference;
	using size_type = typename std::vector<T>::size_type;

public:
	polynomial(const std::vector<T>& r): std::vector<T>(r) {}
	polynomial(size_t size, std::function<T(size_t)> f): std::vector<T>(size) {
		for(size_t i = 0; i < size; i++) (*this)[i] = f(i);
	}

	polynomial operator+(const polynomial& r) const { return polynomial(*this) += r; }
	polynomial operator+(const_reference r) const { return polynomial(*this) += r; }
	friend polynomial operator+(const_reference l, polynomial r) { return r += l; }
	polynomial operator-(const polynomial& r) const { return polynomial(*this) -= r; }
	polynomial operator-(const_reference r) const { return polynomial(*this) -= r; }
	friend polynomial operator-(const_reference l, polynomial r) { return r -= l; }
	polynomial operator*(const_reference r) const { return polynomial(*this) *= r; }
	friend polynomial operator*(const_reference l, polynomial r) { return r *= l; }
	polynomial operator*(const polynomial& r) const { return polynomial(*this) *= r; }
	polynomial operator/(const_reference r) const { return polynomial(*this) /= r; }
	polynomial operator<<(size_type r) const { return polynomial(*this) <<= r; }
	polynomial operator>>(size_type r) const { return polynomial(*this) >>= r; }
	polynomial operator-() const {
		polynomial ret(this->size());
		for(size_t i = 0; i < this->size(); i++) ret[i] = -(*this)[i];
		return ret;
	}
	polynomial& operator+=(const polynomial& r) {
		if(r.size() > this->size()) this->resize(r.size());
		for(size_t i = 0; i < r.size(); i++) (*this)[i] = (*this)[i] + r[i];
		return *this;
	}
	polynomial& operator+=(const_reference r) {
		if(this->empty()) this->push_back(T{});
		(*this)[0] += r;
		return *this;
	}
	polynomial& operator-=(const polynomial& r) {
		if(r.size() > this->size()) this->resize(r.size());
		for(size_t i = 0; i < r.size(); i++) (*this)[i] = (*this)[i] - r[i];
		return *this;
	}
	polynomial& operator-=(const_reference r) {
		if(this->empty()) this->push_back(T{});
		(*this)[0] -= r;
		return *this;
	}
	polynomial& operator*=(const_reference r) {
		for(size_t i = 0; i < this->size(); i++) (*this)[i] = (*this)[i] * r;
		return *this;
	}
	polynomial& operator/=(const_reference r) {
		for(size_t i = 0; i < this->size(); i++) (*this)[i] = (*this)[i] / r;
		return *this;
	}
	polynomial& operator<<=(size_type r) {
		this->insert(begin(*this), r, T{});
		return *this;
	}
	polynomial& operator>>=(size_type r) {
		if(r >= this->size()) this->clear();
		else this->erase(begin(*this), begin(*this) + r);
		return *this;
	}
	polynomial& operator*=(const polynomial& r) {
		polynomial ret(this->degree() + r.degree() + 1);
		for(size_t i = 0; i < this->size(); i++) {
			if((*this)[i] == T{}) continue;
			for(size_t j = 0; j < r.size(); j++) ret[i + j] += (*this)[i] * r[j];
		}
		return *this = std::move(ret);
	};

	polynomial differential(size_type k) const {
		polynomial ret(*this);
		for(size_t i = 0; i < k; i++) ret = ret.differential();
		return ret;
	}
	polynomial differential() const {
		if(degree() < 1) return polynomial();
		polynomial ret(this->size() - 1);
		for(size_t i = 1; i < this->size(); i++) ret[i - 1] = (*this)[i] * T(i);
		return ret;
	}
	polynomial integral(size_type k) const {
		polynomial ret(*this);
		for(size_t i = 0; i < k; i++) ret = ret.integral();
		return ret;
	}
	polynomial integral() const {
		polynomial ret(this->size() + 1);
		for(size_t i = 0; i < this->size(); i++) ret[i + 1] = (*this)[i] / T(i + 1);
		return ret;
	}
	polynomial prefix(size_type size) const {
		return polynomial(begin(*this), begin(*this) + std::min(this->size(), size));
	}
	void shrink() {
		while(!this->empty() and this->back() == T{}) this->pop_back();
	}

public:
	polynomial sparse_convex(const polynomial& r) const {
		if(this->nonzeros() < r.nonzeros()) return (*this) * r;
		return r * (*this);
	}
	size_type degree() const { return std::max<size_type>(1, this->size()) - 1; }
	size_type nonzeros() const {
		size_type ret = 0;
		for(size_t i = 0; i < this->size(); i++) {
			if((*this)[i] != T{}) ret++;
		}
		return ret;
	}
	T operator()(T x) const { return eval(x); }
	T eval(T x) const {
		T ret = (*this)[0], tmp = x;
		for(size_t i = 1; i < this->size(); i++) {
			ret = ret + (*this)[i] * tmp;
			tmp = tmp * x;
		}
		return ret;
	}

	static polynomial<T> one() { return term(0); }
	static polynomial<T> zero() { return polynomial<T>({T{0}}); }
	static polynomial<T> term(int k) { return polynomial<T>({T{1}}) << k; }
};

template<class T> T convex_all(std::vector<T> polies, int size = -1) {
	if(polies.empty()) return T::zero();

	std::deque<int> qu;
	for(int i = 0; i < polies.size(); i++) qu.push_back(i);
	while(qu.size() > 1) {
		int a = qu.front(); qu.pop_front();
		int b = qu.front(); qu.pop_front();

		polies.push_back(polies[a] * polies[b]);
		if(size != -1) polies.back().resize(size);
		qu.push_back((int)polies.size() - 1);
	}
	return polies.back();
}
}


#line 7 "/home/ecasdqina/cpcpp/libs/library_cpp/math/number_theoritic_transform.hpp"

namespace cplib {
template<std::uint_fast64_t MOD,
	int primitive_root = 3,
	class T = modint<MOD>>
class number_theoritic_transform: public polynomial<T> {
public:
	using polynomial<T>::polynomial;
	using value_type 	  = typename polynomial<T>::value_type;
	using reference 	  = typename polynomial<T>::reference;
	using const_reference = typename polynomial<T>::const_reference;
	using size_type 	  = typename polynomial<T>::size_type;

public:
	number_theoritic_transform(const polynomial<T>& p): polynomial<T>(p) {}

protected:
	static void ntt(number_theoritic_transform& a) {
		size_t N = a.size();
		static std::vector<T> dw;
		if(dw.size() < N) {
			int n = dw.size();
			dw.resize(N);
			for(size_t i = n; i < N; i++) dw[i] = -(T(primitive_root) ^ ((T::mod - 1) >> (i + 2)));
		}

		for(size_t m = N; m >>= 1;) {
			T w = 1;
			for(size_t s = 0, k = 0; s < N; s += 2 * m) {
				for(size_t i = s, j = s + m; i < s + m; i++, j++) {
					T x = a[i], y = a[j] * w;
					a[i] = x + y;
					a[j] = x - y;
				}
				w *= dw[__builtin_ctz(++k)];
			}
		}
	}
	static void intt(number_theoritic_transform& a) {
		size_t N = a.size();
		static std::vector<T> idw;
		if(idw.size() < N) {
			size_t n = idw.size();
			idw.resize(N);
			for(size_t i = n; i < N; i++) idw[i] = (-(T(primitive_root) ^ ((T::mod - 1) >> (i + 2)))).inverse();
		}

		for(size_t m = 1; m < N; m *= 2) {
			T w = 1;
			for(size_t s = 0, k = 0; s < N; s += 2 * m) {
				for(size_t i = s, j = s + m; i < s + m; i++, j++) {
					T x = a[i], y = a[j];
					a[i] = x + y;
					a[j] = (x - y) * w;
				}
				w *= idw[__builtin_ctz(++k)];
			}
		}
	}
	static void transform(number_theoritic_transform& a, bool inverse = false) {
		size_type n = 0;
		while((1ul << n) < a.size()) n++;
		size_type N = 1 << n;
		a.resize(N);

		if(!inverse) {
			ntt(a);
		} else {
			intt(a);
			T inv = T(N).inverse();
			for(size_t i = 0; i < a.size(); i++) a[i] *= inv;
		}
	}

	static number_theoritic_transform convolution(const number_theoritic_transform& ar, const number_theoritic_transform& br) {
		size_type size = ar.degree() + br.degree() + 1;
		number_theoritic_transform a(ar), b(br);
		a.resize(size);
		b.resize(size);

		transform(a, false);
		transform(b, false);

		for(size_t i = 0; i < a.size(); i++) a[i] *= b[i];
		transform(a, true);
		a.resize(size);
		return a;
	}

public:
	number_theoritic_transform convex(const number_theoritic_transform& r) const { return (*this) * r; }
	number_theoritic_transform operator*(const number_theoritic_transform& r) const { return number_theoritic_transform(*this) *= r; }
	number_theoritic_transform& operator*=(const number_theoritic_transform& r) {
		return (*this) = convolution((*this), r);
	}
	number_theoritic_transform operator*(const_reference r) const { return number_theoritic_transform(*this) *= r; }
	number_theoritic_transform& operator*=(const_reference r) {
		for(size_t i = 0; i < this->size(); i++) (*this)[i] = (*this)[i] * r;
		return *this;
	}

};
}
// @docs docs/number_theoritic_transform.md


#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/math/formal_power_series.hpp"



#line 8 "/home/ecasdqina/cpcpp/libs/library_cpp/math/formal_power_series.hpp"

namespace cplib {
template<class T>
class formal_power_series: public T {
public:
	using T::T;
	using value_type = typename T::value_type;
	using reference = typename T::reference;
	using const_reference = typename T::const_reference;
	using size_type = typename T::size_type;

	using i64 = std::int_fast64_t;

public:
	formal_power_series(const T& p): T(p) {}

public:
	formal_power_series inverse() const {
		assert((*this)[0] != value_type{});
		formal_power_series ret(1, (*this)[0].inverse());
		for(size_t i = 1; i < this->size(); i <<= 1) {
			auto tmp = T::convolution(ret, this->prefix(i << 1));
			for(size_t j = 0; j < i; j++) {
				tmp[j] = value_type{};
				if(j + i < tmp.size()) tmp[j + i] *= value_type(-1);
			}
			tmp = tmp * ret;
			for(size_t j = 0; j < i; j++) tmp[j] = ret[j];
			ret = std::move(tmp).prefix(i << 1);
		}
		return ret.prefix(this->size());
	}
	formal_power_series log() const {
		assert((*this)[0] == value_type(1));

		return (formal_power_series(this->differential()) * this->inverse()).integral().prefix(this->size());
	}
	formal_power_series exp() const {
		assert((*this)[0] == value_type{});

		formal_power_series f(1, value_type(1)), g(1, value_type(1));
		for(size_t i = 1; i < this->size(); i <<= 1) {
			g = (g * value_type(2) - f * g * g).prefix(i);
			formal_power_series q = this->differential().prefix(i - 1);
			formal_power_series w = (q + g * (f.differential() - f * q)).prefix((i << 1) - 1);
			f = (f + f * (*this - w.integral()).prefix(i << 1)).prefix(i << 1);

		}
		return f.prefix(this->size());
	}
	formal_power_series power(i64 k) const {
		if(k < 0) return this->inverse().power(-k);
		for(size_type i = 0; i < this->size(); i++) {
			if((*this)[i] != value_type{}) {
				value_type inv = (*this)[i].inverse();
				formal_power_series f(*this * inv);
				formal_power_series g(f >> i);
				g = formal_power_series(g.log() * value_type(k)).exp() * (*this)[i].power(k);
				if(i * k > this->size()) return formal_power_series(this->size());

				return (g << (i * k)).prefix(this->size());
			}
		}
		return *this;
	}

public:
	formal_power_series convex(const formal_power_series& r) const { return ((*this) * r).prefix(this->size()); }
};
}

// @docs docs/formal_power_series.md


#line 11 "main.cpp"
using ntt = cplib::number_theoritic_transform<998244353>;
using fps = cplib::formal_power_series<ntt>;
using mint = ntt::value_type;

int main() {
	int n, m, k; scanf("%d%d%d", &n, &m, &k);

	std::vector<mint> fact(n + 1, 1);
	for(int i = 0; i < n; i++) fact[i + 1] = fact[i] * (i + 1);
	auto comb = [&](int n, int r) { return fact[n] / fact[r] / fact[n - r]; };

	fps f(n + 1); f[0] = 1;
	for(int i = 0; i < n; i++) f[i + 1] = f[i] * mint(m) / mint(i + 1); // f = e^(yM)

	fps g(n + 1); g[0] = 1;
	for(int i = 0; i < n; i++) g[i + 1] = g[i] / mint(i + 1); // g = e^y
	g = fps(g - 1).power(k); // g = (e^y - 1) ^ K

	fps h = f.convex(g);
	printf("%lld\n", (comb(m, k) * fact[n] * h[n]).value());
	return 0;
}

yukicoder

結果

テストケース

ソースコード