【AGC009E】Eternal Average

【AGC009E】Eternal Average

题面

洛谷

题解

神仙题.jpg

我们把操作看成一棵(k)叉树，其中每个节点有权值，所有叶子节点(共(n+m)个)就是(0)或(1)。

出了叶子节点外的所有节点就代表一次合并，权值就是他们的平均值。

设一开始(0)点的深度分别为(x_1,x_2...x_n)，(1)的深度为(y_1,y_2...y_m)。

那么根节点的权值为(sum (frac 1k) ^ {y_i})，而如果我们将所有点的权值改为(1)，则根节点权值也为(1)，那么有(sum (frac 1k) ^ {x_i}+sum (frac 1k) ^ {y_i}=1)，而如果满足这个条件，则一定可以构造出一种方案。

那么问题转化为有多少个(z)能写成(n)个((frac 1k)^x)，(1-z)能写成(m)个((frac 1k)^y)相加的形式。

我们将(z)表示为((0.c_1c_2...)_k)，那么若不进位(sum c=m)，而进位的话进位一次就减去(k-1)，那么(sum c=m(mod;k-1))。
假设小数有(len)位，那么(1-z)的和应为((len-1)(k-1)+k-sum c=len(k-1)-sum c+1)。

然后设(f_{i,j})表示到第(i)位，目前和为(j)的方案数即可，因为末尾不能为(0)，所以要多开一维记一下最后一位是否为(0)。
(大量参考litble的题解)

代码

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <cmath> 
#include <algorithm> 
using namespace std;
const int Mod = 1e9 + 7; 
const int MAX_N = 2e3 + 5; 
int N, M, K, ans; 
int f[MAX_N << 1][MAX_N][2], s[MAX_N]; 

int main () { 
	cin >> N >> M >> K; 
	f[0][0][0] = 1; 
	for (int i = 1; i <= N + M; i++) { 
		s[0] = (f[i - 1][0][0] + f[i - 1][0][1]) % Mod; 
		for (int j = 1; j <= N; j++) 
			s[j] = (s[j - 1] + (f[i - 1][j][0] + f[i - 1][j][1]) % Mod) % Mod; 
		for (int j = 0; j <= N; j++) { 
			f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % Mod; 
			if (j) f[i][j][1] = (s[j - 1] - (j - K >= 0 ? s[j - K] : 0) + Mod) % Mod; 
		} 
		for (int j = 0; j <= N; j++) 
			if (j % (K - 1) == N % (K - 1) && 
			    (i * (K - 1) - j + 1) % (K - 1) == M % (K - 1) &&
				i * (K - 1) - j + 1 <= M)
				ans = (ans + f[i][j][1]) % Mod; 
	} 
	printf("%d
", ans); 
    return 0; 
}