宋家庄网站建设,即将上市的手机,全国领先网站制作,服装网站建设需要什么内容2024/6/28UPD CSDN又擅自给我改VIP文章:(
前面七八周的题解就直接咕咕咕掉了 #xff08;要学的东西太多了#xff0c;实在是写不过来了#xff09;
在网上搜了许久都没有看到一篇非常详细的题解#xff0c;以至于我和巨佬基情激情 讨论了许久才搞懂#xff08;准确来讲…2024/6/28UPD CSDN又擅自给我改VIP文章:(
前面七八周的题解就直接咕咕咕掉了 要学的东西太多了实在是写不过来了
在网上搜了许久都没有看到一篇非常详细的题解以至于我和巨佬基情激情 讨论了许久才搞懂准确来讲是才把我讲懂。作为一个资深蒟蒻我深知一篇削微详尽的一篇题解对我的理解是多么重要。
鉴于这次只写一道题而且也不是很长所以就来写写吧~
先看题目 3 超级树 3.1 背景 如果一棵树除了叶节点外每个节点都恰有两个子节点那么称它为一棵满二叉树。 3.2 描述 一棵k-超级树可按如下方法得到取一棵深度为k的满二叉树对每个节点向它的所有祖先连边如果这条边不存在的话。例如下图是一个4-超级树的例子 现在你的任务是统计一棵k-超级树中有多少条每个节点最多经过一次的不同有向路径。两条路径被认为不同当且仅当它们经过的节点的集合不同或经过的节点的顺序不同。由于答案可能很大请输出总路径数对mod取模后的结果。 3.3 输入 一行两个整数k、mod意义见上。 3.4 输出 一行一个整数代表答案。 3.5 样例 样例输入1 2 100 样例输出1 9 样例输入2 3 1000 样例输出2 245 样例输入3 20 998244353 样例输出3 450500168 样例解释 对第一组样例将节点如图编号共有9条不同的路径1, 2, 3, 1−2, 2−1, 1−3, 3−1, 2−1-3, 3−1−2。 3.6 限制与约定 对于10%的数据k ≤ 4。 对于40%的数据k ≤ 10。 对于60%的数据k ≤ 100。 另有10%的数据mod 998244353。 对于所有数据1 ≤ k ≤ 3001 ≤ mod ≤ 109。 分析
首先对于一个 i - 超级树来说可以看作两棵 i-1 - 超级树加上一个根节点的组合于是我们可以将子树当做子问题来处理于是我们可以想到用DP来解决这个问题我考场上脑子想出毛病都没想出来。
我们设计一个诡异的DP状态自然是题解提供的状态我自己是肯定想不到的 我们定义 f [ i ][ j ] 为在一棵 i - 超级树中 选出 j 条 点不重复的路径 的方案数千万注意断句我就是这一点理解了好久当然如果你是用量词来判断那当我没说。就不管你咋选选出 j 条就行当然点不能重
转移
我们来考虑转移 首先我们枚举 l 和 r 分别表示左子树中选 l 条边右子树中选 r 条边。 我们计算出一个 n u m f [ i − 1 ] [ l ] ∗ f [ i − 1 ] [ r ] num f[i - 1][l] * f[i - 1][r] numf[i−1][l]∗f[i−1][r]表示在当前枚举状态下左右子树组合起来的方案数因为对于每一个 l 和 r 都会有多种不同的选取方案所以这里算出这些不同选取组合方案数可能我说的不太清楚可以自己理解一下主要是这东西画图也不好画大概只能抽象理解
转移分5种情况讨论 忽略这个根节点不选取这个根节点为任意一条边的节点则有 f [ i ] [ l r ] n u m f[i][lr]\; num f[i][lr]num 考虑以这个根节点为单独的一条路径这条路径上只有这一个点由于不影响子树内的方案选择仅仅只是对于每一个选取方案都加入了根节点这个路径于是有 f [ i ] [ l r 1 ] n u m f[i][l r 1]\; num f[i][lr1]num 考虑将这个根节点与左子树或右子树内的一条边连接起来于是有 f [ i ] [ l r ] n u m ∗ ( l r ) ∗ 2 f[i][l r]\; num * (l r) * 2 f[i][lr]num∗(lr)∗2怎么理解这个柿子呢我们考虑当前枚举状态下所有的方案中每一种方案都会有 l 种在左子树中选择方案选择一条路径与根相连 同样也会有 r 种在右子树中的选择方案于是有 n u m ∗ l n u m ∗ r num * l num * r num∗lnum∗r而因为超级树的定义一条路径的首和尾都可以和根相连于是我们乘以2如下图对于这样一条紫色路径我们都有以下两种连接方案如橙色所示 考虑分别在左右子树中选取一条路径与根节点连接成一条路径相当于总路径数减少了1于是我们有 f [ i ] [ l r − 1 ] n u m ∗ l ∗ r ∗ 2 f[i][l r - 1] \; num * l * r * 2 f[i][lr−1]num∗l∗r∗2解释与上一种情况近乎相同由于你的f[i - 1][ r ] (此时被记录在了num中)中已经包含了 r 的某一条路径的正反两种情况了所以这里是乘二而不是乘四这里可以理解为枚举 l 去找 rr 的两种已经包含在num中了而这里枚举的 l 却是只有一种所以要乘2 考虑我们在左子树或右子树中选取两条路径与根节点连接成一条路径与上一个同样于是我们有 f [ i ] [ l r − 1 ] n u m ∗ ( C l 2 C r 2 ) ∗ 2 f[i][l r - 1]\; num * (C_l^2 C_r^2) * 2 f[i][lr−1]num∗(Cl2Cr2)∗2考虑理解就是在同一棵子树中选两条边组合。
最后f [ k ][ 1 ]就是答案
空间注意
但是我们这样仍然有一个问题那就是我们考虑这样枚举的话我们的第二维空间必定会开到 2^k-1 这么大每一个点都可能成为一个独立路径这必定会爆掉。 于是我们考虑究竟有哪些状态可能对最终答案 f [ k ][ 1 ] 造成影响由于我们所有方程中都只有 “-1” 操作也就是说任何一个第二维大于 k 的状态都不可能对最终答案造成影响于是我们就只用递推到 k 即可也就是我们的第二维也只用开到k。
代码
最后来给出我的代码有详细的注释
//省略头文件和快读int k, MOD;int c2[MAXN];struct node {int val;node operator (const node x)const {node qwq;qwq.val (val x.val MOD) ? val x.val - MOD : val x.val;return qwq;//根据模的定义重载的加运算,可以快一点 }node operator * (const node x)const {node qwq;qwq.val 1ll * val * x.val % MOD;return qwq;}node operator * (const int x)const {node qwq;qwq.val 1ll * val * x % MOD;return qwq;}
}f[MAXN][MAXN];//f[i][j]表示一棵i-超级树中,选出 j条 点不重复 的路径 的方案数
//这里定义为结构体是为了使下面避免冗杂的取模运算//但似乎因为重载的特性,我就T成瓜娃子了 int main()
{freopen(tree.in, r, stdin);freopen(tree.out, w, stdout);k inpt(), MOD inpt();for(int i 1; i k; i) {c2[i] i * (i - 1) / 2;}f[1][0].val f[1][1].val 1 % MOD;for(int i 2; i k; i) {for(int l 0; l k; l) {for(int r 0; r k - l; r) {node num f[i - 1][l] * f[i - 1][r];//从左子树中选l条,从右子树中选r条 进行组合的方案数 f[i][l r] f[i][l r] num;//忽略这个根节点,选择lr个路径的方案数 f[i][l r 1] f[i][l r 1] num;//将根节点单独视为一个路径,但这样并不会影响左右子树的选取//所以可以直接加f[i][l r] f[i][l r] (num * (l r) * 2);//将根节点与左子树或右子树中的某一条路径相连的方案数//当前枚举状态下从左边选一条与根相连的有num * l * 2种,乘二是因为在该题意义下一条路径首尾都可以与根相连//右子树同理 //num中每一种方案都分别有(l r) * 2种选择方案,所以这里乘起来 f[i][l r - 1] f[i][l r - 1] (num * l * r * 2);//从左右子树中分别选一条路径与根相连//连上后相当于总路径条数少了一个所以是l r - 1f[i][l r - 1] f[i][l r - 1] (num * (c2[l] c2[r]) * 2);//从左子树或右子树中选两条不同路径与根相连 }}}printf(%d, f[k][1].val);fclose(stdin);fclose(stdout);return 0;
}需要注意的是由于重载运算符的特性他超级慢对于这道题最大数据慢了整整400ms于是这样的写法只能得到 85pts有且只有写单独函数的才能通过此题。
下面是没有注释的函数写法
//省略头文件和快读int k, MOD;int c2[MAXN];int f[MAXN][MAXN];void Add(int x, int y)
{x x y MOD ? x y - MOD : x y;
}int main()
{freopen(tree.in, r, stdin);freopen(tree.out, w, stdout);k inpt(), MOD inpt();for(int i 1; i k; i) {c2[i] i * (i - 1) / 2;}f[1][0] f[1][1] 1 % MOD;for(int i 2; i k; i) {for(int l 0; l k; l) {for(int r 0; r k - l; r) {int num 1ll * f[i - 1][l] * f[i - 1][r] % MOD;Add(f[i][l r], num);Add(f[i][l r 1], num);Add(f[i][l r], 1ll * num * (l r) * 2 % MOD);Add(f[i][l r - 1], 1ll * num * l * r * 2 % MOD);Add(f[i][l r - 1], 1ll * num * (c2[l] c2[r]) % MOD * 2 % MOD);}}}printf(%d, f[k][1]);fclose(stdin);fclose(stdout);return 0;
}虽然不是因为这道题的原因但是我改完以后莫名其妙的就暴杀标程了QwQ
希望以后做这套题的学弟能看到这篇博客吧祝你前程似锦。
贴上我看到的一句我很喜欢的话 亦悲亦喜才明白宿命的意义
