#324878 (C++14) No.802 だいたい等差数列

提出ソース

結果

問題	No.802 だいたい等差数列
ユーザー	square1001
提出日時	2019-03-17 22:03:00
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	7,035 bytes
コンパイル時間	1,825 ms
コンパイル使用メモリ	102,992 KB
実行使用メモリ	94,328 KB
最終ジャッジ日時	2024-07-07 22:55:21
合計ジャッジ時間	7,707 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	332 ms 10,624 KB
testcase_01	AC	107 ms 5,376 KB
testcase_02	AC	378 ms 5,376 KB
testcase_03	AC	85 ms 5,376 KB
testcase_04	AC	178 ms 5,376 KB
testcase_05	AC	257 ms 5,376 KB
testcase_06	AC	180 ms 5,376 KB
testcase_07	AC	75 ms 5,376 KB
testcase_08	AC	311 ms 5,376 KB
testcase_09	AC	180 ms 5,376 KB
testcase_10	TLE	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-

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

ソースコード

raw source code

#ifndef ___CLASS_MODINT
#define ___CLASS_MODINT

#include <vector>
#include <cstdint>

using singlebit = uint32_t;
using doublebit = uint64_t;

static constexpr singlebit find_inv(singlebit n, int d = 5, singlebit x = 1) {
	return d == 0 ? x : find_inv(n, d - 1, x * (2 - x * n));
}
template <singlebit mod, singlebit primroot> class modint {
	// Fast Modulo Integer, Assertion: mod < 2^31
private:
	singlebit n;
	static constexpr int level = 32; // LIMIT OF singlebit
	static constexpr singlebit max_value = -1;
	static constexpr singlebit r2 = (((1ull << level) % mod) << level) % mod;
	static constexpr singlebit inv = singlebit(-1) * find_inv(mod);
	static singlebit reduce(doublebit x) {
		singlebit res = (x + doublebit(singlebit(x) * inv) * mod) >> level;
		return res < mod ? res : res - mod;
	}
public:
	modint() : n(0) {};
	modint(singlebit n_) { n = reduce(doublebit(n_) * r2); };
	modint& operator=(const singlebit x) { n = reduce(doublebit(x) * r2); return *this; }
	bool operator==(const modint& x) const { return n == x.n; }
	bool operator!=(const modint& x) const { return n != x.n; }
	modint& operator+=(const modint& x) { n += x.n; n -= (n < mod ? 0 : mod); return *this; }
	modint& operator-=(const modint& x) { n += mod - x.n; n -= (n < mod ? 0 : mod); return *this; }
	modint& operator*=(const modint& x) { n = reduce(1ull * n * x.n); return *this; }
	modint operator+(const modint& x) const { return modint(*this) += x; }
	modint operator-(const modint& x) const { return modint(*this) -= x; }
	modint operator*(const modint& x) const { return modint(*this) *= x; }
	static singlebit get_mod() { return mod; }
	static singlebit get_primroot() { return primroot; }
	singlebit get() { return reduce(doublebit(n)); }
	modint binpow(singlebit b) {
		modint ans(1), cur(*this);
		while (b > 0) {
			if (b & 1) ans *= cur;
			cur *= cur;
			b >>= 1;
		}
		return ans;
	}
};

template<typename modulo>
std::vector<modulo> get_modvector(std::vector<int> v) {
	std::vector<modulo> ans(v.size());
	for (int i = 0; i < v.size(); ++i) {
		ans[i] = v[i];
	}
	return ans;
}

#endif

#ifndef ___CLASS_NTT
#define ___CLASS_NTT

#include <vector>

