Submission #3419258

---

Source Code Expand

/*
可以用一颗有根树来描述题目给定的过程。这颗有根树的每个非叶子节点有恰好K个儿子，描述了一次合并。叶子共有N + M个，N个点权是0，M个点权是1
每个非叶节点的点权是所有孩子点权和的平均值。题目所要求的就是根节点的点权有多少种可能的取值
可以发现，根节点的点权取决于所有叶子对其的贡献。叶子u对根节点点权的贡献是V[u] / K^Deep[u]，Deep[u]是u到根节点需要经过的边数
*/
/*
性质1：Sum{1 / K^Deep[u]   |   u是一个叶子} = 1
       这可以归纳证明：合并过程的任意时刻，每个根节点r的Sum{1 / K^Deep[u]   |   u是r子树中的叶子} = 1。这里Deep[u]是u到r需要经过的边数
                       初始该条件显然成立。每次合并的时候，新的根有K个儿子，每个儿子对其的贡献都是1 / K，所以该条件仍然成立。那么也就证明了该结论
性质2：如果确定了最终每个叶子的深度，那么只要满足Sum{1 / K^Deep[u]   |   u是一个叶子} = 1，就一定可以构造出满足条件的树
       给出构造的过程：当只有1个Deep = 0的点的时候，构造直接完成
                       否则选出Deep[u]最大的点，显然Deep[u] >= 1。这些点的个数一定是K的倍数，否则考虑K进制，Sum{1 / K^Deep[u]} = 1一定不满足
		       那么直接选出K个点合并成为一个深度为Deep[u] - 1的根节点的儿子，继续按照该过程构造即可
根据以上两条性质，可以得出，一个确定每个叶子深度的方案是合法的   <=>   Sum{1 / K^Deep[u]   |   u是一个叶子} = 1
*/
/*
回到题目，设根节点的权值为s，s = Sum{1 / K^Deep[u]   |   u是一个叶子且V[u] = 1}，那么有1 - s = Sum{1 / K^Deep[u]   |   u是一个叶子且V[u] = 0}
只要能找到恰好M个u满足Sum{1 / K^Deep[u]} = s、恰好N个u满足Sum{1 / K^Deep[u]} = 1 - s，就说明s是可行的
判断能否找到恰好X个K的负次幂使得它们的和 = S，是一个经典问题，按照如下两个步骤构造即可：
(1)考虑S在K进制下的数位和D，显然需要有D <= X，令X的初始值X' = D
(2)当0 < X' < X时，可以把1个K^(-e)拆成K个K^(-e - 1)使得X' += K - 1，故需要满足D = X(mod K - 1)
直接dp在K进制下s的值，F[i][j]表示考虑到了K^(-i)，s当前数位和为j的方案数，根据j可以推算出1 - s的数位和
*/

#include <cstdio>
#include <cstring>

using namespace std;
const int Max_N(2050);
const int MOD(1000000000 + 7);

constexpr int Add(int a, int b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}

constexpr int Sub(int a, int b)
{
	return a - b < 0 ? a - b + MOD : a - b;
}

int N, M, K, Ans, F[Max_N], Pre[Max_N];

inline bool check(int X, int D)
{
	return D == X || (0 < D && D <= X && D % (K - 1) == X % (K - 1));
}

int main()
{
	scanf("%d%d%d", &N, &M, &K);
	Ans = (check(M, 1) && check(N, 0));
	F[0] = 1;
	for (int i = 1;(K - 1) * i + 1 - M <= N;++i)
		for (int j = 0;j <= M;++j)
		{
			if (j == 0)
				Pre[j] = 0;
			else
				Pre[j] = Pre[j - 1];
			Pre[j] = Add(Pre[j], F[j]);
			if (j)
				F[j] = Sub(Pre[j - 1], j - K >= 0 ? Pre[j - K] : 0);
			else
				F[j] = 0;
			if (check(M, j) && check(N, (K - 1) * i + 1 - j))
				Ans = Add(Ans, F[j]);
			F[j] = Add(F[j], Sub(Pre[j], j >= 1 ? Pre[j - 1] : 0));
		}
	printf("%d", Ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &K);
                             ^

Judge Result