模拟赛的一道题目："ppip看到了一个各元素均为正整数、长度为k、各元素之和为n的不降数列。他想要知道这种数列的个数，对998244853取模。"
事实证明，我的写法是：先垫一层 \(1\)，再用拆解为正整数的做法去求答案。虽然过了，但感觉自己都不知道自己在干什么。
正解代码：
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244853;
int f[2][100010],n,k,ans;
inline int add(int x,int y){ return x + y >= mod ? x + y - mod : x + y; }
inline void toadd(int &x,int y){ x = add(x,y); }
int main(){
scanf("%d%d",&n,&k);
if(n < k)return puts("0"),0;
else if(n == k)return puts("1"),0;
f[0][0] = 1;
for(int i = 1;i<=k;++i){
int now = (i&1),pre = (now^1);
for(int j = 0;j<=n;++j)f[now][j] = 0;
for(int j = i;j<=n;++j){
toadd(f[now][j],f[pre][j-1]);
toadd(f[now][j],f[now][j-i]);
}
}
printf("%d",f[k&1][n]);
return 0;
}
下面是数拆分的几种类型。
自然数：
f[0]=1;
// f[i][j] = f[i][j-1] + f[i-1][j-i]
// 留下第 2 维
for(int i=1;i<=k;i++)
for(int j=i;j<=n;j++)
f[j]=(f[j]+f[j-i])%mod;
printf("%lld\n",f[n]);
理解：
前 \(i\) 个位置选出总和为 \(j\) 的方案数，完全背包。
正整数：
// f[i][j] 表示选择了 i 个，总和为 j
f[0][0] = 1
for(int i=1;i<=k;i++)
for(int j=i;j<=n;j++)
f[i][j]=f[i-1][j-1]+f[i][j-i];
理解：每次要么多选一个 \(1\)，要么每个数都 \(+1\)。
不重复：
g[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
g[i][j]=g[i-1][j-i]+g[i][j-i];
理解：必须选 \(i\)，每次要么多放一个 \(i\)，要么每个数都加上 \(i\)。
有些感性。相对于每次的增量为 \(1\) 而言，每次增量为 \(i\) 可以保证每个增量都会出现