C、D题解解析

发表于 2020-11-12 更新于 2023-12-07 分类于测试

首先本人并不会做这两道题，以下只是对题解的理解

猪国杀

题目描述

《猪国杀》是一款热门的桌上游戏，该游戏以身份、势力或阵营等为线索，以卡牌为形式，合纵连横，经过一轮一轮的谋略和动作获得最终的胜利。《猪国杀》集合历史、文学、美术等元素于一身，在OI界广受欢迎。

在《猪国杀》游戏中，牌堆中牌的数量是无穷大的，并且每一张牌的点数都是在$[1,A]$内均匀随机的正整数。

游戏中有多种武将，每个武将有其独特的技能，其中一个技能描述如下：

称猪：每当你受到一次伤害后，你可以亮出牌堆顶的$n$张牌。然后获得其中任意数量点数之和不大于$m$的牌，将其余的牌置入弃牌堆。

现在询问如果“称猪”时总是获得尽量多的牌，那么单次发动“称猪”期望能获得几张牌。

输入格式

一行三个整数$n,m,A$。

输出格式

输出一行一个整数表示答案，对998244353取模。

样例一输入

4 12 13

样例一输出

844808106

样例二输入

4 13 13

样例二输出

76298711

样例三输入

48 47 22

样例三输出

127439024

数据范围与约定

本题采用子任务捆绑测试。对于每个子任务，你只有通过了这个子任务的所有数据，才能获得这个子任务的分数。

对于所有的数据，满足$1\leq n\leq 100\ \ 1\leq m,A\leq 1000$。

子任务$1$（$2$0分）：$n,m,A$
子任务$2$（$20$分）：$n,m,A\leq 50$
子任务$3$（$20$分）：$n\leq 5$
子任务$4$（$20$分）：$m,A\leq 5$
子任务$5$（$20$分）：没有额外的限制

题解

最优策略肯定是取所有牌中点数最小的几张

考虑固定选了哪些牌，并求出有多少个方案使得选的牌中前几个恰好是这些，那么有

$ans \times A^n = \sum_{i=0}^{n}\sum_{j=1}^{A}\sum_{k=1}^{n-i}g_{i,j-1,m-j\times k}\times \binom{n}{i} \sum_{t \geq k}\binom{n-i}{t} \times (A-j)^{n-i-t}$

其中$g_{i,j,k}$表示有多少个长度为$i$的正整数序列满足每一个数字不大于$j$且所有数字总和不超过$k$

大概就是枚举选的牌中的最大值$j$，最大值个数$k$，以及选了$i$个小于$j$的牌。

可以用背包计算，也可以枚举有多少个数字大于$j$容斥计算，那么有

$ans \times A^n = \sum_{i=0}^{n}\sum_{j=1}^{A}\sum_{k=1}^{n-i}\left(\sum_{t=0}^i (-1)^t\binom{i}{t}\binom{m-k\times j-t \times(j-1)}{i}\right)\times \binom{n}{i} \sum_{t \geq k}\binom{n-i}{t} \times (A-j)^{n-i-t}$

组合数为$0$的时候能直接跳过，那么直接按照上式计算大概是$O(n^2m\log m)$的。

个人理解

首先第一个方程不难理解，$i+k$就是最后选的数。

Q: 题目问的不是出牌数的期望吗，为什么算出方案后不$\times (i+k)$？

A: 因为每个方案都会被算$i+k$次，考虑$(3,3,3,5,5,8,6)$这样的序列，如果是最后选了前五个，你会发现选前四个的时也会分别枚举这个状态（注意状态不仅仅是序列有哪些数，还有最后选出的是哪些），也就是说每个状态会被选的数更少状态枚举到，恰好$i+k$次

解释下最后的容斥是什么意思。

\[g_{i,j,k}=\sum_{t=0}^i (-1)^t\binom{i}{t}\binom{k -t \times j}{i}\]

这东西并不是插板法，因为并不要求把$k$选完。

只是往一个方向选，最后一边空出来。

这样就满足了和$\leq k$的条件。

但是你发现不一定满足单个不大于$j$的条件，所以把大于$j$的拿出来减去，多减去的又加上......

数树(count)

题目描述

给定两颗树$T1,T2$，求$T1$有多少个连通块与$T2$同构。

树$A$与树$B$同构当且仅当存在一个$A$的点集到$B$的点集的双射$f$，且存在一个$A$的边集到$B$的边集的双射$g$将边$(x,y)$映射到边$(f(x),f(y))$。换一种说法，即存在一种将$A$重标号的方案使得$A$与$B$完全相同。

