#672139 (C++17) No.1581 Multiple Sequence

提出ソース

結果

問題	No.1581 Multiple Sequence
ユーザー	Ebishu
提出日時	2021-07-02 21:52:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	82 ms / 2,000 ms
コード長	10,506 bytes
コンパイル時間	4,021 ms
コンパイル使用メモリ	193,436 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-29 11:24:17
合計ジャッジ時間	5,718 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	63 ms 5,376 KB
testcase_03	AC	70 ms 5,376 KB
testcase_04	AC	17 ms 5,376 KB
testcase_05	AC	75 ms 5,376 KB
testcase_06	AC	30 ms 5,376 KB
testcase_07	AC	16 ms 5,376 KB
testcase_08	AC	22 ms 5,376 KB
testcase_09	AC	66 ms 5,376 KB
testcase_10	AC	40 ms 5,376 KB
testcase_11	AC	8 ms 5,376 KB
testcase_12	AC	24 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	71 ms 5,376 KB
testcase_15	AC	48 ms 5,376 KB
testcase_16	AC	11 ms 5,376 KB
testcase_17	AC	80 ms 5,376 KB
testcase_18	AC	7 ms 5,376 KB
testcase_19	AC	61 ms 5,376 KB
testcase_20	AC	64 ms 5,376 KB
testcase_21	AC	70 ms 5,376 KB
testcase_22	AC	36 ms 5,376 KB
testcase_23	AC	82 ms 5,376 KB

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

ソースコード

raw source code

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using lint = long long;
using P = pair<lint, lint>;

#define rep(i, n) for (lint i = 0; i < (lint)(n); ++i)
#define rep1(i, n) for (lint i = 1; i < (lint)(n); ++i)
#define repn(i, a, b) for(lint i = (a); i < (lint)(b); ++i)
#define rep_inv(i, n) for (lint i = (n); i >= 0; --i)
#define all(vec) (vec).begin(), (vec).end()

constexpr lint Mod = /**/ 1000'000'007LL /*/ 998244353LL /**/;
constexpr lint Inf = 1'000'000'000'000'000'010LL;
constexpr int IntInf = 1000'000'010;
constexpr double Pi = 3.141592653589793238;
constexpr double InvPi = 0.318309886183790671;

const int di[4] = { 0,1,0,-1 }, dj[4] = { 1,0,-1,0 };

#if __has_include(<atcoder/all>)
#include <atcoder/all>

using namespace atcoder;
using mint = static_modint<Mod>;

inline istream& operator>>(istream & is, mint & rhs) {
	long long tmp;
	is >> tmp;
	rhs = tmp;
	return is;
}

inline ostream& operator<<(ostream & os, const mint & rhs) { return os << rhs.val(); }
#endif

template<typename T> using prique     = priority_queue<T>;
template<typename T> using prique_inv = priority_queue<T, vector<T>, greater<T>>;
template<typename T> inline istream& operator>>(istream& is, vector<T>& v) { for (auto&& e : v) is >> e; return is; }
template<typename T> inline istream& operator>>(istream& is, complex<T>& c) {
	double real, imag;
	is >> real >> imag;
	c.real(real);
	c.imag(imag);
	return is;
}
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) {
	size_t i = 0, n = v.size();
	for (const auto& e : v) {
		os << e;
		if (++i < n) os << " ";
	}
	return os;
}
template<typename T, typename U> inline bool chmin(T& a, const U b) { return a > b ? a = b, true : false; }
template<typename T, typename U> inline bool chmax(T& a, const U b) { return a < b ? a = b, true : false; }
template<typename T, typename U> inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; }
template<typename T, typename U> inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << "{" << rhs.first << ", " << rhs.second << "}"; }

