洛谷5296 [北京省选集训2019]生成树计数
Luogu分析根据二项式定理有所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==========...
标签 矩阵树定理 / Matrix-Tree 定理 下的文章
- 首页
- 矩阵树定理 / Matrix-Tree 定理
CF578F Mirror Box
CodeforcesLuogu分析我们把顶点黑白染色，那么一面镜子就可以看成是连接同色点的一条边。接下来给出一个结论：一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。（比较感性理解的）证明：首先，当黑点连边确定时白点连边一定唯一确定，所以我们只考虑黑边确定的情况。先证必要性：先考虑后面那个限制。如果连成了环，则环内部的边一定没有光线会穿过，所以不能有环。再考虑前面那个限制。我们需要...
CF917D Stranger Trees
CodeforcesLuogu算法一分析设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可。时间复杂...
洛谷6624 [省选联考 2020 A 卷]作业题
LuoguLOJ分析显然莫比乌斯反演一下，可以得到直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel代码// ==============================...
CQOI2018简要题解
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ，然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵树定理。代码交错序列首先推式子： $x^ay^b=(n-y)^ay^b=\sum\limits_{i...
洛谷4111 [HEOI2015]小Z的房间
LuoguBZOJ分析矩阵树定理板子题。相邻的两个.间连一条边，然后直接算就行了。注意模数是 $10^9$ 而不是 $10^9+7$ （我就这么 $\mathrm{WA}$ 了 $3$ 次，身败名裂）。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdli...
洛谷4455 [CQOI2018]社交网络
LuoguBZOJ分析有向图上的$\texttt{Matrix_Tree}$定理的板子。这题以$1$为根，所以只能删去第一行和第一列。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #in...
洛谷3317 [SDOI2014]重建
LuoguBZOJ分析puts("nan")可在BZOJ上AC很神仙的一道题目。考虑暴力枚举每颗树，答案就是$\large\sum\limits_{T}\prod\limits_{e\in T}p_e\prod\limits_{e\not\in T}(1-p_e)$直观上理解就是树边选中的概率乘上非树边不选中的概率加起来。基尔霍夫矩阵的任一个代数余子式是所有生成树的边权积...
洛谷4336 [SHOI2016]黑暗前的幻想乡
LuoguBZOJ分析求出来的$n-1$条边要满足两个限制：构成一颗生成树恰好$n-1$种颜色考虑容斥，用至多$n-1$种颜色的，减去至多$n-2$种的，加上至多$n-3$种的，......至于生成树个数怎么求，用$\texttt{Matrix_Tree}$定理就行了。然后就可以直接枚举子集容斥去算了。代码//It is made by M_sea #include <algorith...
洛谷2144 [FJOI2007]轮状病毒
Luogu分析打表找规律：n=1 ans=1 n=2 ans=5 n=3 ans=16 n=4 算不出那就分析前三项，发现：$1=1\times 1,5=3\times 3-4,16=4\times 4,...$看样子是平方数，不过好像有变化——偶数项要减4。然后要平方的数是可以递推的，$f[1]=1,f[2]=3,f[i]=f[i-2]+f[i-1](2)$。到此递推式已经明显了，不过有一...