@省选模拟赛03/16 - T3@ 超级树

目录

  • @description@
  • @solution@
  • @accepted code@
  • @details@

@description@

一棵 k-超级树(k-SuperTree) 可按如下方法得到:取一棵深度为 k 的满二叉树,对每个节点向它的所有祖先连边(如果这条边不存在的话)。

例如,下面是一个 4-超级树:

请统计一棵 k-超级树 中有多少条不同的简单有向路径,对 mod 取模。

input
一行两整数 k, mod。
output
一行一整数表示答案。

example
input1: 2 100
output1: 9

input2: 3 1000
output2: 245

input3: 20 998244353
output3: 450500168

explain
第一个样例的 9 条路径如下:
1, 2, 3, 1->2, 2->1, 1->3, 3->1, 2->1->3, 3->1->2。

@solution@

神仙树。

你问我为什么 3/27 要写 3/16 的模拟赛题解?
因为我热爱文化课。
题解就少说点,我要去准备月考了。

对于某一条路径:
要么它完全在左右某一棵子树中,可以转换为子问题;
要么它肯定经过根节点,这种情况再分成几类:
(1)只包含根节点。easy。
(2)以根节点作为终点/起点。easy。
(3)从左子树/右子树到另一颗子树。easy。
(4)从左子树/右子树回到这棵子树。……

好像第 4 类不可做的样子。我们需要求解一棵子树含有两条不相交路径的方案数。

既然如此,就再加一维状态。定义 dp(i, j) 表示深度为 i 的超级树选出 j 条不相交路径的方案数。
因为增加一个根节点最多只会将两条路径合并,即总路径数减一,故 j ≤ k。

然后就是非常简单的 O(n^3) 的 dp 题了。
最后答案为 dp(k, 1)。

@accepted code@

#include<cstdio>
const int MAXN = 500 + 5;
int dp[MAXN][MAXN], k, mod;
inline int add(int a, int b) {return (a + b) % mod;}
inline int mul(int a, int b) {return 1LL * a * b % mod;}
int main() {
    scanf("%d%d", &k, &mod); dp[0][0] = 1;
    for(int i=1;i<=k;i++)
        for(int p=0;p<=k;p++) {
            if( dp[i - 1][p] == 0 ) continue;
            for(int q=0;q<=k;q++) {
                if( dp[i - 1][q] == 0 ) continue;
                int x = mul(dp[i - 1][p], dp[i - 1][q]);
                dp[i][p + q] = add(dp[i][p + q], mul(x, add(1, mul(2, add(p, q)))));
                dp[i][p + q - 1] = add(dp[i][p + q - 1], mul(x, add(mul(2, mul(p, q)), add(mul(p, p - 1), mul(q, q - 1)))));
                dp[i][p + q + 1] = add(dp[i][p + q + 1], x);
            }
        }
    printf("%d\n", dp[k][1]);
}//本地卡常,还没卡过。因此仅供参考。

@details@

暴力加一维状态的神仙操作。

写到一半我突然明白为什么要求是有向的路径……路径数变为原先的两倍,就不用求 2 的逆元。
出题人真懒。

原文地址:https://www.cnblogs.com/Tiw-Air-OAO/p/10607000.html

时间: 03-27

@省选模拟赛03/16 - T3@ 超级树的相关文章

[模拟赛10.12] 老大 (二分/树的直径/树形dp)

[模拟赛10.12] 老大 题目描述 因为 OB 今年拿下 4 块金牌,学校赞助扩建劳模办公室为劳模办公室群,为了体现 OI 的特色,办公室群被设计成了树形(n 个点 n ? 1 条边的无向连通图),由于新建的办公室太大以至于要将奖杯要分放在两个不同的地方以便同学们丢硬币进去开光,OB 想请你帮帮他看看奖杯放在哪两个办公室使得在任意一个在劳模办公室做题的小朋友能最快地找到奖杯来开光. 一句话题意:给出一个 n 个点的树,在两个合适且不同的点放上奖杯,使得每个点到最近的奖杯距离最大值最小. 输入

2018.3.10 省选模拟赛

