【AtCoder Grand Contest 009 E】Eternal Average
数位 DP，构造。
题目大意：
给定 $n$ 个 $0$ 和 $m$ 个 $1$，给定 $k$。
每次可以选择 $k$ 个数删掉，并插入这 $k$ 个数的平均数（实数）。
问最后剩下的 $1$ 个数有多少种不同的可能。
保证 $n+m-1$ 能被 $k$ 整除。
题解：
我们考虑构造一棵 $k$ 叉树，有 $n+m$ 个叶子，$n$ 个为 $0$，$m$ 个为 $1$。非叶子结点的值为叶子结点的值的平均数。那么要求的就是根有多少种不同的取值。
定义根的深度为 $0$，那么对于一个深度为 $x$ 的 $1$ 结点，它对答案的贡献为 $(\frac 1 k)^x$。所有 $1$ 结点的贡献之和就是根。
故令根为 $z$，所有 $1$ 的深度为 $x_1,x_2,x_3,\ldots,x_m$，所有 $0$ 的深度为 $y_1,y_2,y_3,\ldots,y_n$。要求满足 $z=\sum_{i=1}^m (\frac 1 k)^{x_i}$。由于把 $n$ 个 $0$ 改成 $1$ 后，最后的答案一定为 $1$，所以还需要满足 $1-z=\sum_{i=1}^n(\frac 1 k)^{y_i}$。
我们将 $z$ 写成 $k$ 进制小数，则 $z=0.c_1c_2c_3\ldots$。
如果没有进位，则 $\sum_i c_i=m$，每产生一次进位，会使得 $k$ 变成 $1$，那么数位和就减少了 $k-1$。所以合法的方案必须满足 $\sum_i c_i\equiv m\pmod{k-1}$。$1-z$ 和 $n$ 之间也有这样的条件。
我们考虑数位 DP。令 $f_{i,j}$ 表示前 $i$ 位，数位和为 $j$ 的方案数。
$f_{i,j}=\sum_{l=0}^{\min(k-1,j)}f_{i-1,j-l}$。
统计合法方案时，我们不能让小数后面有多余的 $0$，否则会算重。所以再加一维表示当前末尾是否为 $0$ 即可。
当 $j\bmod (k-1)=m\bmod (k-1)$ 且 $(i\cdot(k-1)-j+1)\bmod (k-1)=n\bmod(k-1)$ 且 $i\cdot(k-1)-j+1\leq n$ 且末尾不是 $0$ 时，$f_{i,j}$ 代表符合条件的方案。
时间复杂度 $O(n^3)$，转移的部分用前缀和优化，时间复杂度 $O(n^2)$。
Code：
#include<cstdio>
const int N=2333,md=1e9+7;
int n,m,k,f[N*2][N][2],ans;
int main(){
scanf("%d%d%d",&n,&m,&k);
f[0][0][0]=1;
for(int i=1;i<=n+m;++i){
static int s[N];
f[i][0][0]=s[0]=(f[i-1][0][0]+f[i-1][0][1])%md;
for(int j=1;j<=m;++j){
f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%md;
s[j]=(s[j-1]+f[i][j][0])%md;
f[i][j][1]=(s[j-1]+md-(j-k>=0?s[j-k]:0))%md;
}
for(int j=0;j<=m;++j)
if(i*(k-1)-j+1>=0&&j%(k-1)==m%(k-1)&&(i*(k-1)-j+1)%(k-1)==n%(k-1)&&i*(k-1)-j+1<=n)
ans=(ans+f[i][j][1])%md;
}
printf("%d\n",ans);
return 0;
}