洛谷4457 [BJOI2018]治疗之雨
Luogu LOJ 分析 设 $f_i$ 为从 $i$ 点生命值变为 $0$ 点生命值的期望步数,$p_i$ 为生命值 $\geq i$ 时一回合扣掉 $i$ 点生命值的概率,那么有 直接高斯消元是 $\mathcal{O}(n^3)$ 的,只能获得 70 分。 但是这个矩阵很有性质。我们从上往下消,消到每一行时只会有 $3$ 个位置(包括常数项)有值,也就是只要消三列。最后一行时只会剩下...
Luogu LOJ 分析 设 $f_i$ 为从 $i$ 点生命值变为 $0$ 点生命值的期望步数,$p_i$ 为生命值 $\geq i$ 时一回合扣掉 $i$ 点生命值的概率,那么有 直接高斯消元是 $\mathcal{O}(n^3)$ 的,只能获得 70 分。 但是这个矩阵很有性质。我们从上往下消,消到每一行时只会有 $3$ 个位置(包括常数项)有值,也就是只要消三列。最后一行时只会剩下...
Codeforces Luogu 分析 我们把顶点黑白染色,那么一面镜子就可以看成是连接同色点的一条边。 接下来给出一个结论:一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。 (比较感性理解的)证明: 首先,当黑点连边确定时白点连边一定唯一确定,所以我们只考虑黑边确定的情况。 先证必要性: 先考虑后面那个限制。如果连成了环,则环内部的边一定没有光线会穿过,所以不能有环。 再考虑前...
UOJ 分析 结论:如果有解,那么步数必然 $\leq m+1$。 证明:首先操作 $2$ 可以合并,所以只需要进行至多一次;其次,我们随便造一个生成森林,那么每条非树边就相当于一个简单环,从而操作 $1$ 的次数不会超过非树边数。所以总操作数至多为 $m-n+2\leq m+1$。 于是我们只需要判是否有解即可。 那么我们相当于要选若干个简单环异或 $1$,使得所有 $1$ 边变成 $0$...
Luogu 分析 先莫比乌斯反演一下 后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$,显然是积性函数,所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$,所以只要算两项即可。 至于 $f_i$,可以求拉格朗日插值公式中每项系数求出,也可以直接高斯消元。 代码 // =...
Codeforces Luogu 算法一 分析 设树边的权值为 $x$,非树边的权值为 $1$,然后矩阵树定理。设得到的多项式为 $F(x)$,那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。 然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式,所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$,然后解方程组解出系数即可...
Codeforces Luogu 分析 首先确定基本的计算方式 则我们需要平方、减法、乘法(除以 $2$ 就是乘逆元)这三种运算。 既然要造计算机,那么一定要先求出一个 $0$ 来。因为 $1+1\times(p-1)\equiv 0\pmod p$,所以可以快速乘一下。 for (int i=p-1;i;>=1) { // 0 -> o[16] if (i&1...
LOJ 分析 不难想到一个 $\mathcal{O}(n^3m^3)$ 的高斯消元做法,即将每个位置出发的期望步数作为变量,然后暴力高斯消元。 考虑将第一行、第二行、第一列的位置作为主元,并将其它元用主元线性表示。可以发现只有 $(x+2,y+1)$ 无法直接求出它的线性表示,但因为向八个方向走的概率之和为 $1$,所以可以用其它七个方向来求 $(x+2,y+1)$ 的线性表示。 当 $(x...
Luogu LOJ 分析 首先你需要看懂这篇题解。 设 $f_{i,j}$ 表示长度为 $i$ 时出现 $j$ 结束的概率,$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_{i,j}$ 的概率生成函数为 $F_i(x)$ ,$g_i$ 的概率生成函数为 $G(x)$ 。 设 $a_{i,j,k}$ 表示 $s_{i}[1..k]$ 是否等于 $s_j[m-k+1..m]$ 。 ...
CodeForces Luogu 分析 设 $f_{i, j}$ 表示 $(i,j)$ 到最后一排的移动步数的期望。显然有转移 对于每行,列与列之间的转移有后效性,高斯消元即可。但是这是一个 band-matrix,所以可以 $\mathcal{O}(m)$ 消元。 注意特判$m=1$的情况。 代码 #include <bits/stdc++.h> #define re reg...