[CF 965E]Short Code

你有\(n\)个两两不同的串,你要将每个串变成其的一个前缀,使得变换后的所有串仍然两两不同,并且所有串长度和尽可能小,输出这个和。

\(n\leq 10^5\),所有串长之和不超过\(10^5\)。

继续阅读

[BZOJ 3512]DZY Loves Math IV

给定正整数\(n, m\),求\(\sum_{i = 1}^n\sum_{j = 1}^m \varphi(ij)\),膜\(10^9+7\)输出。

\(n\leq 10^5, m\leq 10^9\)。

继续阅读

[BZOJ 4916]神犇与蒟蒻

给定\(n\),分别求出\(\mu(x^2)\)和\(\varphi(x^2)\)的前\(n\)项和。

\(1\leq n\leq 10^9\)。

继续阅读

[LibreOJ 2538][PKUWC2018]Slay the Spire

给定一个\(2n\)张卡的卡组,其中有\(n\)张强化卡(其权值为一大于\(1\)的整数),\(n\)张攻击卡(其权值为一正整数)。在一次游戏中,你需要有序的打出一些卡牌,如果说你打了一张权值为\(x\)的攻击卡,那么对对方造成\(x\)点伤害;如果说你打出了一张权值为\(x\)的强化卡,那么之后所有伤害乘上\(x\)。

现在,你需要随机从卡组中抽出\(m\)张牌,然后选出其中的\(k\)张照一定顺序打出,要求使得产生的伤害最大化。求伤害的期望,答案乘\(\binom{2n}{m}\)再膜\(998244353\)输出。

\(1\leq k\leq m\leq 2n\leq 3000, 1\leq x\leq 10^8\)(其中\(x\)为牌的权值)。

多组数据,满足\(\sum 2n\leq 30000\)。

继续阅读

[CF 900F]Unusual Sequence

求有多少正整数序列,满足所有数的最大公约数为\(x\),所有数的和为\(y\)。

\(1\leq x, y\leq 10^9\)。

继续阅读

[LibreOJ 2803][CCC2018]平衡树

假设每个结点都有正整数权值,那么我们定义完美平衡树:权值为\(1\)的单点树是完美平衡树;根的权值为\(w(w\geq 2)\)的话,那么它一定有\(k(2\leq k\leq w)\)个子树,每个子树要完全一致,并且每个子树的根权值都要是\(\lfloor\frac{w}{k}\rfloor\)。

给定\(N\),计算根权值为\(N\)的完美平衡树的数量。

\(1\leq N\leq 10^9\)。

继续阅读

[LibreOJ 6433][PKUSC2018]最大前缀和

给你一个长为\(n\)的整数序列\(a\),求出将序列随机打乱之后的最大前缀和(不能选空前缀!)的期望,答案乘上\(n!\)之后对\(998244353\)输出。

\(1\leq n\leq 20, \sum_{i = 1}^n |a_i|\leq 10^9\)。

继续阅读

[UOJ 207]共价大爷游长沙

给你一棵\(n\)个点的树,要求你滋磁以下操作(共\(m\)次):

  • 对于给定的点对\((x, y)\)和\((u, v)\),删除边\((x, y)\),添加边\((u, v)\)。保证操作时\((u, v)\)存在,并且保证操作后的图还是一棵树。
  • 向集合\(S\)中加入一个点对\((u, v)\)。
  • 从\(S\)中删除一个点对。
  • 给定一条边\((x, y)\)(保证在当前树中存在),求问是否所有\((u, v)\in S\)都满足\(u\)到\(v\)的路径经过了\((x, y)\)。

\(1\leq n\leq 10^5, 1\leq m\leq 300000\)。

继续阅读

[LibreOJ 2316][NOIP2017]逛公园

给你一张\(n\)个点\(m\)条边的有向图,设从\(1\)到\(n\)的最短路为\(d\),那么请问有多少\(1\)到\(n\)的路径(可以是非简单路径)满足其长度在\([d, d + K]\)中,如果答案为无限大的话输出\(-1\)。

\(1\leq n\leq 10^5, 1\leq m\leq 2\times 10^5, 0\leq K\leq 50\)。

继续阅读

[UOJ 14][UER #1]DZY Loves Graph

一张\(n\)个点的图,初始没边,然后要求你支持以下操作:

  • 给定\((x, y)\),在\(x\)和\(y\)两点间添加一条长度为\(i\)的边(假设这是第\(i\)次操作)。
  • 给定\(k\),删除当前图中边权最大的\(k\)条边。
  • 撤销上一次操作。保证存在上一次操作且不是撤销操作。

共\(m\)次操作,每次操作后输出当前图最小生成树的边权和(不存在的话输出\(0\))。

\(1\leq n\leq 300000, 1\leq m\leq 500000\)。

继续阅读