[DP记录]AT2294 [AGC009E] Eternal Average

· · 个人记录

题意 ： 黑板上有 n 个 0 和 m 个 1 ，每次可以选择 k 个数字将其擦除，然后把它们的平均数写上去。

保证 n+m-1 能被 k-1 整除。于是，这样一直操作最终只会剩下一个数字，问这个数字有多少种不同的可能。

答案对 10^9+7 取模。

------------ 神必题。 将操作刻画为 $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

考虑 \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)。

#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;
}