rt，题目如下：

题目描述

现在有一张长度为 $h$ 的画布，下标范围为 $0 \sim h - 1$。你需要用笔刷将其染上颜色。

笔刷可以表示为一个长度为 $n - 1$ 的正整数序列 $\{d_{n-1}\}$。每次可以选择画布的 $n$ 个位置 $b_1 \sim b_n$ 满足：

$$\forall 1 \leq i < n, \ b_{i+1} - b_i = d_i$$

并将画布的这 $n$ 个位置染上色。

由于颜色太深或太浅都不好看，所以画布的每一个位置必须 恰好被染色一次。一支笔刷是合格的，当且仅当存在一种方法能够恰好将画布的每一个位置都染色一次；两支笔刷不同，当且仅当 $\{d_{n-1}\}$ 中至少有一个位置不同。

共 $T$ 组数据，每次给出 $h, n$。请计算对于固定的 $h, n$，有多少支合格的笔刷，答案对 $10^9 + 7$ 取模。

---

输入格式

输入包括若干行：

• 第一行包含一个整数 $T$，表示测试组数。
• 接下来 $T$ 行，每行包括两个整数 $h, n$，表示一组数据。

---

输出格式

输出包括 $T$ 行，每行包含一个整数，表示合格的笔刷个数。

---

样例输入

4
9 3
1 1
100 10
5 4

---

样例输出

2
1
14
0

---

样例解释

对于第一组数据，仅有以下两种笔刷满足条件：

• $\{1, 1\}$
• $\{3, 3\}$

---

数据范围

• 对于 30% 的数据：

  $$T = 5, \ 1 \leq n \leq 3, \ 1 \leq h \leq 100$$

• 对于 60% 的数据：

  $$T = 10, \ 1 \leq n \leq h \leq 10^5$$

• 对于 100% 的数据：

  $$T = 500, \ 1 \leq n \leq h \leq 10^9$$

以下是给出来的参考解法，是记忆化搜索，时间复杂度我不会算，只知道是$O(\text{能过})$，最慢的点跑了不到500毫秒。

题目分析

有解的必要条件

首先，有解的一个必要条件是：

$n \mid h$

因为一个位置必须 恰好被涂一次，而一次涂 ( n ) 个位置。

如果将一个 ( b_{i+1} = b_i + 1 ) 的连续段称作一个 块，那么所有块的大小必须相等，否则会发生“相撞”。

---

块大小的讨论

当块大小 ( > 1 ) 时，间距必须是块大小的倍数。因此，我们可以直接将整个状态 缩小。

我们定义：

• ( F(h, n) )：块大小 ( > 1 ) 的解数。
• ( G(h, n) )：块大小 ( = 1 ) 的解数。

于是有公式：

$$F(h, n) = \sum_{k \mid n, \ k > 1} G\left(\frac{h}{k}, \frac{n}{k}\right)$$

---

计算 ( G(h, n) )

对于 ( G(h, n) )，我们考虑以下步骤：

1. 把笔刷的数组 ( {d_{n-1}} ) 最前面添加一个 ( 0 )，然后计算其 前缀和，得到数组 ( {p_n} )。

2. 将每次选择的数组 ( {b_n} ) 的第一个元素 ( b_1 ) 构成递增序列 ( {q_t} )，其中满足：

   $n \times t = h$

3. 一支笔刷合法的充要条件是：对于 ( p_i + q_j )，它们必须 互不相同且覆盖区间 ([0, h))。

---

双射的构造

对于合法的笔刷，序列 ( {q_t} ) 存在且唯一。因此，我们可以通过以下双射进行分析：

• 当交换 ( p ) 和 ( q ) 时，这对应了一支块大小为 ( n' = t ) 的合法笔刷。

块大小为 1 的情况

当块大小为 ( 1 ) 时：

1. 初始条件：

   • ( p_1 = q_1 = 0 )
   • ( p_2 > p_1 + 1 = 1 )

2. 由于 ( p_i + q_j ) 覆盖区间 ([0, h))，从而：

   $q_2 = 1$

这说明，交换 ( p ) 和 ( q ) 后，恰好对应一支块大小 ( > 1 ) 的笔刷。

于是得到公式：

$$G(h, n) = F\left(h, \frac{h}{n}\right)$$

---

结论

通过上述分析，我们可以直接使用 记忆化搜索 来解决本题。

参考代码（核心部分）：

const int mod = 1e9+7;
int h, n;
inline int f(int h, int n);
inline int g(int h, int n);
struct phs {
	template <class T1, class T2>
	std::size_t operator()(const std::pair<T1, T2>& pair) const {
		return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
	}
};
unordered_map<pair<int, int>, int, phs> m1, m2;
inline int f(int h, int n) {
	if (h % n)return 0;
	if (n == h || n == 1)return 1;
	if (m1.count({h, n}))return m1[ {h, n}];
	for (int i = 1; i * i <= h; i++) {
		if (h % i)continue;
		if (n % (h / i) == 0)(m1[ {h, n}] += g(i, n / (h / i))) %= mod;
		if (i * i^h && i ^ 1 && n % i == 0)(m1[ {h, n}] += g(h / i, n / i)) %= mod;
	}

	return m1[ {h, n}];
}
inline int g(int h, int n) {
	if (h % n)return 0;
	if (n == h || n == 1)return 1;
	if (m2.count({h, n}))return m2[ {h, n}];
	for (int i = 1; i * i <= h; i++) {
		if (h % i)continue;
		(m2[ {h, n}] += f(i, n)) %= mod;
		if (i * i^h && i ^ 1)(m2[ {h, n}] += f(h / i, n)) %= mod;
	}

	return m2[ {h, n}];
}

void solve() {
	cin>>h>>n;
	if (h % n)return puts("0"), void();
	if (n == h || n == 1)return puts("1"), void();
	cout<<g(h, n) + f(h, n)) % mod<<'\n';
}

那么这个东西的复杂度具体是多少？如何证明？蒟蒻不会，求神犇解答