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;
}