题意

给定目标整数 n 和一个字符串 tmp。把 tmp 中每个数字字符看成一张数字牌，例如 "102" 表示数字牌 1,0,2 各一张。相同数字可以出现多次。

有五种运算符：

+  -  *  /  ^

其中 ^ 表示幂运算。

要求用这些数字牌和运算符构造表达式，满足：

1. 表达式必须以数字开头；
2. 每种运算符至多使用一次；
3. 每张数字牌至多使用一次；
4. 表达式按从左到右计算，没有括号、没有运算符优先级；
5. 允许不使用完所有数字牌，只要当前表达式的值等于 n 就计入答案；
6. 相同的表达式字符串只算一次。

求值等于 n 的不同表达式数量。

例如：

1+2*3

按代码语义计算为：

(1+2)*3 = 9

而不是普通的先乘后加。

核心思路

使用 DFS 搜索所有可能的表达式。

状态设计

dfs(cnt, mask, val, expr, target, found)

• cnt[d]：数字 d 还剩多少张；
• mask：二进制状态，表示哪些运算符已经使用过；
• val：当前表达式的值；
• expr：当前表达式字符串；
• target：目标值 n；
• found：存储所有合法表达式，用于去重。

运算符状态

vector<char> OPS = {'+', '-', '*', '/', '^'};

mask 的第 i 位表示 OPS[i] 是否已经使用：

if (mask & (1 << i)) continue;

递归时标记使用：

mask | (1 << i)

因此每种运算符最多使用一次。

枚举起点

表达式必须以数字开头，所以主函数枚举第一个数字：

for (int i = 0; i <= 9; i++) {
    if (cnt[i] == 0) continue;
    cnt[i]--;
    dfs(cnt, 0u, i, string(1, char(i + '0')), n, found);
    cnt[i]++;
}

如果有多个相同数字，只按数字值枚举一次，避免从相同数字牌重复生成相同字符串。

递归扩展

在 DFS 中，每次选择：

1. 一个还没用过的运算符；
2. 一个还有剩余的数字 j；
3. 计算 val op j；
4. 如果合法，则继续递归。

for (int i = 0; i < 5; i++) {
    if (mask & (1 << i)) continue;
    char op = OPS[i];

    for (int j = 0; j <= 9; j++) {
        if (cnt[j] == 0) continue;

        ll nxt;
        if (!apply(op, val, j, nxt)) continue;

        cnt[j]--;
        dfs(cnt, mask | (1 << i), nxt, expr + op + char('0' + j), target, found);
        cnt[j]++;
    }
}

注意每次都是：

当前值 op 新数字

所以整个表达式是严格左结合的，例如：

1+2*3

计算过程是：

((1 + 2) * 3)

apply 函数细节

加法、减法、乘法

直接计算：

res = a + b;
res = a - b;
res = a * b;

除法

代码中的除法不是 C++ 默认的向零截断，而是向负无穷取整，即：

floor(a / b)

实现方式：

ll i = a / b;
ll j = a % b;
if (j != 0 && ((a < 0) != (b < 0))) i--;
res = i;

例如：

-7 / 3

C++ 默认结果是 -2，但代码会修正为 -3。

除数为 0 时非法。

幂运算

a ^ b

要求：

• b >= 0；
• 不允许 0^0；
• 乘法过程中检查溢出，超过约 1e17 就判定非法。

if (b < 0 || (a == 0 && b == 0)) return false;
res = 1;
for (ll i = 0; i < b; i++) {
    if (a != 0 && llabs(res) > 100000000000000000LL / llabs(a))
        return false;
    res *= a;
}

因为这里的指数 b 是单个数字，所以最多是 9，循环次数很小。

去重

使用：

set<string> found;

每当前表达式值等于目标值：

if (val == target) found.insert(expr);

就插入集合。

最终输出：

cout << found.size();

由于 set 会自动去重，所以相同表达式只会计数一次。

注意：代码是在 DFS 每层入口判断 val == target，因此表达式可以在任意位置停止，不要求用完所有数字牌。