从这里开始 概况 Problem A 三元组 Problem B 攻略 Problem C 迂回 概况 这是省选T1合集?还是欢乐AK赛? 全班一半以上的人三道题都会做qwq. Doggu还剩一小时时以为自己AK了,然后玩了一小时.虽然最终被卡了20分的常数. ZJC 1个半小时AK?Excuse me? 我这条大咸鱼到最后10分钟才敲完了T1,然后发现线段树要T掉. 发自内心鄙视垃圾出题人卡常数,本来的欢乐AK变成280. 教练给我们考4个小时的试,题面上也这么写的,看题解,woc,考试时间3

2018.2.12 省选模拟赛

题目大意 (题目很简洁了,不需要大意) 其实显而易见地可以发现,当被卡一次后后面的路程都是固定了的. 可以用类似动态规划的思想来进行预处理.现在的问题就是怎么知道在某个位置刚等完红灯然后出发会在哪个路口再次被卡. 尝试画一画图: 其中横轴表示位置,纵轴表示时间,长方体表示红灯时段.有用的部分长度只有$r + g$,所以在模意义下弄一下就可以减少很多重复和无用状态: 但是这样仍然不好处理上面提到的问题,考虑让线段横着走,第一个撞着的长方形就是答案.为了实现这个目标,就每个长方形向下移动一段(移动的

2018/3/29 省选模拟赛 80

我真是太菜了... T1 10分纯暴力没写,20分容斥也没写(人就是懒死的).还有30分矩乘不会 正解 <IOI2018 中国国家集训队第一阶段作业题解部分 - 杭州第二中学 吴瑾昭.pdf>最后一题 T2  以为自己能拿到50分,但是其实那个暴力算法只能过10分的点,n=2000的20分数据用n^3带剪枝过不了,所以拿了30分. 正解 <计数与期望问题选讲 CLJ.pdf>最后一题 我记得我以前好像看到过这个文档但是没读过..今天读一下 T3 依然是分情况50分,30分树归20分

xjoi省选模拟赛_14

T1 发现 对于当前 投出 奇数次向上的概率为 p 那么 若加入一个 pi=0.5 的骰子 发现  p奇 +1=p奇 * 0.5+p偶 * 0.5 = p偶+1  也就是说 只要方案中存在一个 p=0.5 的骰子 这个方案必然合法  : 1 #include <bits/stdc++.h> 2 #define N 100 3 #define eps 1e-7 4 using namespace std; 5 typedef long double ldb; 6 int t,n; 7 ldb A

2018/3/9 省选模拟赛 0分

第二题模拟扫一遍就可以过,不能更划算了.q=1的30分写的比100分还麻烦,有趣哦. 破暴力40分也没什么可写了,日常辣鸡吃枣药丸. 原文地址:https://www.cnblogs.com/137shoebills/p/8533870.html

2018/3/27 省选模拟赛 140分

T1 树归 100 T2 写的快速幂卷积 40,超时了,正解是矩阵乘法之类的. 正解 1 暴力(m<=5):将x的所有约数提出来矩阵乘法 2 3 定义乘法同构: 4 A=p[1]^a[1] * p[2]^a[2] * ... * p[n]^a[n] 5 B=q[1]^b[1] * q[2]^b[2] * ... * q[n]^b[n] 6 其中p[i]与q[i]皆为质数 7 将数组a与b降序排序后如果是完全相同的,那么称A与B是乘法同构的 8 如 2*2*2*2*3*3*5 与 7*11*11*

省选模拟赛20180416

上午 T1 提答送了40分拿了20. T2 费用流,不会 暴力骗分40 T3 dp变成四个方向的转移优化掉一个m^2 不会 暴力分都没拿全只有50 下午 T1 dp+扫描线,不会扫描线,60分暴力 T2  40分二分,100分要找规律不会找,二分写炸了只有20分. 原文地址:https://www.cnblogs.com/137shoebills/p/8858110.html

2018.6.29 省选模拟赛

*注意:这套题目应版权方要求,不得公示题面. 从这里开始 Problem A 小D与电梯 Problem B 小D与田野 Problem C 小D与函数 Problem A 小D与电梯 题目大意 假设电梯在0层,容量无限大.给定$n$个人的到达时间和要去的楼层.电梯上下一层楼花费的时间为1,电梯开关门.乘客上下的耗时不计,电梯可以停留在某一层楼.问将所有人送达到目的地,并让电梯回到0层的最少耗时. 先按到达时间将所有人排序.显然,每次电梯运输的人是一段连续的区间中的人. 用$f[i]$表示将前$