Link
题目给我们的这个东西可以转化为一棵(k)叉树，有(n+m)个叶子节点，其中(m)个权值为(1)，(n)个权值为(0)，每个非叶子节点的权值为其儿子的平均值，现在问你根节点的权值有多少种取值。
转化之后发现似乎可做了一点。（当然还是一道神仙题）
我们设(n)个权值为(0)的叶子节点的深度为(x_1sim x_n)，(m)个权值为(1)的叶子节点的深度为(y_1sim y_m)，根节点的权值为(z)。
那么有(sumlimits_{i=1}^mk^{-y_i}=z)。
并且如果我们把所有叶子节点的权值都设为(1)，那么树上所有点的权值都为(1)，(sumlimits_{i=1}^mk^{-y_i}+sumlimits_{i=1}^nk^{-x_i}=1)即(sumlimits_{i=1}^nk^{-x_i}=1-z)。
我们将(z)写成(k)进制下的小数形式，(z=0.overline{c_1cdots c_l})。
那么对于一个(k^{-y_i})，它会让(c_{y_i}+1)。
因此在不考虑进位的情况下，(sumlimits_{i=1}^lc_i=m)。
进位实质上就是某一位(-k)，高位(+1)，反映到数位和上就是(-(k-1))。
因此在考虑进位的情况下，(sumlimits_{i=1}^lc_iequiv m(mod k-1))。
当然也有(sumlimits_{i=1}^lc_ile m)。
对(1-z)做类似的分析。
我们可以发现(1-z)的数位和就是(sumlimits_{i=1}^l(k-1-c_i)+1=l(k-1)+1-sumlimits_{i=1}^lc_i)。
后面那坨就是(z)的数位和对吧。
与求(z)的数位和的性质的过程类似，我们有(l(k-1)+1-sumlimits_{i=1}^lc_iequiv n(mod k-1))。
以及(l(k-1)+1-sumlimits_{i=1}^lc_ile n)。
那么我们就可以设计一个数位dp了。
首先这个(k)叉树的深度最多为(frac{n+m-1}{k-1})，也就是说(z)和(1-z)最多有(frac{n+m-1}{k-1})位。
我们设(f_{i,j,k})表示考虑前(i)位小数，数位和为(j)时的方案数。注意到小数不能存在后导(0)，我们再开一维(k)表示最后一位是不是(0)。
那么有(f_{i,j,0}=f_{i-1,j,0}+f_{i-1,j,1})，
以及(f_{i,j,1}=sumlimits_{o=max(0,j-k)}^{j-1}(f_{i-1,o,0}+f_{i-1,o,1}))。
前缀和优化一下就行了。
求答案的时候判一下第二维是否满足上面的(z)和(1-z)的(4)个条件（(sum cle m)的实际上可以不用判，因为循环里面最多跑到了(m)），而且注意一下只能加第三维为(1)的答案。
#include<cstdio>
#include<cctype>
const int N=2007,P=1000000007;
int inc(int a,int b){return a+=b,a>=P? a-P:a;}
int dec(int a,int b){return a-=b,a<0? a+P:a;}
int read(){int x;scanf("%d",&x);return x;}
int f[N<<1][N][2],s[N];
int main()
{
int n=read(),m=read(),k=read(),i,j,ans=0;
f[0][0][0]=1;
for(i=1;i<=(n+m-1)/(k-1);++i)
{
s[0]=inc(f[i-1][0][1],f[i-1][0][0]);
for(j=1;j<=m;++j) s[j]=inc(s[j-1],inc(f[i-1][j][0],f[i-1][j][1]));
for(j=0;j<=m;++j)
{
f[i][j][0]=inc(f[i-1][j][0],f[i-1][j][1]);
if(j) f[i][j][1]=dec(s[j-1],(j>=k? s[j-k]:0));
}
for(j=0;j<=m;++j) if(j%(k-1)==m%(k-1)&&(i*(k-1)+1-j)%(k-1)==n%(k-1)&&i*(k-1)+1-j<=n) ans=inc(ans,f[i][j][1]);
}
printf("%d",ans);
}