复杂度

由于运算符最多使用 5 个，而表达式从 1 个数字开始，每用一个运算符就追加一个数字，所以表达式最多使用：

1 + 5 = 6

个数字。

DFS 深度最多为 6。每层最多枚举：

• 5 个运算符；
• 10 种数字值。

因此搜索量受常数级深度限制。粗略上界为：

O(5! · 10^6 · L · log S)

其中：

• L 是表达式字符串长度；
• S 是找到的表达式数量；
• log S 来自 set<string> 插入。

实际运行时会受到剩余数字数量和溢出剪枝的限制，远小于这个上界。

空间复杂度为：

O(S · L + 10)

主要用于存储答案集合。

参考代码

#include <bits/stdc++.h>

#define ll long long
using namespace std;

vector<int> cnt(10, 0);
vector<char> OPS = {'+', '-', '*', '/', '^'};

// 计算 a op b，结果放入 res
// 返回 false 表示该运算非法
bool apply(const char &op, const ll &a, const ll &b, ll &res) {
    switch (op) {
    case '+':
        res = a + b;
        return true;

    case '-':
        res = a - b;
        return true;

    case '*':
        res = a * b;
        return true;

    case '/': {
        if (b == 0) return false;

        // 实现 floor(a / b)
        ll i = a / b;
        ll j = a % b;
        if (j != 0 && ((a < 0) != (b < 0))) i--;
        res = i;
        return true;
    }

    case '^': {
        // 不允许负指数和 0^0
        if (b < 0 || (a == 0 && b == 0)) return false;

        res = 1;
        for (ll i = 0; i < b; i++) {
            // 防止乘法溢出
            if (a != 0 && llabs(res) > 100000000000000000LL / llabs(a))
                return false;
            res *= a;
        }
        return true;
    }

    default:
        return false;
    }
}

static void dfs(vector<int> &cnt,
                unsigned int mask,
                ll val,
                const string &expr,
                ll target,
                set<string> &found) {
    // 允许在任意位置停止，只要当前值等于目标值
    if (val == target) {
        found.insert(expr);
    }

    // 枚举下一个运算符
    for (int i = 0; i < 5; i++) {
        if (mask & (1 << i)) continue; // 该运算符已经用过

        char op = OPS[i];

        // 枚举下一个数字
        for (int j = 0; j <= 9; j++) {
            if (cnt[j] == 0) continue; // 数字 j 没有剩余

            ll nxt;
            if (!apply(op, val, j, nxt)) continue;

            cnt[j]--;
            dfs(cnt,
                mask | (1 << i),
                nxt,
                expr + op + char('0' + j),
                target,
                found);
            cnt[j]++;
        }
    }
}

int main() {
    ll n;
    set<string> found;
    string tmp;

    cin >> n;
    cin >> tmp;

    // 统计 tmp 中每个数字字符出现的次数
    for (auto c : tmp) {
        if (isdigit(static_cast<unsigned char>(c))) {
            cnt[c - '0']++;
        }
    }

    // 枚举表达式的第一个数字
    for (int i = 0; i <= 9; i++) {
        if (cnt[i] == 0) continue;

        cnt[i]--;
        dfs(cnt, 0u, i, string(1, char(i + '0')), n, found);
        cnt[i]++;
    }

    cout << found.size() << '\n';
    return 0;
}

易错点总结

1. 表达式是左结合计算
   没有括号，也没有普通四则运算优先级。

2. 除法是向下取整
   不是 C++ 默认的向零截断。

3. 每种运算符最多用一次
   通过 mask 实现。

4. 每张数字牌最多用一次
   通过 cnt[j]-- 和恢复实现。

5. 可以在中途停止
   代码在每次 DFS 入口检查 val == target，不要求用完所有数字牌。

6. ^ 是幂运算，不是异或
   且 0^0 非法，幂运算过程中会检查溢出。

7. 相同表达式需要去重
   最终用 set<string> 统计不同表达式数量。