自动搬运

查看原文

来自洛谷，原作者为

	Punainen 不过初赛不改签

搬运于2025-08-24 23:02:53，当前版本为作者最后更新于2024-08-25 23:02:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

看到数字可以重复时，便容易想到使用完全背包。我们可以使 $f_i$ 表示当某个数为 $i$ 时总共的拆分方案的总数。则易得转移方程 $f_j = f_j + f_{j-i}$，即数字 $j$ 原本的总数加上数字 $j$ 拆分掉 $i$ 时的总数。此时注意到，$f_0$ 的值必为 $1$，因为 $f_0$ 代表一个数被拆分完的状态，即为一种答案。另外，记得输出之前将 $f_n$ 减去 $1$，因为不能将原数拆为原数加上 $0$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[114514],w[114514],c[114514];
signed main(){
	int n;
	cin>>n;
    f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			f[j]=f[j]+f[j-i];
            f[j]%=2147483648;
		}
	}
    f[n]--;
	cout<<f[n]%2147483648;
    return 0;
}