JZOJ 6833. 2020.10.24【NOIP提高A组】T3.justice（DP）

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

题目大意

• 有$n$个$x$和$m$个$y$，每次其中$k$个合并成一个，权值变为它们的平均值，求只剩一个数的权值有多少种可能。
• $n,m,k\le 3000$
• $x,y\le 10^{18}$

题解

• 如果$x=y$，那么答案是$1$，否则显然$x$和$y$无论是多少，答案都只和$n,m,k$有关。
• 直接令$x=0,y=1$，考虑把初始的$n+m$个数放在一棵$k$叉树上，$0$对最后权值的贡献是$0$，$1$对最后权值的贡献就是$(\frac{1}{k}{)}^{deep}$，其中$deep$为这个数的深度。
• 那么最后的数就是$V=\sum (\frac{1}{k}{)}^{deep}$，可以理解为是一个$k$进制下的小数，
• 如果没有进位，那这个数小数部分数位之和$S=m$，每进位一次$S$就要减去$k-1$，所以$S\equiv m(\mathrm{m}\mathrm{o}\mathrm{d}k-1)$，且$S\le m$.
• 在某种操作方式下，如果把$0$和$1$交换，那么$1-V$表示成的$k$进制数数位之和$S^{\prime }$就应该满足$S^{\prime }\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}k-1)$，且$S\le n$.
• 而此时的$S^{\prime }$是可以通过$S$计算出来的，若这个小数位数为$l$，则$S^{\prime }=(l-1)\ast (k-1)+k-S$，类似于$1.000\dots$减去某个数列竖式减法。
• 这样就相当于要构造一个$k$进制小数，满足数位和为$S$，$S$满足上面的限制，$S$对应的$S^{\prime }$也要满足上面的限制，求方案数。
• 设$f_{i,j}$表示前$i$位和为$j$的方案数，$O(n)$转移，总复杂度$O(n^3)$，用前缀和可以优化到$O(n^2)$。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define md 1000000007
#define ll long long 
#define N 3010
ll f[N * 2][N][2], g[N];
int main() {
	int n, m, k, i, j; ll x, y;
	scanf("%d%d%d%lld%lld", &m, &n, &k, &x, &y);
	f[0][0][0] = 1;
	for(i = 1; i <= (n + m) / (k - 1); i++) {
		g[0] = (f[i - 1][0][0] + f[i - 1][0][1]) % md;
		for(j = 1; j <= n; j++) g[j] = (g[j - 1] + f[i - 1][j][0] + f[i - 1][j][1]) % md;
		for(j = 0; j <= n; j++) {
			if(j) {
				if(j - k < 0) f[i][j][1] = g[j - 1];
				else f[i][j][1] = (g[j - 1] - g[j - k] + md) % md;	
			}
			f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % md;
		}
	}
	ll ans = 0;
	for(i = 0; i <= (n + m) / (k - 1); i++) {
		for(j = 0; j <= n; j++) 
			if(j % (k - 1) == n % (k - 1) && i * (k - 1) - j + 1 <= m) (ans += f[i][j][1]) %= md;
	}
	if(x == y) ans = 1;
	printf("%lld
", ans);
	return 0;
}