CWOI S C0294C 货币系统

题意

U2FsdGVkX1+BEbTAhPCSrzF/tq3hUKT50YUIWhPYVeEybXqk7K7OhSLSd50jjPK6
/zXcJhRsYMBy3VA4nrDcCu2PlNTPYbqeCjxRQ2jNUO+OpXe1gFCxZBeJEyNwAiMH
KnurvTfcGgWUEVeVNfQMeUqalynXgt26jGZ1TvIBF+txVqJaQ58saE+cKQFGtQOY
UuSXxV9eSlDf4kfVBjpSGeY00BPk3YtiWnskYcZ/srP4ARhjA9wKslXZheS9LXH/
WRp3KK3awgg/cdd49CZcK7DHDbXzU955F6U9N75ziZKkUE3FW3GKJ7yhaxjPCnwa
k55Dm+TPB7MQH6UlY6m/l4eUNTEuLm9FxRGz6cydMtUX3qtMybcOvQjM3MchdWAh
AXmrTMHH/9IGBBmGtbnkU7XGd95iX5moosBvm26C1a/g7Hsew7JBupylLAxzaKdh
Z3xr0ac6acmWoDO60AuwaEuRY54eEn4GBiSynhrijWcPReNCY5d9d7RsSronJ8fs
ac8EMXX0o6CUl7597V5c8oIsshYgbNo8EWddOpXiqZv+Ee5+aB+tijqjvYAUKr7s
V8xcghYDv/vW0DpaygbLCWvtDvbAlhYU4Xz6xzBE5WeLyp0u3hj9bB6Z1IAMavUL
lx/XyVlIuAq09RJ5K7CLmJQlaMokMTw/tjCXNq+pLSCvvYN7luS47hP4riQ9uSwM
KnnRDO4XmNQF4U9WVn8ysB31x9kRmxKylhFfZk06AufGVjbJqxajKTT+jIvz4ke/

解析

先考虑对于某个 $a$ 如何计算表示 $n$ 的方案数。首先，容易发现最后一定有 $n \bmod a_{1}$ 个 $a_{0}$，因为前面所有数都应该组成了 $a_{1}$ 的倍数，我们可以先忽略掉后面的 $n \bmod a_{1}$ 个值。如果前面出现 $a_{0}$，则出现次数一定是 $a_{1}$ 的倍数个。这个时候，你发现 $n$，$a_{1}$ 到 $a_{L-1}$，$a_{0}$ 的出现次数都是 $a_{1}$ 的倍数，你可以考虑全部除以 $a_{1}$。这是一个递归的过程。

具体来说，定义 $f(i, j)$ 表示当 $n=i$ 且有 $j$ 种表示 $1$ 的方式时，表示 $n$ 的方案数。枚举所有的 $t = a_{1}$，然后从 $f(\frac{i}{t}, j^{t}+1)$ 转移，系数是 $j^{n \bmod t}$ 即，组成末尾 $1$ 的方案数。特别的，注意以上的转移是基于存在 $a_{1}$ 的，如果 $L=1$，则方案数为 $j^{i}-(j-1)^{i}$，即将所有 $1$ 摆到一起的方案数，减去没有用 $a_{L-1}$ 的。

关于时间复杂度。注意到在上面转移中，$j$ 都是底数，可以对 $19$ 取模。同时 $i$ 也是从 $n$ 整除出来的，级别是 $\sqrt{n}$ 的。所以复杂度是 $O(19m\sqrt{n})$。

特别注意，使用欧拉定理降幂的时候，需要对 $0$ 特判，因为 $0$ 和 $19$ 不互质。

实现

可以写成记忆化搜索的形式。

#include <algorithm>
#include <array>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>

void set_io()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
}

template <int P> struct static_modint
{
	using mint = static_modint;
	unsigned int _v;

	static_modint() : _v(0) {}

	static_modint(long long v)
	{
		long long x = v % mod();
		if (x < 0) x += mod();
		_v = x;
	}

	unsigned int val() const { return _v; }
	static constexpr unsigned int mod() { return P; }
	static constexpr unsigned int phi() { return mod() - 1; }

	mint operator-() const { return mint(-_v); }
	mint &operator+=(const mint &a)
	{
		_v += a._v;
		if (_v >= mod()) _v -= mod();
		return *this;
	}
	mint &operator-=(const mint &a)
	{
		_v += mod() - a._v;
		if (_v >= mod()) _v -= mod();
		return *this;
	}
	mint &operator*=(const mint &a)
	{
		_v = (long long)_v * a._v % mod();
		return *this;
	}
	mint operator+(const mint &a) const { return mint(*this) += a; }
	mint operator-(const mint &a) const { return mint(*this) -= a; }
	mint operator*(const mint &a) const { return mint(*this) *= a; }

	static std::array<std::array<mint, phi()>, mod()> init_pow_table()
	{
		std::array<std::array<mint, phi()>, mod()> pow_table;
		for (unsigned int i = 0; i < mod(); i++) {
			pow_table[i][0] = 1;
			for (unsigned int j = 1; j < phi(); j++) {
				pow_table[i][j] = pow_table[i][j - 1] * i;
			}
		}
		return pow_table;
	};

	mint pow(long long n) const
	{
		static auto pow_table = init_pow_table();

		if (val() == 0) {
			if (n == 0) return 1;
			return 0;
		}
		return pow_table[val()][n % phi()];
	}

	mint inv() const { return pow(mod() - 2); }

	mint &operator/=(const mint &a) { return *this *= a.inv(); }
	mint operator/(const mint &a) const { return mint(*this) /= a; }
};

using mint = static_modint<19>;

constexpr long long MAXN = 10'000'000'000ll;
constexpr long long SQRT_MAXN = 100'000;

int main()
{
	set_io();

	long long N;
	int M;
	std::cin >> N >> M;

	static std::array<std::array<mint, mint::mod()>, SQRT_MAXN * 2> f;
	static std::array<std::array<bool, mint::mod()>, SQRT_MAXN * 2> has_val;

	auto dfs = [N, M](auto &&self, long long n, mint cnt1) -> mint
	{
		if (n == 0) return 0;
		long long nid = n;
		if (nid > SQRT_MAXN) nid = SQRT_MAXN + N / n;
		if (has_val[nid][cnt1.val()]) return f[nid][cnt1.val()];

		mint res = cnt1.pow(n) - (cnt1 - 1).pow(n);
		for (int t = 2; t <= M; t++) {
			res += self(self, n / t, cnt1.pow(t) + 1) * cnt1.pow(n % t);
		}

		has_val[nid][cnt1.val()] = true;
		f[nid][cnt1.val()] = res;
		return res;
	};

	std::cout << dfs(dfs, N, 1).val() << std::endl;
}