template<typename modulo>
class ntt {
	// Number Theoretic Transform
private:
	int depth;
	std::vector<modulo> roots;
	std::vector<modulo> powinv;
public:
	ntt() {
		depth = 0;
		uint32_t div_number = modulo::get_mod() - 1;
		while (div_number % 2 == 0) div_number >>= 1, ++depth;
		modulo b = modulo::get_primroot();
		for (int i = 0; i < depth; ++i) b *= b;
		modulo baseroot = modulo::get_primroot(), bb = b;
		while (bb != 1) bb *= b, baseroot *= modulo::get_primroot();
		roots = std::vector<modulo>(depth + 1, 0);
		powinv = std::vector<modulo>(depth + 1, 0);
		powinv[1] = (modulo::get_mod() + 1) / 2;
		for (int i = 2; i <= depth; ++i) powinv[i] = powinv[i - 1] * powinv[1];
		roots[depth] = 1;
		for (int i = 0; i < modulo::get_mod() - 1; i += 1 << depth) roots[depth] *= baseroot;
		for (int i = depth - 1; i >= 1; --i) roots[i] = roots[i + 1] * roots[i + 1];
	}
	void fourier_transform(std::vector<modulo> &v, bool inverse) {
		int s = v.size();
		for (int i = 0, j = 1; j < s - 1; ++j) {
			for (int k = s >> 1; k >(i ^= k); k >>= 1);
			if (i < j) std::swap(v[i], v[j]);
		}
		int sc = 0, sz = 1;
		while (sz < s) sz *= 2, ++sc;
		std::vector<modulo> pw(s + 1); pw[0] = 1;
		for (int i = 1; i <= s; i++) pw[i] = pw[i - 1] * roots[sc];
		int qs = s;
		for (int b = 1; b < s; b <<= 1) {
			qs >>= 1;
			for (int i = 0; i < s; i += b * 2) {
				for (int j = i; j < i + b; ++j) {
					modulo delta = pw[(inverse ? b * 2 - j + i : j - i) * qs] * v[j + b];
					v[j + b] = v[j] - delta;
					v[j] += delta;
				}
			}
		}
		if (inverse) {
			for (int i = 0; i < s; ++i) v[i] *= powinv[sc];
		}
	}
	std::vector<modulo> convolve(std::vector<modulo> v1, std::vector<modulo> v2) {
		const int threshold = 16;
		if (v1.size() < v2.size()) swap(v1, v2);
		int s1 = 1; while (s1 < v1.size()) s1 <<= 1; v1.resize(s1);
		int s2 = 1; while (s2 < v2.size()) s2 <<= 1; v2.resize(s2 * 2);
		std::vector<modulo> ans(s1 + s2);
		if (s2 <= threshold) {
			for (int i = 0; i < s1; ++i) {
				for (int j = 0; j < s2; ++j) {
					ans[i + j] += v1[i] * v2[j];
				}
			}
		}
		else {
			fourier_transform(v2, false);
			for (int i = 0; i < s1; i += s2) {
				std::vector<modulo> v(v1.begin() + i, v1.begin() + i + s2);
				v.resize(s2 * 2);
				fourier_transform(v, false);
				for (int j = 0; j < v.size(); ++j) v[j] *= v2[j];
				fourier_transform(v, true);
				for (int j = 0; j < s2 * 2; ++j) {
					ans[i + j] += v[j];
				}
			}
		}
		return ans;
	}
};

#endif

#include <vector>
#include <iostream>
using namespace std;

using modulo1 = modint<469762049, 3>; ntt<modulo1> ntt_base1;
using modulo2 = modint<167772161, 3>; ntt<modulo2> ntt_base2;
using modulo3 = modint<998244353, 3>; ntt<modulo3> ntt_base3;

const modulo1 magic_inv = modulo1(modulo2::get_mod()).binpow(modulo1::get_mod() - 2);

const int mod = 1000000007;

int binpow(int a, int b, int p) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = (long long)(ans) * a % p;
		a = (long long)(a) * a % p;
		b >>= 1;
	}
	return ans;
}

// Garner: Thanks to https://math314.hateblo.jp/entry/2015/05/07/014908
long long garner(vector<pair<int, int> > mr, int mod) {
	mr.emplace_back(mod, 0);

	vector<long long> coffs(mr.size(), 1);
	vector<long long> constants(mr.size(), 0);
	for (int i = 0; i < mr.size() - 1; ++i) {
		// coffs[i] * v + constants[i] == mr[i].second (mod mr[i].first) を解く
		long long v = (mr[i].second - constants[i]) * binpow(coffs[i] % mr[i].first, mr[i].first - 2, mr[i].first) % mr[i].first;
		if (v < 0) v += mr[i].first;

		for (int j = i + 1; j < mr.size(); j++) {
			(constants[j] += coffs[j] * v) %= mr[j].first;
			(coffs[j] *= mr[i].first) %= mr[j].first;
		}
	}

	return constants[mr.size() - 1];
}

vector<int> convolve_mod(vector<int> v1, vector<int> v2) {
	vector<modulo1> mul_base1 = ntt_base1.convolve(get_modvector<modulo1>(v1), get_modvector<modulo1>(v2));
	vector<modulo2> mul_base2 = ntt_base2.convolve(get_modvector<modulo2>(v1), get_modvector<modulo2>(v2));
	vector<modulo3> mul_base3 = ntt_base3.convolve(get_modvector<modulo3>(v1), get_modvector<modulo3>(v2));
	vector<int> ans(mul_base1.size());
	for (int i = 0; i < mul_base1.size(); ++i) {
		vector<pair<int, int> > vec = {
			make_pair(modulo1::get_mod(), mul_base1[i].get()),
			make_pair(modulo2::get_mod(), mul_base2[i].get()),
			make_pair(modulo3::get_mod(), mul_base3[i].get())
		};
		long long val = garner(vec, mod);
		ans[i] = val % mod;
	}
	return ans;
}

int main() {
	int N, M, D1, D2;
	cin >> N >> M >> D1 >> D2;
	vector<int> cur(M); cur[0] = 1;
	vector<int> pw(M);
	for (int i = D1; i <= D2; ++i) {
		if (0 <= i && i < M) pw[i] = 1;
	}
	--N;
	while (N) {
		if (N & 1) {
			cur = convolve_mod(cur, pw);
			cur.resize(M);
		}
		pw = convolve_mod(pw, pw);
		pw.resize(M);
		N >>= 1;
	}
	int ans = 0;
	for (int i = 0; i < M; ++i) {
		ans = (ans + (long long)(cur[i]) * (M - i)) % mod;
	}
	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード