问题引入 问题来源：CF348D Turtles。 一个有障碍物的 $N\times M$ 网格图上，两只乌龟分别从 $(0,0)$ 点爬到 $(N-1,M-1)$ 点，询问路径不相交的方案数。 $N,M\leq 3000$ 。 首先问题可以转化为：两个人分别从 $A_0(0,1)$ 和 $B_0(1,0)$ 点出发，分别走到 $A_1(N-2,M…

AC代码 C. Cells 给定大小为 $N$ 的数组 $A$ ，询问 $N$ 个人分别从点 $(0,A_i)$ 出发前往 $(i,0)$ 且路径不相交的方案数。 $N\leq 5\times 10^5, A_i\leq 10^6$ 。 光从题面考虑，这就是LGV引理的模板题，但是求行列式的复杂度高达 $N^2(N+\log MOD)$ ，因此难以…

2021牛客暑期多校训练营5 AC代码 B. Boxes 箱子中有黑或白的球，开箱需要花费，也可以花费一定代价询问剩余箱子中黑白球的数量，求解要知道所有球颜色的代价的期望。首先考虑把所有箱子打开的代价，其次考虑一开始进行询问后代价花费的期望。通过找规律可以得到询问后每个箱子需要打开的几率，然后取两种方式较小值的答案。 C. Cheating and…

2021“MINIEYE杯”中国大学生算法设计超级联赛（4） AC代码 1001 Calculus 给定一个函数求函数极限是否存在，如果所有系数均为0极限存在，否则不存在。 1002 Kanade Loves Maze Designing 给定一棵树，需要求出任意两点直接不同元素的数量。直接进行 $n$ 次dfs即可。 1004 Display S…

题目来源：AIsing Programming Contest 2020 F - Two Snuke 已知：$s_2>s_1,n_2>n_1,u_2>u_1,k_2>k_1,e_2>e_1$ 且均为非负整数，计算： \begin{aligned} \sum_{s_1 + s_2 + n_1 + n_2 + u_1 + …

2021暑假训练dp优化题解 AC Codes A - GTY's birthday gift 矩阵优化dp 给出序列 $a$ ，每次从序列选两个数相加后，将新数加入序列 $a$ 问操作 $k$ 次后序列的和最大为多少 序列和最大，每次选当前最大和次大相加， $dp[i]=d[i-1]+dp[i-2]$ ，由于 $k$ 范围大，无法直接模拟。考虑到…

题目来源：ACL Beginner Contest F - Heights and Pairs。 给定一个大小为 $2N$ 的数组 $H$ ，要求将 $H$ 中的元素两两匹配，使得恰好构成 $N$ 个数对 $(H_i,H_j)$ 满足 $H_i\neq H_j$ 。 $N\leq 50000, H_i\leq 100000$ 。 首先容易想到通过容…

多项式基本操作 多项式加法、减法 有手就行。 多项式乘法 一句话概括，就是FFT。 这是整个多项式章节中最基础的一部分：如何用FFT将两个 $n$ 度的多项式乘法优化到 $O(n\log n)$ 的时间复杂度。 洛谷模板题：P3803 【模板】多项式乘法（FFT），P4245 【模板】任意模数多项式乘法 。 在多项式乘法中，有两个核心问题，加法卷积…

本文主要讨论形式幂级数在解决数学问题以及算法竞赛问题的思维，因此并不会涉及形式幂级数运算的编程实现。 例题引入 [admonition title="问题1" color="indigo"]有 $3$ 个集合 $A=\{2,3\}, B=\{2,4\},C=\{3,5,7\}$ ，现在要求从三个集合中各选择恰好一个元素 $a,b,c$ 使得 $a+…

压位BFS 一个 $n$ 个点，$m$ 条边的有向图，当所有边权均为 $1$ 时，求任意两点之间的最短路。 $n\leq 1000,m\leq \frac{n(n-1)}{2}$ 。 多源最短路是一个经典问题，显然可以通过floyd算法在 $O(n^3)$ 的复杂度下求解。同时，考虑到本题中一个特殊的条件：所有边权均为 $1$ ，本题也可以通过01…