传送门

考虑一个1对最终那个值产生的贡献,只可能是$1/K,1/K^2,1/K^3,...$。假设我们已经确定了每个1的贡献,那我们每次合并就等价于找一些有相同贡献$1/K^x$的1(最多找$K$个,不足$K$个的用0来补),然后删掉这些1,并加入一个贡献为$1/K^{x-1}$的1。注意到这其实就是一个$K$进制下的进位过程,进完位之后每位都是$[0,K)$之间的数,但是每位之和可能会减少。

考虑一个$K$进制小数是否能成为答案。记$x=0.x_1x_2x_3\ldots$,根据上面所述,这个$K$进制小数是由某个不满足每位小于$K$的小数进位得到的。由于每次进位后,每位之和都会减少$K-1$,所以只要$\sum x_k\equiv m\pmod {K-1}$,这个小数就能通过某个数位之和为$n$的不严格$K$进制小数进位得到(可以通过不断把最后一位退位来得到)。

由于$x$已经不能直接进位,我们每次进位时都要补一些0。除了最低位需要补$K-x_i$个0,剩下的每一位都要补$K-1-x_i$个0。这样,设最低位是第$L$位,总共需要补$(K-1)L+1-\sum x_k$个0。由于$K-1 \mid n+m-1$,所以只要$(K-1)L+1-\sum x_k\leq n$,就能恰好补完所有0。

所以我们可以直接DP,设$f_{ij}$表示当前共有$i$位,数位之和为$j$的方案数。这个DP可以直接枚举在最高位前面加一个数来转移,DP完之后直接枚举总位数及总数位和,如果满足$(K-1)L+1-\sum x_k\leq n$,就能对答案产生贡献。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 2010
#define LL long long

const LL P=1000000007;

int n,m,l,K;
LL **f;

void dp(){
    f=new LL* [l];
    for(int i=0;i<=l;i++){
        f[i]=new LL[n+1];
        memset(f[i],0,sizeof(LL)*(n+1));
    }
    f[0][0]=1;
    for(int i=1;i<=l;i++){
        for(int j=0;j<=n;j++)
            for(int k=0;k<K;k++)
                f[i][j]=(f[i][j]+(j>=k?f[i-1][j-k]:0))%P;
        if(i==1) f[i][0]=0;
    }
}

LL calc(){
    LL ans=0;
    for(int j=n;j>0;j-=K-1){
        for(int i=l;i;i--)
            if((K-1)*i+1-j<=m)
                ans=(ans+f[i][j])%P;
    }
    return ans;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d%d%d",&m,&n,&K);
    l=(n+m-1)/(K-1);
    dp();
    printf("%lld\n",calc());
    return 0;
}