数学
|
2k 字
|
7 分钟

数论

伯特兰-切比雪夫定理

这个东西说实话还挺难的……（啊我说的是这个东西要是出题的话）

为什么这东西要用二项式系数进行证明……感觉非常奇怪的证明方式唉

P5535 【XR-3】小道消息

这个题有三种情况

首先我们考虑，和一个质数不互质的数，他一定是这个质数的倍数

  1. 如果这个数字是质数：如果说，在这些号码里，这个质数乘二之后大于这些号码中的任何一个数，那么我们直接告诉这个人就好了，一天解决任务
  2. 还是讨论质数的情况：如果这个指数乘二之后小于等于号码的最大数，那么就需要两天，因为由于上面的那个定理我们可以知道，这个数字一定会传给所有数字里最大的那个质数的耳朵里，那么这个质数一定是符合第一种情况的，所以两天
  3. 如果这个数字是合数（和第二种情况其实一样）（选出最大的质数就好了）两天

是不是很妙

P2568 GCD

GCD的题目（话说GCD的性质似乎很多很多唉

既然要求的是GCD为素数，那么说明这两个数同时除以这个GCD之后的数字是互质的

然后就可以转化成一个经典问题：仪仗队（洛谷有）

然后随便求就好了

欧拉反演

还有个很像的题：P2398 GCD SUM

P4139 上帝与集合的正确用法

神仙题目……

题目的意思基本上就是说让你求222222222。。。2^{2^{2^{2^{2^{2^{2^{2^{2。。。}}}}}}}}%mod（给定mod之后的值）

通过扩展欧拉定理我们可以得知，

当b≥ϕ(p)b\ge\phi(p)时 ：

ab≡abmod  ϕ(p)+ϕ(p)(mod  p)a^b \equiv a^{b\mod\phi(p)+\phi(p)}(\mod p)

b≤ϕ(p)b\le \phi(p)时

ab≡abmod  ϕ(p)(mod  p)a^b\equiv a^{b\mod\phi(p)}(\mod p)

然后我们就可以递归进行求解

因为我们的ϕ\phi在慢慢慢慢的消减，它就会变成1啊0啊之类的东西，之后mod出来的东西就是不变的了

那么我们递归求一发，就可以知道最后的答案了（谁出的毒瘤题目啊）

P2480 [SDOI2010]古代猪文

CRT

简化版题意（lyd）

q∑d∣n(nd)mod  999911659q^{\sum_{d|n}{n\choose d}}\mod 999911659

由于欧拉定理的推论我们可以直接把上面的二项式系数把上面的指数进行一下化简

就会变成

q∑d∣n(nd)mod  999911658mod  999911659q^{\sum_{d|n}{n\choose d}\mod 999911658}\mod 999911659

所以我们的目的就是求指数

在进行求解的时候我们可以用lucas定理再一次化简

但是……

似乎不是很对的样子

lucas定理是用在质数上的

那么，我们就把999911658分解质因数，然后进行lucas定理，然后再用CRT合并，你会发现，这样子是时间比较优秀的

就算是mod999911659的时间都会比他劣……

线性代数

矩阵乘法：

对于两个矩阵来说，加法就是把两个矩阵的对应位进行相加

乘法就不一样了，我们设两个矩阵为A，B；A为n*m的矩阵，B为m * k的矩阵

我们设这个结果矩阵为C，它会是一个n*k的矩阵

这个C矩阵的第i行第j列为A的第i行第l列乘上B的第l行第j列的总和

例题：

P1962 斐波那契数列

这个转移矩阵就直接写成0,11,1{0,1}{1,1}（不会搞矩阵的写法

然后矩阵快速幂

P1349 广义斐波那契数列

很简单对吧，改一改就好了

P3758 [TJOI2017]可乐

P5343 【XR-1】分块

这两个挺水的矩乘优化dp，过了吧

P5337 [TJOI2019]甲苯先生的字符串

同样是矩乘优化dp

P5303 [GXOI\GZOI2019]逼死强迫症

这题……

如果我们已经确定了两个单个的方格放在那两列了的话，我们就可以发现，这两个单个的方格之间的方法是固定的，所以我们枚举第一个块放在哪里，其他的方案数直接用矩乘算出来，然后求和……

高斯消元法

高斯消元是对一个n元线性方程组进行求解的方法

n∗(n+1)n*(n+1)的增广矩阵前面n∗nn * n的矩阵的数字都是未知数的系数

最后的第n+1个数字就是方程组右边的数字

首先我们要知道，如果说我们求解一些特殊的方程组的话，是有一点点技巧的（比如二元一次方程组等等）

但是，对于求解方程组来说，是有通法的，就是这个，高斯约旦消元法

如果说一个增广矩阵是前面的n∗nn*n的矩阵是对角线矩阵，那么……就可以非常简单的求出来解（直接得数除以系数就好了

高斯约旦就是进行了这样的一个操作

我们对于每一列来说，选出最大的系数，然后用这个最大的系数对其他的方程组进行消元法

最后得到的对角线矩阵

P3389 【模板】高斯消元法

P4783 【模板】矩阵求逆

高斯消元的东西们：

P4035 [JSOI2008]球形空间产生器

经典题目了好吧

球心对于球面上任何一个点来说距离相等

用欧几里得距离列出来方程组高斯消元

P2447 [SDOI2010] 外星千足虫

线性基一下就好了其实

高斯消元求解异或方程组

把高斯消元的过程改成异或就好了

P5516 [MtOI2019]小铃的烦恼

题目里面有个非常迷惑的条件：选定这本书之后的概率……根据下面的条件综合等于n^2来说，概率一定是1

我们设最后所有书的魔法值都变成了某一个固定的值

枚举那个固定的值

假设他出现了x次

那么选中另外的使得总数加一减一的概率就都会是i(n−i)n(n−1)\dfrac{i(n-i)}{n(n-1)}

那么就说明f[i]=i(n−i)n(n−1)f[i−1]+i(n−i)n(n−1)f[i+1]f[i]=\dfrac{i(n-i)}{n(n-1)}f[i-1]+\dfrac{i(n-i)}{n(n-1)}f[i+1]

然后我们就可以进行：带装矩阵高斯消元

就是说整个矩阵来说把对角线行数正负x的格子全部有数

然后高斯消元

这样的矩阵我们直接把每一行的下一行用自己消一遍，然后回代就好了复杂度优秀为n

然后就好了

矩阵树定理

（证明不会，太难了

  • 拉普拉斯矩阵：我们把A矩阵的对角线设为这个点的度数，B矩阵为邻接矩阵，C为拉普拉斯矩阵，C=A-B
  • 行列式

对于一张图来说，他的生成树数量就是拉普拉斯矩阵的行列式

行列式：对于一个矩阵来说，他的行列式等于∑s∏ai,si\sum_{s}\prod a_{i,s_i}

三个性质：

  1. 交换矩阵的任意一行行列式变成相反数
  2. 将一个矩阵的一行加上另一行的倍数，行列式不变
  3. 三角矩阵的行列式为对角线的乘积

然后我们求行列式的时候就可以用高斯消元，消成三角矩阵之后对角线乘积。但是高斯消元的时候要用更相减损，不然会损失精度

上一篇
下一篇