传送门:

AtCoder

洛谷


题目大意:

黑板上有n0m1,我们每次选择k个数字将其擦除,然后把它们的平均数写上去,这样一直操作直到只剩下一个数字,问剩下的这个数字有多少种不同的情况。

答案对10^9+7取模

1 \leqslant n,m \leqslant 2000,2 \leqslant k \leqslant 2000

保证n+m-1能被k整除。


%%%pyz

直接抄国集爷题解了…

我们用一棵有根树来描述这个过程:这棵树有N+M个叶子节点,其中N个标号为0M个标号为1。对于每个非叶子节点,它都有恰好K个儿子,并且它的标号是所有儿子标号的算术平均数。这个过程最终得到的数就是根结点的标号。

x_1 , \cdots , x_N表示所有标号为0的叶子的深度,y_1 , \cdots , y_M表示所有标号为1的叶子的深度。显然根结点的标号
\sum\limits _{i=1}^{m}K^{-y_i}

如果我们直接给出所有叶子的深度,如何判断能否构造这样一棵树呢?

显然,如果\sum\limits_{i=1}^{n}K^{-x_i} + \sum\limits_{i=1}^mK^{-y_i} = 1,就一定存在一组构造方案。考虑将所有叶子节点的深度从大到小排序,如果
它们满足上述条件,那么最大的K个一定相同(将和式的每一项表示成K进制数,如果和恰好为1,则最低位一
定会产生一个进位)。假设它们的深度均为d,我们就可以将它们合并成一个深度为d-1​的结点,从而构造出一
组解。

因此,对于任意有理数s \in (0,1),它能被构造出当且仅当:

  • \sum\limits_{i=1}^mK^{-y_i}=s
  • \sum\limits_{i=1}^nK^{-x_i}=1-s​

我们把s​写成K​进制的形式,令s=0.s_1s_2 \cdots s_t(s_t>0)​,容易证明,如果s​可以表示成恰好N​K^{-1}​的幂次
的和,那么它一定满足\sum\limits_{i=1}^ts_i \leqslant N​\sum\limits_{i=1}^t \equiv N ({\rm{mod}}~K-1)​,这样我们可以把K^{-d}​拆成K​K^{-d-1}​来使各
个数位上的和恰好等于N​

因此我们要求的就是满足以下条件的数列 的数量:

  • 0 \leqslant s_i < K

  • s_t > 0

  • \sum\limits_{i=1}^ts_i \leqslant N\sum\limits_{i=1}^t \equiv N ({\rm{mod}}~K-1)

  • \sum\limits_{i=1}^tK-s_i-1 \leqslant N-1\sum\limits_{i=1}^t K-s_i-1 \equiv N-1 ({\rm{mod}}~K-1)

考虑\rm DP,令f_{i,j}表示s的前i项和为j的方案数,我们可以通过一个简单的时间复杂度为O(n^2)\rm DP计算出
f,然后就能轻松计算出答案。

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
const int maxn=2e3+10;
int f[maxn<<1][maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int main(){
    int n=read(),m=read(),k=read(),len=(n+m-1)/(k-1),ans=0;
    for(int i=1;i<k;i++)f[1][i]=1;
    for(int i=2;i<=len;i++)
        for(int j=1;j<=n;j++){
            f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
            if(j>=k)f[i][j]=(f[i][j]-f[i-1][j-k]+mod)%mod;
        }
    for(int i=1;i<=len;i++){
        int tmp=max(0,i*(k-1)-m)+1;
        for(int j=n;j>=tmp;j-=k-1)ans=(ans+f[i][j])%mod;
    }write(ans);
    return 0;
}

发表评论