挺套路的。 先计算出所有数的积的逆元,再计算除了这个数以外的数的积,然后乘一起,这样就完成了线性求逆元。
lp4980 【模板】Polya定理
Polya定理是一个关于置换群中组合计数的定理。 首先我们来了解Burnside引理。这个引理的证明较为复杂, …
CF102268C
贪心构造即可。 具体来说,如果把a依次标成-n…-1,那么只会有三种数:0(贡献是下标-1),n(贡献是0)以 …
lp5395 【模板】第二类斯特林数·行
第二类斯特林数,指的是一组表示「将n个不同的元素划分为m个非空不相交集的方案数」的组合数。有时写作\(S(n, …
lp5175 数列
$$f_{i}=f_{i-1}+a_{i}^2$$ $$a_{i}^2=(xa_{i-1}+ya_{i-2}) …
lp3455 POI2007 ZAP-Queries
曾经有一道题,叫做YY的GCD,它求的是这样一个值: $$\begin{equation}\begin{spl …
lp4363 九省联考2018 一双木棋chess
快要省选了,需要学习一些乱搞操作。 在这里学习一下Min-Max对抗搜索。 首先了解一下Min-Max对抗搜索 …
lp4245 【模板】任意模数NTT
我们首先考虑一个很暴力的玩法,直接找一个很大很大很大的模数,然后用int128上一个朴素NTT,再将结果对题目 …
lp4777 【模板】扩展中国剩余定理(EXCRT)
$$ \left\{ \begin{matrix}x\equiv a_{1} \pmod{p_1} \\x\e …
lp70296 回忆京都
处理方法类似于NOIP2016,预处理完前缀和即可。 注意这里处理前缀和时需要判负数。
lp3868 TJOI2009 猜数字
这是一道中国剩余定理(又名孙子定理、CRT)的模板题。 它最早来自于「孙子算经」,形式化的说,它是一种用于求解 …
lp2044 NOI2012 随机数生成器
我们不妨将原式递归展开,可以得到形如此的式子: $$f_{n}=a^nf_{0}+\frac{(a^{n}-1 …
lp3812 【模板】线性基
线性基这个名字似乎是来自于它的数学意义。它的用途一般是在集合异或的题目中简化复杂度。 对于关于一个数集的线性基 …
lp2257 YY的GCD
不妨设\(n<m\) 首先将原提问形式化,可以得到原式为: $$\sum_{x=1}^{n}\sum_{ …
CF1091 Good Bye 2018
不知不觉就到了2018的最后一天。这个博客也有两个多月了。我的姿势水平固然有了一定长进,但和巨神的距离却是越拉 …
lp5104 红包发红包
在\(\lbrack 0,1 \rbrack \)中任取一个数,期望是\(\frac{1}{2}\) 同理,在 …
lp5077 Tweetuzki 爱等差数列
令首项为\(x\),长度为\(l\)由等差数列求和式可得:$$s=\frac{l(l-1)}{2}+l*x$$ …
lp2260 清华集训2012 模积和
题目大意:求式子: $$\sum_{i=1}^{n}\sum_{j=1}^{m}(n\ mod\ i)*(m\ …
NOIP2018 货币系统
一道看起来像数论题的完全背包问题。 幸好我前一天没有仔细看数论,使得我想的是写暴力…要不然我可能真 …
线性求逆元
$$我们有一个质数p$$ $$\forall i\in Z,def\ q_{i}=[\frac{p}{i}], …