摘要
Title: 1209. 带分数
Tag: dfs、排列、剪枝、字符串哈希
Memory Limit: 64 MB
Time Limit: 1000 ms

1209. 带分数

题意
思路

具体思路：
- 考虑从 1 ~ 9 进行全排列，从全排列中挑出 $x, y, z$ ，满足 $x + \frac{y}{z} == n$
- 可以用dfs实现全排列
- 选 $x, y, z$ 可以枚举 $x, y$ 从1 ~ 9
- 总复杂度约为 $O(9! * 9 * C(8, 2))$ ，勉勉强强可以过（其中 $n! * n$ 是全排列的复杂度）
优化：
- 首先，可以将等式优化为 $xz + y == zn$
- 其次，可以对dfs进行剪枝，如果一开始 $x$ 就已经大于n，那么可以直接return
- 再者，可以优化挑数的环节，在一个字符串中挑子串，可以通过字符串哈希来优化，达到 $O(1)$ 的复杂度
- 复杂度会降到很多

代码

'''
Author: NEFU AB-IN
Date: 2022-03-21 21:36:13
FilePath: \ACM\Acwing\1209.py
LastEditTime: 2022-03-22 16:34:09
'''
path, h = [0] * 10, [0] * 10 #路径，前缀和
st = [0] * 10 #标记是否遍历
p = [0] * 10 #底数数组
P = 10 #底数
ans = 0


def count(l, r):
    return h[r] - h[l - 1] * p[r - l + 1] #类似于字符串哈希，求一个串中的某一串


def dfs(u):
    global ans
    if u > 9:
        for i in range(1, P):
            h[i] = h[i - 1] * P + path[i] #求前缀和
        for a in range(1, 8):
            if count(1, a) > n:
                return
            for b in range(a + 1, 9):
                x = count(1, a)
                y = count(a + 1, b)
                z = count(b + 1, 9)
                if x * z + y == z * n:
                    ans += 1
        return

    for i in range(1, P):
        if st[i] == 0:
            st[i] = 1
            path[u] = i
            dfs(u + 1)
            st[i] = 0
    return


n = int(input())
p[0] = 1
for i in range(1, P):
    p[i] = p[i - 1] * P
dfs(1)
print(ans)

1209. 带分数

题意

思路

代码