_WA自动机的blog

HA省蒟蒻OIer


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • links

[SCOI2014][Luogu P3288]方伯伯运椰子

发表于 2019-04-22 | 更新于 2019-04-23

题目描述

四川的方伯伯为了致富,决定引进海南的椰子树。方伯伯的椰子园十分现代化,椰子园中有一套独特的交通系统。

阅读全文 »

[ZJOI2016]书架

发表于 2019-03-18

[六省联考2017]相逢是问候

发表于 2019-03-18 | 分类于 题解

不要在意网址…打错了qwq

题目大意

Informatik verbindet dich und mich.
信息将你我连结。

维护一个数列A,支持两种操作:

  • 0 l r :表示将A[l..r]这个区间的每个数$A_i$变成$c^{A_i}$(c是输入给定的常量)
  • 1 l r : 表示求$A[l..r]$的和,结果对p(输入给定的常量)取模。
阅读全文 »

BZOJ1016

发表于 2019-03-08 | 更新于 2019-03-19 | 分类于 题解 , BZOJ百题计划

大意:

给你一个联通无向图,求其最小生成树的个数。答案对31011取模。(鬼知道为啥是这个数)

阅读全文 »

[BZOJ3534][SDOI2014]重建

发表于 2019-03-07 | 更新于 2019-03-08 | 分类于 题解

题目大意:

你有一个无向完全图。在一场洪水(?)以后,每条边都可能会损毁。给定每条边没有被损毁的概率,求最后剩下的边正好组成原来的图的一棵生成树的概率。

阅读全文 »

高斯消元-行列式-矩阵树定理学习笔记

发表于 2019-03-06 | 更新于 2019-03-10 | 分类于 学习笔记

高斯消元

引入

高斯消元听起来非常高大上,其实就是我们初中学的加减消元、代入消元法的程序化实现罢了。
考虑一个方程组
$$
\begin{cases}
A_{1,1} x_1+A_{1,2} x_2+A_{1,3} x_3+…+A_{1,n} x_n=C_1 \\\\
A_{2,1} x_1+A_{2,2} x_2+A_{2,3} x_3+…+A_{2,n} x_n=C_2 \\\\
…\\\\
A_{k,1} x_1+A_{k,2} x_2+A_{k,3} x_3+…+A_{k,n} x_n=C_n \\\\
\end{cases}
$$
我们要求出它的一组解,或者判定无解或无穷多组解。这就是高斯消元的基础应用。

阅读全文 »

BZOJ1003

发表于 2019-03-03

[BZOJ1002][FJOI2007]轮状病毒

发表于 2019-03-03 | 更新于 2019-03-09 | 分类于 题解 , BZOJ百题计划

询问生成树个数,一眼矩阵树定理…但是高消会爆精度,long double都存不下。不取模的计数题都是耍流氓! 所以,用Python打表就行了正解是递推打表找规律。其实可以用矩阵树直接推行列式的,但是我不会,回头再想一下吧.

阅读全文 »

[BZOJ1001][BeiJing2006]狼抓兔子

发表于 2019-03-03 | 更新于 2019-03-09 | 分类于 题解 , BZOJ百题计划

网格图求最小割?据说这题正解是平面图最小割转对偶图最短路。但是不知为啥数据太水最大流就可以直接过了..
很久以前的代码了,将就着看吧(虽然这种水题也没人会去看题解…
也许我以后会更一篇正解的题解吧(flag

阅读全文 »

多项式算法小结

发表于 2019-02-18 | 更新于 2019-02-24 | 分类于 学习笔记

万古神犇卢宸昊,数论算法碾众生!

多项式求逆

给定一个多项式 $F(x)$ ,请求出一个多项式$G(x)$, 满足 $F(x) * G(x) \equiv 1 ( \mathrm{mod\:} x^n )$。系数对$998244353$取模。

阅读全文 »
123
_WA自动机

_WA自动机

消えない过去、消えていく未来。

29 日志
8 分类
40 标签
© 2019 _WA自动机
由 Hexo 强力驱动 v3.8.0
|
主题 – NexT.Pisces v6.7.0
|