输入格式

第一行一个整数$n$表示$T1$的点数。

接下来$n-1$行每行两个整数描述$T1$中的一条边。

接下来一行一个整数$m$表示$T2$的点数。

之后$m-1$行每行两个整数描述$T2$中的一条边。

输出格式

输出一行一个整数表示答案，对998244353取模。

样例一输入

样例一输出

样例二

见下发文件中的count/count2.in和count/count2.out

数据范围与约定

本题采用子任务捆绑测试。对于每个子任务，你只有通过了这个子任务的所有数据，才能获得这个子任务的分数。

对于所有的数据，满足$n\leq 3000\ \ m\leq 10$。

子任务$1$（$2$0分）：$n,m$
子任务$2$（$20$分）：$n \leq 50$
子任务$3$（$10$分）：$T2$是一条链
子任务$4$（$10$分）：$T2$中所有边都有一端是$1$号点
子任务$5$（$40$分）：没有额外的限制

题解

可以考虑求出$T1$的每个连通块有多少个双射$f$是合法的之和，然后除去$T2$的自同构方案数即可。

我们只要固定一个$T1$的根即可，但是需要枚举$T2$的根并每次进行dp。

令$dp_{u,S}$表示$u$的儿子已经向$T2$的$S$中的点建立双射的方案数，每次枚举当前儿子与哪个点建立双射进行转移。

然后将$T1$每个点与$T2$的根配对的方案数加起来。

时间复杂度$O(nm^2 2^m)$。

个人理解

首先题目要求算答案的不要求顺序，算$T2$的自同构方案就相当于除掉顺序，如果你想一步到位还得判重就很麻烦...

其次，很难对某个联通块换根什么的，所以每次枚举$2$的根是等效的。

转移的时候判断孩子$v$能不能双射到$T2$某个点$p$上，其实取决于$v$的孩子能不能双射到$p$的孩子上。

根据$dp$数组的定义，$v$的子树双射的方案数也就是它孩子们的双射方案数。

$std$的代码很牛逼，忍不住抄了一份。

//copy and paste from std
#include<bits/stdc++.h>
using namespace std;

const int N = 3005, MOD = 998244353, M = 1024;
int dp[N][M], son[12], S, lg[M];

int fpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = a * 1ll * a % MOD) if (b & 1) res = res * 1ll * a % MOD;
	return res;
}
struct Tree {
	int n;
	vector<int> e[N];
	void input() {
		scanf("%d", &n);
		for (int i = 1; i < n; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			e[u].push-back(v);
			e[v].push-back(u);
		}
	}
	void init(int u, int fa) {
        son[u] = 0;
        for (int v : e[u]) {
        	if (v == fa) continue;
            init(v, u);
            son[u] |= 1 << (v - 1);
        }
	}
	void dfs(int u, int fa) {
		dp[u][0] = 1;
        for (int v : e[u]) {
        	if (v == fa) continue;
        	dfs(v, u);
        	for (int i = S; i >= 0; i--) if (dp[u][i]) {
        		int t = dp[u][i];
        		for (int tt = S ^ i; tt; tt -= (tt & -tt)) {
        			int p = lg[tt & -tt];
        			if (dp[v][son[p + 1]]) dp[u][i | (1 << p)] = (dp[u][i | (1 << p)] + t * 1ll * dp[v][son[p + 1]]) % MOD;
        		}
        	}
        }
	}
} T1, T2;

int main() {
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
	int ans1 = 0, ans2 = 0;
	T1.input();
	T2.input();
	S = (1 << T2.n) - 1;
	for (int i = 0; i < T2.n; i++) lg[1 << i] = i;
	for (int i = 1; i <= T2.n; i++) {
		memset(dp, 0, sizeof dp);
		T2.init(i, 0);
		T1.dfs(1, 0);
		for (int j = 1; j <= T1.n; j++) ans1 = (ans1 + dp[j][son[i]]) % MOD;
	}
    T1 = T2;
    for (int i = 1; i <= T2.n; i++) {
    	memset(dp, 0, sizeof dp);
    	T2.init(i, 0);
    	T1.dfs(1, 0);
    	ans2 = (ans2 + dp[1][son[i]]) % MOD;
    }
    printf("%lld\n", ans1 * 1ll * fpow(ans2, MOD - 2) % MOD);
    return 0;
}