template<typename T> T gcd(const vector<T>& vec) {
	T res = vec.front();
	for (T e : vec) {
		res = gcd(res, e);
		if (res == 1) return 1;
	}
	return res;
}
template<typename T> T gcd(initializer_list<T> init) {
	auto first = init.begin(), last = init.end();
	T res = *(first++);
	for (auto itr = first; itr != last; ++itr) {
		res = gcd(res, *itr);
		if (res == 1) return 1;
	}
	return res;
}
template<typename T> T lcm(const vector<T>& vec) {
	T res = vec.front();
	for (T e : vec) res = lcm(res, e);
	return res;
}
template<typename T> T lcm(initializer_list<T> init) {
	auto first = init.begin(), last = init.end();
	T res = *(first++);
	for (auto itr = first; itr != last; ++itr) {
		res = lcm(res, *itr);
	}
	return res;
}
template<typename T> T pow(T x, lint n) {
	T res = 1;
	while (n > 0) {
		if (n & 1) res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

void out() {}
template<typename T> void out(T x) { cout << x << endl; }
template<typename T, typename... Args> void out(T x, Args... xs) {
	cout << x << ", ";
	out(xs...);
}

bool is_prime(lint x) {
	for (lint i = 2; i * i <= x; ++i) {
		if (x % i == 0) return false;
	}
	return 1 < x;
}

vector<lint> fact, fact_inv;
void fact_init(lint n, lint m = Mod) {
	fact.resize(n + 1);
	fact_inv.resize(n + 1);

	vector<lint> inv(n + 1);
	inv[1] = 1;

	fact[0] = fact[1] = 1;
	fact_inv[0] = 1;

	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1] % m;
		inv[i] = m - m / i * inv[m % i] % m;
	}

	for (lint i = 1; i <= n; ++i) {
		fact_inv[i] = fact_inv[i - 1] * inv[i] % m;
	}
}

