题解：P1832 A+B Problem（再升级）

· · 题解

别的大佬们都用完全背包做的，蒟蒻（我）提供一种添加限制的方法。

Analysis

开始会想到枚举小于 n 的每个素数为基础进行分解。

设 f(m) 表示将 m 拆分成素数的方案数，则对于 n，可以分解为一些类似 n=prime_i+f(n-prime_i) 的方案。但这样会有重复，比如分解 10：

10=2+f(8) 10=3+f(7) 10=5+f(5) 10=7+f(3)

发现 3+f(7) 和 7+f(3) 明显存在方案数上的重复（重复一直是求方案数这一类问题的主要错误点之一）。

在做计数类题目的时候，有一种常用的方法，即给函数添加一个限制条件，以保证枚举全的情况下避开重复的情况。

不妨设 f(m,l) 表示以小于等于 l 的数拆分 m 的方案数。

那么对 10 的分解如下：

10=2+f(8,2) \rightarrow 2+2+2+2+2=10 10=3+f(7,3) \rightarrow 3+3+2+2=10 10=5+f(5,5) \rightarrow 5+5=10\ \operatorname{and}\ 5+3+2=10 10=7+f(3,7) \rightarrow 7+3=10

这样五种策略都凑齐了，再验证几个数字，发现都是正确的。

这样为什么是对的？

答：因为我们加了小于等于 l 的限制，这样可以使枚举的所有方案都是升序的，不会出现重复（和进行 dfs 爆搜的结果顺序一样）。

Code

代码实现：先筛素数，然后用记忆化搜索进行动态规划。递归的终止条件是 m=0，表示分解成功，返回 1；否则返回所有分解的方案数之和。

这样的时间复杂度约为 \text{O}(\frac{n^3}{\log_2 n})，虽然没有背包快，但通过本题也是足够的。

十年 OI 一场空，不开 long long 见祖宗。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;

int prime[maxn], cnt; // 存储素数的数组、数组长度的指针
int vis[maxn]; // 筛素数的数组

void getPrime()
{
    for(int i = 2; i < maxn; i ++){
        if(!vis[i]){
            prime[cnt ++] = i;
            for(int j = 2 * i; j < maxn; j += i) vis[j] = 1;
        }
    }
}

ll f[1010][1010];
ll dfs(int m, int l) // 以小于等于l的素数拆分m的方案数
{
    if(m == 0) return 1; // 如果减到0了，证明可以成功分解
    if(f[m][l] != -1) return f[m][l];
    f[m][l] = 0; // 初始化为0，不然会累加上-1
    for(int i = 0; prime[i] <= l && prime[i] <= m; i ++){ // 枚举小于l和m的，不然会把m减出负数
        f[m][l] += dfs(m - prime[i], prime[i]);
    }
    return f[m][l];
}

signed main()
{
    getPrime();
    memset(f, -1, sizeof f);
    int n;
    cin >> n;
    cout << dfs(n, n) << endl;
    return 0;
}