$毒瘤之神异之旅$毒瘤之神异之旅

题目描述见链接 .

$最初想法$最初想法

设 $F[i,j]$F[i,j] 表示将 $j$j 划分为 $i$i 份的方案数, $F[i,j]=\sum F[i-1,j-k]$F[i,j]=∑F[i−1,j−k] .
发现这样会使得形如 1 1 3. 的方案算多次: 1 1 3, 1 3 1, 3 1 1.

$正解部分$正解部分

设 $F[i,j]$F[i,j] 表示将 $i$i 划分成 $j$j 份的方案数, 转移时不再一个一个数字添加, 而是整体往上叠,
可得 $F[i,j]=F[i-1,j-1]+F[i-j,j]$F[i,j]=F[i−1,j−1]+F[i−j,j], 分别表示包含 $1$1 和 不包含 $1$1 的情况 .
初值: $F[0,0]=1$F[0,0]=1, 时间复杂度 $O\left(N^2\right)$O(N2) .

鉴于上方的 $dp$dp 方式, 统计答案不能按传统顺序统计, 那么怎么统计呢 $?$?

我们可以对数字 $x$x 单独考虑, 设 $x$x 出现 $y$y次 的方案为 $num[x,y]$num[x,y],
则 $num[x,y]=x至少出现y次的方案数-x至少出现y+1的方案数$num[x,y]=x至少出现y次的方案数−x至少出现y+1的方案数 .
而 $x至少出现y次的方案数=F[N-xy,K-y]$x至少出现y次的方案数=F[N−xy,K−y] .

到这一步, 发现求出 $num[x,y]$num[x,y] 对统计答案好像并没有作用,
只需计算出 $x至少出现y次的方案数=F[N-xy,K-y]$x至少出现y次的方案数=F[N−xy,K−y] 即可.

于是答案等于 $\sum F[N-xy,K-y]\ast x^M$∑F[N−xy,K−y]∗xM, 统计答案时间复杂度同样是 $O\left(N^2\right)$O(N2) .

$实现部分$实现部分

#include<bits/stdc++.h>
#define reg register

const int maxn = 5005;
const int mod = 1e9 + 7;

int N;
int K;
int M;
int Ans;
int F[maxn][maxn];

int Ksm(int a, int b){ int s = 1; while(b){ if(b&1)s=1ll*s*a%mod; a=1ll*a*a%mod; b>>=1;} return s; }

int main(){
        scanf("%d%d%d", &N, &K, &M);
        F[0][0] = 1;
        for(reg int i = 0; i <= N; i ++) F[i][i] = 1;
        for(reg int j = 1; j <= K; j ++)
                for(reg int i = j; i <= N; i ++)
                        F[i][j] = (F[i-1][j-1] + F[i-j][j]) % mod;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 1; j <= K; j ++){
                        int num = 0;
                        if(i*j <= N) num += F[N-i*j][K-j];
                        int Amp = 1ll*num*Ksm(i, M) % mod;
                        Ans = (Ans + Amp) % mod;
                }
        printf("%d\n", Ans);
        return 0;
}