[DP记录]AT2294 [AGC009E] Eternal Average

**题意** ： 黑板上有 $n$ 个 $0$ 和 $m$ 个 $1$ ，每次可以选择 $k$ 个数字将其擦除，然后把它们的平均数写上去。 保证 $n+m-1$ 能被 $k-1$ 整除。于是，这样一直操作最终只会剩下一个数字，问这个数字有多少种不同的可能。 答案对 $10^9+7$ 取模。 $n,m,k\leq 2000$ ，时限 $\texttt{2s}$。 ------------ 神必题。 将操作刻画为 $k$ 叉树。每次将新产生的节点与擦除的 $k$ 个节点连边，点权为直接儿子的平均数。 记 $m$ 个 $1$ 的深度分别为 $d_{1\sim m}$ （根的深度为 $0$），则最终的数为 $z=\sum\limits_{i=1}^mk^{-d_i}$。 将 $z$ 写作 $k$ 进制小数 $0.z_1z_2z_3...z_t$ ，其中 $z_t\neq 0$。 问题变为 ： 有多少个 $k$ 进制小数可以生成合法的操作树。 我们知道，假如所有叶子都是 $1$ ，则根节点的点权一定是 $1$。 设 $m$ 个 $0$ 的深度为 $d'_{1\sim n}$ ，则有 $1=\sum\limits_{i=1}^mk^{-d_i}+\sum\limits_{i=1}^nk^{-d'_i}$。这是一个必要条件。 实际上，这个条件同时也是充分的 ： 将 $z'=\sum\limits_{i=1}^nk^{-d'_i}$ 写成小数，最后一位一定和 $z$ 的最后一位和为 $k$ 而产生进位，然后再次必须和为 $k$。 根据这个过程不难构造出对应的树。 - 故问题转化为 ： 求符合下列条件的实数 $z$ 的个数 ： - $z$ 可以写成 $m$ 个 $\frac{1}{k}$ 的幂的和。 - $1-z$ 可以写成 $n$ 个 $\frac{1}{k}$ 的幂的和。 对于 $k$ 进制小数 $z=0.z_1z_2z_3...z_t$ ，需要满足下列条件 ： - $0\leq z_i<k$ - $\sum_{i=1}^tz_i\leq n$ - $\sum_{i=1}^tz_i= n\pmod{k-1}$ - $1+\sum_{i=1}^t(k-1-z_i)\leq m$ - $1+\sum_{i=1}^t(k-1-z_i)= m\pmod{k-1}$ 考虑 $\rm DP$。设 $dp[t][s][0/1]$ 表示填写了 $t$ 个数位，目前的数位和为 $s$ ，最后一个数是否为 $0$。（统计答案时钦定末位非 $0$） 边界为 $dp[0][0][0]=1$。 则有如下转移 ： $$dp[t][s][0]=dp[t-1][s][0]+dp[t-1][s][1]$$ $$dp[t][s][1]=\sum\limits_{c=1}^{k-1}dp[t-1][s-c][0]+dp[t-1][s-c][1]$$ 利用前缀和优化即可 $O(1)$ 转移。 这里 $t$ 只会达到 $O(\frac{n+m}{k-1})$ 级别， $s$ 可以达到 $O\big(n\big)$ 级别。 于是复杂度为 $O\big((n+m)^2/k\big)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 2050 using namespace std; const int mod=1000000007; int n,m,k,ans,dp[MaxN<<1][MaxN][2],o[MaxN]; int main() { scanf("%d%d%d",&n,&m,&k); dp[0][0][0]=1; for (int t=1;t<=(n+m)/(k-1);t++){ o[0]=(dp[t-1][0][0]+dp[t-1][0][1])%mod; for (int s=1;s<=n;s++) o[s]=((long long)o[s-1]+dp[t-1][s][0]+dp[t-1][s][1])%mod; for (int s=0;s<=n;s++){ dp[t][s][0]=(dp[t-1][s][0]+dp[t-1][s][1])%mod; if (s-k<0)dp[t][s][1]=o[s-1]; else dp[t][s][1]=(o[s-1]-o[s-k])%mod; if (s%(k-1)==n%(k-1)&&1+t*(k-1)-s<=m&&(1+t*(k-1)-s)%(k-1)==m%(k-1)) ans=(ans+dp[t][s][1])%mod; } }printf("%d",(ans+mod)%mod); return 0; } ```