标签 矩阵树定理 下的文章

  1. 首页
  2. 矩阵树定理

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...

  • M_sea
  • 2019 年 06 月 28 日
  • 暂无评论

    • 洛谷4111 [HEOI2015]小Z的房间

    LuoguBZOJ分析矩阵树定理板子题。相邻的两个.间连一条边，然后直接算就行了。注意模数是 $10^9$ 而不是 $10^9+7$ （我就这么 $\mathrm{WA}$ 了 $3$ 次，身败名裂）。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdli...

  • M_sea
  • 2019 年 03 月 31 日
  • 1 条评论

    • 洛谷4455 [CQOI2018]社交网络

    LuoguBZOJ分析有向图上的$\texttt{Matrix_Tree}$定理的板子。这题以$1$为根，所以只能删去第一行和第一列。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #in...

  • M_sea
  • 2019 年 01 月 28 日
  • 暂无评论

    • 洛谷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)$直观上理解就是树边选中的概率乘上非树边不选中的概率加起来。基尔霍夫矩阵的任一个代数余子式是所有生成树的边权积...

  • M_sea
  • 2019 年 01 月 28 日
  • 暂无评论

    • 洛谷4336 [SHOI2016]黑暗前的幻想乡

    LuoguBZOJ分析求出来的$n-1$条边要满足两个限制：构成一颗生成树恰好$n-1$种颜色考虑容斥，用至多$n-1$种颜色的，减去至多$n-2$种的，加上至多$n-3$种的，......至于生成树个数怎么求，用$\texttt{Matrix_Tree}$定理就行了。然后就可以直接枚举子集容斥去算了。代码//It is made by M_sea #include <algorith...

  • M_sea
  • 2019 年 01 月 28 日
  • 暂无评论

    • 洛谷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)$。到此递推式已经明显了，不过有一...

  • M_sea
  • 2017 年 09 月 03 日
  • 暂无评论