高斯消元

引入

高斯消元听起来非常高大上,其实就是我们初中学的加减消元、代入消元法的程序化实现罢了。
考虑一个方程组 \[ \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} \] 我们要求出它的一组解,或者判定无解或无穷多组解。这就是高斯消元的基础应用。

阅读全文 »

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

阅读全文 »

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

阅读全文 »

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

多项式求逆

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

阅读全文 »

从今天开始,蒟蒻_WA自动机也要学多项式辣!虽然我什么都不会,但是好在我们机房有HA A队队长LCHCTP_998244353巨佬啊!所以天天被巨佬爆踩

lg P3723 [AH/HNOI2017]礼物

题目大意

两个长度为n的环形整数数列,您可以进行两种操作: 1. 对一个数列的所有数加上一个值C 2. 将一个数列旋转一位
定义两个数列的差异值为
\[\sum_{i=1}^{n}(x_i-y_i)^2\] 求差异值的最小值。

阅读全文 »

万古神犇LXL,数据结构碾众生!

即使是蒟蒻也想变强啊..

luogu P3987 我永远喜欢珂朵莉~(这是题目名称!)

题目大意:

有一个长为n的非负数序列A,支持以下两个操作:

  • 1 l r x : 把区间[l,r]中所有x的倍数/x
  • 2 l r : 查询区间[l,r]的和

数据范围:

\(1 \le n , m \le 100000\)

\(0 \le A_i \le 500000\)

\(1 \le x \le 500000\)

阅读全文 »

BST:

概念:

BST(Binary Search Tree):二叉排序树或者是一棵空树,或者是具有下列性质的二叉树

  • 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;

  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;

  • 左、右子树也分别为二叉排序树。

    阅读全文 »