【AtCoder思维训练】ABC221H Count Multiset

· · 题解

Preface

一道比较容易的前缀和优化 dp 题目。

Problem

输入两个正整数 n,m，并存在一个集合，问你一个长度为 k 的合法集合存在多少个。你需要回答 k 的值为 1 到 n 的每种情况。
一个合法的集合定义指长度为 k，元素和为 n，每一个数字在集合中出现的次数都小于等于 m 的集合。

Solution

首先，经典套路，集合转不下降序列。
不下降序列转差分。
设 l_1....l_k 为差分数组，则其需要满足：

l_i\geq0,\sum_ {i=x}^{i\leq x+m}l_i >0\space \space (1\leq x \leq k-m)

并且，由于对元素和的性质，根据差分得到：

(\space \sum _{i=1}^{i\leq k}l_i\times (k-i+1)\space ) \space =n

由于这个限制内带 k，我们需要回答若干个 k，并且我们并没有对差分数组的先后顺序做任何的限制，我们将差分数组倒转过来，限制是一样的，这样就消去了 k 的限制，即：

(\space \sum _{i=1}^{i\leq k}l_i\times i\space ) \space =n

现在这个限制就非常的好，可以开始进行 dp 了。
容易设状态为 f_{p,j}，意义为选了 p 个数，他们的差分满足 (\space \sum _{i=1}^{i\leq p}l_i\times i\space ) \space =j。

容易列出状态转移方程：

f_{p,j}=\sum_{i=1}^{i \times p\leq j} \sum_{k=p-m}^{k<p} f_{k,j-p\times i}

其中，k 为上一个非 0 位置，i 为选择的差分数。
显然，第二个 \sum 是可以滚动前缀和的，而第一个 \sum 是调和级数的。
总复杂度为 O(n^2 \ln n)： 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010;
const int mod=998244353;
int n,m,f[N][N],sum[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    f[0][0]=1;sum[0]=1;
    for(int p=1;p<=n;p++){
        for(int j=1;j<=n;j++){
            for(int i=1;i*p<=j;i++){
                f[p][j]+=sum[j-p*i];
                f[p][j]%=mod;
            }
        }
        for(int j=0;j<=n;j++){
            if(p-m>=0)sum[j]=(sum[j]-f[p-m][j]+mod)%mod;
            sum[j]=(sum[j]+f[p][j])%mod;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<f[i][n]<<"\n";
    return 0;
}