lint modinv(lint a, lint m = Mod) {
	lint b = m, u = 1, v = 0;
	while (b != 0) {
		lint t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

lint modpow(lint x, lint n, lint m = Mod) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

lint intpow(lint x, lint n) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

lint comb(lint n, lint r) {
	if (n < 0 || r < 0 || n < r) return 0;
	if (r == 0 || r == n) return 1;
	return fact[n] * fact_inv[n - r] % Mod * fact_inv[r] % Mod;
}

lint perm(lint n, lint r) {
	if (n < 0 || r < 0 || n < r) return 0;
	return fact[n] * fact_inv[n - r] % Mod;
}

template<typename T = int>
vector<T> as_vector(const string& str) {
	const size_t n = str.size();

	vector<T> res(n);

	T* p_res = res.data();
	const char* p_str = str.data();

	for (size_t i = 0; i < n; ++i) {
		*p_res++ = T(*p_str++ - '0');
	}

	return res;
}

template<typename T>
vector<T> compressed(vector<T> v) {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	return v;
}

class Factring {
private:

	const lint max_n;
	vector<lint> sieve;

public:

	explicit Factring(lint max_n) noexcept
		: max_n{ max_n }
		, sieve{ max_n }
	{
		iota(sieve.begin(), sieve.end(), 0);

		for (lint i = 2; i * i < max_n; ++i) {
			if (sieve[i] < i) continue;

			for (lint j = i * i; j < max_n; j += i) {
				if (sieve[j] == j) sieve[j] = i;
			}
		}
	}

	unordered_map<lint, lint> calc(lint x) const noexcept {
		unordered_map<lint, lint> res;
		while (x > 1) {
			++res[sieve[x]];
			x /= sieve[x];
		}
		return res;
	}
};

struct UnionFind {
	const int n;
	vector<int> par, rank, siz, es;

	explicit UnionFind(int _n) noexcept
		: n(_n)
		, par(n)
		, rank(n)
		, siz(n, 1)
		, es(n)
	{
		iota(par.begin(), par.end(), 0);
	}

	int root(int x) noexcept {
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	bool same(int x, int y) noexcept { return root(x) == root(y); }

	void unite(int x, int y) noexcept {
		x = root(x); y = root(y);
		if (x == y) ++es[x];
		else if (rank[x] < rank[y]) {
			par[x] = y;
			siz[y] += siz[x];
			es[y] += es[x] + 1;
		}
		else {
			par[y] = x;
			if (rank[x] == rank[y]) ++rank[x];
			siz[x] += siz[y];
			es[x] += es[y] + 1;
		}
	}

	int count(int x) noexcept { return siz[root(x)]; }

	vector<vector<int>> groups() noexcept {
		vector<int> roots(n), group_size(n);

		for (int i = 0; i < n; ++i) {
			roots[i] = root(i);
			++group_size[roots[i]];
		}

		vector<vector<int>> res(n);

		for (int i = 0; i < n; ++i) {
			res.reserve(group_size[i]);
		}

		for (int i = 0; i < n; ++i) {
			res[roots[i]].push_back(i);
		}

		res.erase(
			remove_if(res.begin(), res.end(),
				[](const vector<int>& v) { return v.empty(); }),
			res.end()
		);

		return res;
	}
};

template<typename T>
class CumulativeSum {
private:

	const int n;
	vector<T> dat;

public:

	CumulativeSum() = default;
	explicit CumulativeSum(const int n) : n(n), dat(n + 1) {}
	CumulativeSum(const vector<T>& vec)
		: n(vec.size())
		, dat(n + 1)
	{
		for (int i = 0; i < n; ++i) dat[i + 1] = vec[i];
	}

	void add(const int i, const T& x) { dat[i + 1] += x; }

	void build() {
		for (int i = 0; i < n; ++i) {
			dat[i + 1] += dat[i];
		}
	}

	// [l, r)
	T sum(const int l, const int r) const { return dat[r] - dat[l]; }

	// [0, a)
	T sum(const int a) const { return dat[a]; }
};

template<typename T>
class CumulativeSum2D {
private:

	vector<vector<T>> dat;

public:

	CumulativeSum2D() = default;

	explicit CumulativeSum2D(size_t n) : dat(n + 1, vector<T>(n + 1)) {}

	CumulativeSum2D(size_t h, size_t w) : dat(h + 1, vector<T>(w + 1)) {}

	CumulativeSum2D(const vector<vector<T>>& vec) noexcept {
		const size_t h = vec.size(), w = vec.front().size();

		dat.resize(h + 1, vector<T>(w + 1));

		for (size_t i = 0; i < h; ++i) {
			for (size_t j = 0; j < w; ++j) {
				dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j] + vec[i][j];
			}
		}
	}

	void add(int h, int w, int v) noexcept {
		dat[h + 1][w + 1] += v;
	}

	void build() {
		const size_t h = dat.size(), w = dat.front().size();
		for (size_t i = 0; i < h; ++i) {
			for (size_t j = 0; j < w; ++j) {
				dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j];
			}
		}
	}

	// [0, h) × [0, w)
	T sum(int h, int w) const noexcept {
		return sum(0, 0, h, w);
	}

	// [h1, h2) × [w1, w2)
	T sum(int h1, int w1, int h2, int w2) const noexcept {
		return dat[h2][w2] - dat[h1][w2] - dat[h2][w1] + dat[h1][w1];
	}
};

template<typename T>
class BinaryIndexedTree {
private:

	const int size;
	vector<T> dat;

public:

	explicit BinaryIndexedTree(const int size) noexcept
		: size(size)
		, dat(size + 1) {}

	explicit BinaryIndexedTree(const vector<T>& vec) noexcept
		: size(vec.size())
		, dat(size + 1)
	{
		for (int i = 0; i < size; ++i) dat[i + 1] = vec[i];
		for (int i = 0; i <= size; ++i) {
			const int j = i + (i & -i);
			if (j <= size) dat[j] += dat[i];
		}
	}

	void add(const int a, const T w) noexcept {
		for (int x = a + 1; x <= size; x += (x & -x)) dat[x] += w;
	}

	void set(const int a, const T w) noexcept {
		add(a, w - dat[a]);
	}

	// [0, a)
	T sum(const int a) const noexcept {
		T res = 0;
		for (int x = a; x > 0; x -= x & -x) res += dat[x];
		return res;
	}

	// [a, b)
	T sum(const int a, const int b) const noexcept { return sum(b) - sum(a); }

	const T& operator[](const size_t x) const noexcept { return dat[x + 1]; }
};

template<typename T>
lint inversion_number(const vector<T> vec) {
	vector<T> v = vec;
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	const int n = vec.size();

	lint res = 0;

	fenwick_tree<int> b(n);
	for (int i = 0; i < n; ++i) {
		const int j = lower_bound(v.begin(), v.end(), vec[i]) - v.begin();
		res += i - b.sum(0, j);
		b.add(j, 1);
	}

	return res;
}

template<typename T, typename U>
T nearest_value(const vector<T>& v, const U& value) {
	auto itr = lower_bound(v.begin(), v.end(), value);
	if (itr == v.begin()) return *itr;
	if (itr == v.end()) return *prev(itr);
	return min(*itr - value, value - *prev(itr)) + value;
}

int m;
mint a[100010];
int main() {
	cin >> m;
	a[1] = 1;

	for (int i = 1; i <= m; ++i) {
		for (int k = 1; k * k <= i; ++k) {
			if (i % k == 0) {
				a[i + 1] += a[k];
				if (i / k != k) a[i + 1] += a[i / k];
			}
		}
	}

	cout << a[m + 1] << endl;
}

yukicoder

結果

テストケース

ソースコード