【题解】AGC 017 — Qiuly
AGC 017 A DP 即可。 const int N = 55; int n, p, a[N]; ll dp[N][2]; int main () { IN (n), IN (p); lep (i, 1, n) IN (a[i]), a[i] &= 1; dp[0][0] = 1; le 阅读更多…
【游记】HNOI2021 没翻车记 — Qiuly
Day -2 考了一套神仙题，dandandan 又虐场了，我又垫底了。后面被 ysu 吐槽了一句” 分太低了”（改了前两题，第三题是个巨大恶心多项式，就咕了。 Day -1 去桃花岭散心。 路上青山一直在讨论博弈论，被要求唱歌了（然后芙卡米也被要求唱歌了 后面发现了一条小 阅读更多…
【题解】CF1349D SLIME AND BISCUITS 概率与期望 — dabuliuzp
有 $n$ 个人，第 $i$ 个人有 $a_i$ 个饼干，每次随机选择一个饼干，将其随机分配给除了它现在所有者的其他 $n-1$ 个人，求使得一个人拥有所有饼干的期望步数，对 $998244353$ 取模。 $n\le 10^5 , \sum a_i\le 3\times 10^5$ 。 毒瘤题， 阅读更多…
【题解】UR #19 通用测评号 容斥，求导 – UOJ#514
题面 UOJ# #514.【UR #19】通用测评号 给定 $n$ 个燃料舱，容量为 $a$ 升 。每次会往没有满的燃料舱里面加 $1$ 升油，直到所有的燃料舱都至少包含 $b$ 升油。求最后满了的燃料舱个数期望。 数据范围：$n, a, b \le 250$。 题解 感觉这题的思想十分巧妙 qwq 阅读更多…
【算法】伯努利数相关 — Qiuly
公式挂了，所以请移步：这里
【算法】杨氏矩阵入门 — Qiuly
杨氏矩阵 简要定义： 一个 $N$ 的整数划分 $x_1+x_2+\cdots x_m = N$ ，满足 $x_1\geq x_2\geq\cdots\geq x_m>0$ 。考虑有 $m$ 行，第 $i$ 行有 $x_i$ 列的表格，称为杨图。将 $1$ 到 $N$ 这 $N$ 个正整数填进去并满 阅读更多…
【题解】雅礼集训 2017 Day7 题解 — Qiuly
「雅礼集训 2017 Day7」事情的相似度 注意到 最长公共后缀 其实是 SAM 上的 LCA ，因此原题变成了询问深度最深的 LCA 。 定义一个前缀在 parent 树上对应的点为其” 结束点”。考虑一个树上的点什么时候可能成为答案，注意到如果这个点的子树内有两个以上的 阅读更多…
【题解】雅礼集训 2018 Day1 题解 — Qiuly
「雅礼集训 2018 Day1」树 考虑令 $f_{i,j}$ 表示大小为 $i$ 的树，深度为 $j$ 的方案数。 一般的 DP 合并过程：枚举大小为 $a,b$ 的树，然后把 $b$ 的根接到 $a$ 的根下面。但是这样会算重：打个比方，以 $1$ 为根，儿子为 $2,3$ 的树会被算两次。 不 阅读更多…
【题解】「WC2018」通道 边分治 + 虚树 — Qiuly
简要题意：给你三棵树，二元组 $(x,y)$ 的贡献是 $x,y$ 在三棵树上最短路径经过的边边权之和，求贡献最高的二元组 $(x,y)$ 所产生的贡献。 考虑对第一棵树边分治，注意到边分治的好处就是直接将第一棵树上 $(x,y)$ 的贡献由原来连在一起的变成相对 $x ,y$ 独立的了。 按照&# 阅读更多…
【题解】CF1479D Odd Mineral Resource 随机化+主席树/莫队 — zhoukangyang
题面 CF1479D Odd Mineral Resource 给定一颗有 $n$ 个节点的树，每一个节点有一种颜色 $a_i$。$q$ 次询问，每次询问点 $x$ 到点 $y$ 的最短路径上是否有一种编号在 $[l, r]$ 的颜色，满足其出现次数为奇数。如果有，输出任意一个；否则输出 -1。 数 阅读更多…