mydcwfy's Blog

题意：给定一棵 $n$ 个点的以 1 为根的树和一个删除序列，每次删除一个 $[2, n]$ 之类的点，当对于任意一个删除的点都有其所有子树的点都被删除时，答案加上删除点的连通块个数。一棵树的价值为最后删除完的答案。动态修改树，删除一条边，加上一条边，保证还是树。实时维护答案。$n, q\leq 5\times 10 ^ 5$。

题意：给定一棵 $n$ 个点的有根树和 $m$ 条直上直下的链，问有多少种给每条边赋值 0 或 1 的方案数使得 $m$ 条链至少有一个 1。$n, m\leq 5\times 10 ^ 5$，2s，1024 MB。

题意：有一棵 $n$ 个点的有根树，每个点有 $a_i$ 个苹果，在 $i$ 处选一个苹果的价值是 $v_i$，一个节点能选苹果当且仅当他的父亲也选了至少一个。假设选的最大深度是 $d$，选了 $t$ 个苹果，要求 $t - d\leq k$，$k$ 给定。求能获得的最大价值。$T(T\leq 5)$ 组数据，$n\leq 2\times 10 ^ 4$，$ k\leq 5\times 10 ^ 5$，$nk\leq 2.5\times 10 ^ 7$，$1\leq v_i\leq 100$，5s。

题意：给定左右各 $n$ 个点的二分图和 $m$ 种边，每一种边有三种情况：

1. 这种边只有一条，有 $50\\%$ 的概率出现。
2. 这种边有两条，同时出现或者不出现，概率均为 $50\\%$。
3. 这种边有两条，分别出现，概率均为 $50\\%$。

求完美匹配的期望数量，对 $10 ^ 9 + 7$ 取模。$n\leq 15$。

题意：求 $\sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(ij)\bmod 998244353$。$T(T\leq 10 ^ 5)$ 组数据，$n, m\leq 10 ^ 5$，4s，64MB。

题意：求 $\prod_{i = 1} ^ n \sigma_0(i) ^ {i + \mu(i)}$。$n\leq 10 ^ {11}$，对 $10 ^ {12} + 39$ 取模，$T(T\leq 3)$ 组数据，15s。

题意：给定一个 $n$ 个点 $m$ 条边的无向图，问有多少个 $m$ 条边组成的集合使得只有这些边存在让 $n$ 个点构成一个边双连通分量。$n\leq 10$，对 $10 ^ 9 + 7$ 取模。

题意：给出 $n$ 个点，每个点有一个权值，$a_i\geq 0$ 表示这个点是好的，否则是不好的。任意构造一棵生成树，定义和至少一个好点连边的点是非常好的。求所有非常好的点权值和 $\leq lim$ 的方案数。$n\leq 40$，$-1\leq a_i\leq 2.5\times 10 ^ 8$，$lim\leq 10 ^ 9$。

题意：问在 $n\times m$ 的网格上染 $c$ 种颜色，问满足任意两行都不相同、任意两列都不相同的方案数。$n, m\leq 4000$，对 $10 ^ 9 + 7$ 取模。

题意：有一个字符集为 A, C, G, T 的字符串 $S$，问有多少个长度为 $n$ 的字符串 $T$ 满足 $\mathrm{LCS}(S, T) = i$。你需要输出所有 $i\in [0, |S|]$ 的答案。$|S|\leq 15$，$n\leq 1000$。

题意：给定一个长度为 $n$ 的序列 $a$，修改为区间乘 $x$，询问为求 $\varphi(\prod_{i = l} ^ r a_i)$。$n\leq 4\times 10 ^ 5$，$q\leq 2\times 10 ^ 5$，$a_i, x\leq 300$。

题意过于神秘，就没有简述了。

题意：问点数为 $n$ 的本质不同无向图个数。$n\leq 60$，对 997 取模。

题意：给定 $n$ 个二进制下 $m$ 位的数，问有多少个集合 $S$ 包含这 $n$ 个数并且满足取反、与运算封闭（即任意对 $S$ 集合内部元素取反或者是与运算操作得到的数都 $\in S$），问都多少个这样的 $S$。$m\leq 1000$，$n\leq 50$，对 $10 ^ 9 + 7$ 取模。

题意：给定长度为 $n$ 序列 $a$，每次随机选择 $i\in [1, n]$，将 $r$ 加上 $\prod_{j\ne i} a_j$，然后让 $a_i$ 减 1。问 $k$ 次操作后，$r$ 的期望。$n\leq 5000$，$k\leq 10 ^ 9$，对 $10 ^ 9 + 7$ 取模。

顺风场，vp 的时候打到了 rk 27 左右，补题也还不算很困难。

题意：有 $n$ 个串只包含 A, B, C, D 的 $S_i$，问是否存在一个 $T$，经过删除 $T$ 中存在的 $S_i$ 直到不存在任意一个 $S_i$ 后，可以得到不同的串。$n, \sum |S_i|\leq 2\times 10 ^ 6$，8s。

有趣的比赛，做题 + 改题一共交了 35 次……

经典 SAM 题目，似乎有很简洁的做法，但没写……

现在才来补 NOI 经典题 /kk