AT2294 Eternal Average

Link

题目给我们的这个东西可以转化为一棵\(k\)叉树，有\(n+m\)个叶子节点，其中\(m\)个权值为\(1\)，\(n\)个权值为\(0\)，每个非叶子节点的权值为其儿子的平均值，现在问你根节点的权值有多少种取值。

转化之后发现似乎可做了一点。（当然还是一道神仙题）

我们设\(n\)个权值为\(0\)的叶子节点的深度为\(x_1\sim x_n\)，\(m\)个权值为\(1\)的叶子节点的深度为\(y_1\sim y_m\)，根节点的权值为\(z\)。

那么有\(\sum\limits_{i=1}^mk^{-y_i}=z\)。

并且如果我们把所有叶子节点的权值都设为\(1\)，那么树上所有点的权值都为\(1\)，\(\sum\limits_{i=1}^mk^{-y_i}+\sum\limits_{i=1}^nk^{-x_i}=1\)即\(\sum\limits_{i=1}^nk^{-x_i}=1-z\)。

我们将\(z\)写成\(k\)进制下的小数形式，\(z=0.\overline{c_1\cdots c_l}\)。

那么对于一个\(k^{-y_i}\)，它会让\(c_{y_i}+1\)。

因此在不考虑进位的情况下，\(\sum\limits_{i=1}^lc_i=m\)。

进位实质上就是某一位\(-k\)，高位\(+1\)，反映到数位和上就是\(-(k-1)\)。

因此在考虑进位的情况下，\(\sum\limits_{i=1}^lc_i\equiv m(\mod k-1)\)。

当然也有\(\sum\limits_{i=1}^lc_i\le m\)。

对\(1-z\)做类似的分析。

我们可以发现\(1-z\)的数位和就是\(\sum\limits_{i=1}^l(k-1-c_i)+1=l(k-1)+1-\sum\limits_{i=1}^lc_i\)。

后面那坨就是\(z\)的数位和对吧。

与求\(z\)的数位和的性质的过程类似，我们有\(l(k-1)+1-\sum\limits_{i=1}^lc_i\equiv n(\mod k-1)\)。

以及\(l(k-1)+1-\sum\limits_{i=1}^lc_i\le 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}=\sum\limits_{o=\max(0,j-k)}^{j-1}(f_{i-1,o,0}+f_{i-1,o,1})\)。

前缀和优化一下就行了。

求答案的时候判一下第二维是否满足上面的\(z\)和\(1-z\)的\(4\)个条件（\(\sum c\le 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);

}

巴特西

AT2294 Eternal Average

最新文章

热门文章