最多只有 \(1\) 类物品没有用完
CF1442D
多重背包计数的前缀和优化
ARC104D
题面
题目：给出正整数 \(n, k, m\)，表示任意正整数 \(i ∈ [1, n]\) 都有 \(k\) 个可供选择，你需要从中选出若干个数组成一个可重集。请计算选出的可重集平均数为 \(x\) 的方案数对 \(m\) 取模后的值，对于所有正整数 \(x ∈ [1, n]\) 求解。
思路
对于平均数为 \(x\) 的情况，相当于在 \([1-x,n-x]\) 中选择一些数使得和为 \(0\)，也就是 值属于 \([1-x,-1]\) 的加上属于 \([1,n-x]\) 的为 \(0\)。
设 \(dp_{i,j}\) 表示在 \(1 \sim i\) 中和为 \(j\) 的方案数，由于 \(n,k\) 极小，可以用多重背包计数的前缀和优化，那么答案就是 \((k+1)(\sum_{i=0}^{limit} dp_{x-1,i}dp_{n-x,i})-1\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,sum,MOD;
int dp[105][505005];
int main(){
scanf("%d%d%d",&n,&k,&MOD);
dp[0][0]=1;
for(int i=1;i<=n;i++){
sum+=i*k;
memcpy(dp[i],dp[i-1],sizeof dp[i]);
for(int j=i;j<=sum;j++) (dp[i][j]+=dp[i][j-i])%=MOD;
int tmp=(k+1)*i;
for(int j=sum;j>=tmp;j--) (dp[i][j]+=MOD-dp[i][j-tmp])%=MOD;
}
for(int i=1;i<=n;i++){
ll ans=0;
for(int j=0;j<=sum;j++) (ans+=1ll*dp[i-1][j]*dp[n-i][j]%MOD)%=MOD;
printf("%lld\n",((k+1)*ans+MOD-1)%MOD);
}
return 0;
}