题目概述

AtCoder Regular Contest 104D

解题报告

对于每个 $x$ ，我们认为第 $i$ 个物品大小为 $x-i$ ，共有 $K$ 个，现在的问题就转化为有多少种方案，使得选出来的和为 $0$ 。

物品大小为负数的背包非常奇怪，所以我们把问题分为两部分，一部分 $i<x$ ，另一部分 $i>x$ 。不难发现，前一部分物品大小范围 $[1,x-1]$ ，后一部分物品大小范围 $[1,n-x]$ ，都是从 $1$ 开始的。

定义 $f_{i,j}$ 表示前 $i$ 个物品（第 $i$ 个物品大小为 $i$ ），背包大小为 $j$ 的方案数，那么：

$$ f_{i,j}=\sum_{k=0}^{K}f_{i-1,j-ki} $$

这是一个可以用前缀和优化的形式，因此复杂度可以降到 $O(n^3)$ 。

对于 $x$ ，答案为 $\sum_{i}(K+1)f_{x-1,i}f_{n-x,i}$ ，其中 $K+1$ 是 $x$ 的方案数。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100,maxm=499950;

int n,K,MOD,f[maxn+5][maxm+5],F[maxn+5];

int main(){
    scanf("%d%d%d",&n,&K,&MOD);f[0][0]=1;
    for (int i=1,sum=i*K;i<n;i++,sum+=i*K){
        for (int j=0;j<i;j++) F[j]=0;
        for (int j=0;j<=sum;j++){
            F[j%i]=(F[j%i]+f[i-1][j])%MOD;
            if (j>=i*(K+1)) F[j%i]=(F[j%i]+MOD-f[i-1][j-i*(K+1)])%MOD;
            f[i][j]=F[j%i];
        }
    }
    for (int x=1;x<=n;x++){
        int ans=MOD-1;
        for (int j=0;j<=maxm;j++) ans=(ans+(LL)f[x-1][j]*f[n-x][j]%MOD*(K+1)%MOD)%MOD;
        printf("%d\n",ans);
    }
    return 0;
}