6833. 2020.10.24【NOIP提高A组】T3.justice

有(n)个(x)和(m)个(y)，每次选(k)个数，删掉它们并加入它们的平均数。

问最后形成的数不同的方案数有多少个。

(n,m,kle 3000)

---

如果(x=y)显然；如果(x eq y)，结果和(x,y)的具体取值没有关系。

证明：操作的过程可以用一棵树来表示。设(x_i,y_i)分别表示深度。那么最终的取值为(xsum k^{-x_i}+ysum k^{-y_i})

假设我们得到了两组不同的(({x_i},{y_i}))，然后列个方程。

两边同时除以(x)，现在得到了一个与(frac{y}{x})有关的一元一次方程。

整理成(ax=b)的形式。

如果(x)有多个解，当且仅当(a=b=0)。显然不可能成立（不然可证两组(({x_i},{y_i}))相等）。

接着发现这个问题中(x=1)一定是解。

钦定(x=0,y=1)。最终权值为(sum k^{-y_i})。如果令(x=y=1)建一棵同构的树，那么有(sum k^{-x_i}+sum k^{-y_i}=1)。这启示我们：如果一个状态合法，当且仅当存在(z)可以如此表示：(z=sum k^{-y_i},1-z=sum k^{-x_i})

假如(z=sum_{i>0} c_ik^{-i})。如果不进位，(sum c_i=m)，进位后(sum c_i)减少(k-1)。所以(sum c_ile mand sum c_i=m pmod {k-1})。
类似的计算(1-z)的限制，如果小数点最后不为(0)的位置为(len)，则(1-z)的(sum c'_i=len(k-1)-sum c_i+1)。

最终问题变成了统计多少不同的合法(sum c_i)，直接DP解决。

---

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 3005
#define ll long long
#define mo 1000000007
int n,m,k;
ll x,y;
int mxd;
int f[N*2][N][2];
int main(){
	freopen("justice.in","r",stdin);
	freopen("justice.out","w",stdout);
//	freopen("in.txt","r",stdin);
	scanf("%d%d%d%lld%lld",&m,&n,&k,&x,&y);
	if (x==y){
		printf("1
");
		return 0;
	}
	mxd=(m+n-1)/(k-1);
	f[0][0][0]=1;
	for (int i=0;i<mxd;++i)
		for (int j=0;j<m && j<=i*(k-1);++j)
			for (int c=0;c<=1;++c){
				if (!f[i][j][c]) continue;
				for (int t=0;t<k;++t)
					(f[i+1][j+t][t!=0]+=f[i][j][c])%=mo;
			}
	ll ans=0;
	for (int i=1;i<=mxd;++i)
		for (int j=1;j<=m && j<=i*(k-1);++j){
			int j_=i*(k-1)-j+1;
			if ((m-j)%(k-1)==0 && j_<=n && (n-j_)%(k-1)==0)
				ans+=f[i][j][1];
		}
	ans%=mo;
	printf("%lld
",ans);
	return 0;
}