数学笔记

一个关于逆元的小技巧

ans = \frac{a}{b}\bmod m = a\bmod \left( {mb} \right)/b

那么下面是证明

\begin{array}{l}\frac{a}{b} = km + x{\rm{ }}\left( {x < m} \right)\\a = kbm + bx\\a\bmod bm = \left( {kbm\bmod bm} \right) + \left( {bx\bmod bm} \right)\\a\bmod bm = bx\\\frac{{a\bmod bm}}{b} = x\\\frac{a}{b}\bmod m = \left( {km\bmod m} \right) + \left( {x\bmod m} \right)\\\frac{a}{b}\bmod m = x\end{array}

为什么我觉得没多大用处……


唯一分解定理

将一个非素数N 唯一分解成有限个素数的乘积

N = \prod\limits_{i = 1}^n {p_i^{{a_{_i}}}}

快速分解:每次只枚举不大于\sqrt {N'}的所有质数(N'\frac{N}{{\prod\limits_{i = 1}^\delta {p_i^{{a_i}}} }},其中\delta是目前枚举到的质数个数 )

可以证明N'只有最多一个超过\sqrt {N'}的质因子。

具体程序如下

 

今天是1月7日,昨天湖南师附集训 宾馆网速40kb/s 本来想传上费马小定理和二次探测定理的证明 结果编辑页面开了2h无果……

Day2 20:35上传一下

上传失败了,Day4 00:02再上传一下

\begin{array}{l}a^{p-1}\equiv 1\,\,\left( \text{mod}\,p \right) \,\,\left( p\text{为素数,}p\nmid a\text{不成立且}a>0 \right)\\\text{记}A=\left\{ a,2a,3a,\cdots ,\left( p-1 \right) a \right\} ,B=\left\{ 1,2,3\cdots ,p-1 \right\}\\A=B\,\,\left( \text{mod}\,p \right) \\ \text{对于}\forall a\in A,\text{存在唯一}b\in B\text{且}a\equiv b\,\,\left( \text{mod}\,p \right) \\\text{如果}a_1,a_2\in A,a_1\equiv a_2\,\,\left( \text{mod}\,p \right) \,\,,\,\,\text{则上式不成立}\\\text{记}a_1=i\times a,a_2=j\times a\\\text{则有}i\times a\,\,\equiv \,\,j\times a\,\,\left( \text{mod}\,p \right) \,\,\left( 0<i,j<p \right) \\\therefore \left( i-j \right) \times a\equiv 0\,\,\left( \text{mod}\,p \right) \\\therefore \left( i-j \right) \equiv 0\,\,\left( \text{mod}\,p \right) \\\therefore i=j\\\because A=B\,\,\left( \text{mod}\,p \right) \\a\times 2a\times 3a\times \cdots \times \left( p-1 \right) a\equiv 1\times 2\times \cdots \times \left( p-1 \right) \,\,\left( \text{mod}\,p \right) \\a^{\left( p-1 \right)}\times \left( p-1 \right) !\equiv \left( p-1 \right) !\,\,\left( \text{mod}\,p \right) \\a^{p-1}\equiv 1\,\,\left( \text{mod}\,p \right) \end{array}

下面是二次探测的证明……? 主要是用在Miller-Rabin上吧……

\begin{array}{l}x^2\equiv 1\,\,\left( \text{mod}\,p \right) \,\,\left( p\text{为素数,}x\in \mathbb{Z} \right)\\x^2-1\equiv 0\,\,\left( \text{mod}\,p \right)\\\left( x+1 \right) \left( x-1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\\left( x-1 \right) \equiv 0\text{或}\left( x+1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\p=2\text{显然成立}\\p>2\text{时,}\\\left( x+1 \right) \equiv 0\,\,\text{或}\left( x-1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\x\equiv \pm 1\,\,\left( \text{mod}\,p \right) \end{array}

接下来是Miller-Rabin,写的时候用费马小定理居然没有判gcd然后好长时间才查出来     真可怕

就放个板子 具体原理上面证完了。

不是很难,也就几行.


2018-3-22 update

遇到一个有趣的式子……

F\left( a+b \right) =F\left( a+1 \right) \times F\left( b \right) +F\left( a \right) \times F\left( b-1 \right)

还有就是

\begin{array}{l} \text{gcd}\left( F\left( a \right) ,F\left( b \right) \right) \\ =\,\,\text{gcd}\left( F\left( a-b+b \right) ,F\left( b \right) \right) \\ =\,\,\text{gcd}\left( F\left( a-b \right) \times F\left( b-1 \right) ,F\left( b \right) \right) \end{array}

然后可以化为

\text{gcd}\left( F\left( a-b \right) ,F\left( b \right) \right) \ =\ F\left( \text{gcd}\left( a,b \right) \right)


\begin{array}{l} \phi \left( x \right) =\left( a_1-1 \right) a_{1}^{p_1-1}\cdot \left( a_2-1 \right) a_{2}^{p_2-1}\cdots \left( a_n-1 \right) a_{n}^{p_n-1} \\ \text{原理:\ 当}x=p^n\text{时\ ,\ }\phi \left( x \right) =x-x/p=p^n-p^{n-1}=\left( p-1 \right) p^{n-1}\ \text{而且}\phi \left( x \right) \text{是积性函数} \end{array}


线性筛的证明

\gcd(n,m)=1 \Rightarrow \gcd(n+m,m)=1

n,m 不互质时,

b=\gcd(n,m) \;\; (b \ne 1) 则有

\begin{cases} n+m=k_2b\\ m=k_1b \end{cases} \;\;\;(k_1,k_2 \in \mathbb{Z})

\Rightarrow k_1b+n=k_2b

\Rightarrow n=(k_2-k_1)b

\Rightarrow \gcd(n,m)=b

这与\gcd(n,m)=1矛盾。

所以我们有了\varphi(p \times i)=p \times \varphi(i)

NOIp2017 DP专项练习

1 Power收集

设dp[i][j]为走到第i,j个位置的最多能量,考虑每一个状态都从上一层dp[i-1][j-t ~ j+t]转移而且取max,于是简化状态每一次用堆维护上一层的最大数(std应该是单调队列然而时限比较善良于是堆也能水过)然后检查当前位置和堆顶元素位置,不满足就pop。然后取堆顶转移

关路灯

区间……没做出来看题解了……

设dp[i][j][0/1]表示把区间[i,j]内的所有灯全部关闭并停在i(第三维是0)或j(第三维是1)处,已经消耗的电能

枚举区间大小转移。注意dp[i][j][0]可从dp[i+1][j][1]转移来,dp[i][j][1]能从dp[i][j-1][0]转移来

小a和uim之大逃离

脑残没想到看题解系列

知道状态一定有第四维,也知道一定有前两维……然而就是脑残想不到可以化成O(nmk),还傻傻的以为是O(n2m2)……

只允许这一次脑残了……

我们设dp[i][j][p][0/1]表示从1,1用随便什么路径走到i,j点,并且disA-disB=p(%k意义下,所有没有负数,尽管应该有)时的合法方案数

那就是dp[i-1][j][ ( (p-mapx[i][j])%k +k)%k ][1]+dp[i][j-1][ ( (p-mapx[i][j])%k +k)%k ][1]

(逆序还原上一个状态的p,因为现在是A走达到了p,那么没经过i,j之前一定是p-mapx[i][j])

另一个状态同理。

注意随时%1000000007

最后O(NM)统计答案。

 矩阵取数游戏

本质上就是关路灯

套一个高精度就行了

我设的dp[i][j]表示这一行余下区间[i,j]的时候的最大得分(好像是得分?还是什么……?)

每一次从dp[i-1][j]+pow(2,m-(j-i)-1)*mapx[i-1][j]和dp[i][j+1]+pow(2,m-(j-i)-1)*mapx[i][j+1]取max转移

注意最外面一层是从大到小枚举长度

最长公共子序列(LCS问题)

傻比题既视感

大概是这样:因为是一个排列,考虑把B串做一个映射,标记下每一个元素(1~n)在B串中的下标

然后让A串通过映射构造一个新的串,因为是公共序列问题,所以只要在新串中按照顺序出现的就是A与B重合的。

比如说,6在B中是[19],那就把6映射到19(codex[6]=19)            3在B中是[22] 也映射过去

那么假设6在A中是[2]那么新串C[2]=codex[A[2]]       所以C[2]=19

3在A中是[5],那么C[5]=codex[A[5]]      C[5]=22

那么显然在A串中,3在6后面,而且B串中3也在6后面,这样如果把A中3 6替换为3 6在B中的下标,那一定是递增的。

最后nlogn做法的LIS就可以过

有线电视网

关键词:树上背包,傻比题。

设状态f[i][j]表示结点i连接j个用户的最大赚取(支付的钱-花费)然后枚举子树暴力转移一波就行

注意计数,枚举到一颗新的子树,现在结点的[最大连接用户(叶子)数目+=子树的最大连接数目]
然后j从0循环到最大连接数目取max

dp[nownode][i] = max ( dp[nownode][i] , dp[nownode][i-j] + dp[v][j] – edge[prex].w );

加分二叉树

破区间dp,什么玩意

对于每个子树,枚举它的根节点(>=L <=R)然后暴力dp更新

1.设计状态dp[i][j]表示在中序遍历中i~j这段区间代表的子树的最大加分

2.注意空树的处理 if (i>j) return 1;

[HAOI2012]音量调节

傻比题,纯粹是为了有时间tuifei

然而交了三遍才过,变量重名竟然都检查不到。

就是些**样例 -Yansir

[HAOI2009]逆序对数列

看题解才过去……

真是道好题

设dp[i][j] 表示前i个数(1-i)出现j个逆序对有多少方案,可知dp[1][0]=1;

考虑把第二个数分别放在第0个位置(第一个数之前),第1个位置,第2个位置……假设现在的i=2则有dp[2][2]=dp[1][2]+dp[1][1]d+dp[1][0]

也就是分别放在哪个位置上(0,1,2  ps注意前后括号里的对应),还欠缺的逆序对需要用之前的i-1个数补。(dp[1][0] dp[1][1],dp[1][2])

归纳总结一下:

1.dp[i][j]=∑dp[i][k]         (  max(j-i+1,0) ≤ k ≤ j  )

2.用前缀和优化转移,O(n2)

直接令dp[i][j]代表之前的∑dp[i][k]    (0 ≤ k ≤ j )

然后转移可以O(n2)  :      dp[i][j]=dp[i-1][j]-dp[i-1][j-i]   +dp[i][j-1]

10 跳舞

(背景)很像紫书上的那个Tango

设计状态dp[i][j]表示踩到了第i个箭头的时候踩了j次,此时的最大得分

可以发现决策就两个:踩,得分;或者不踩,扣分。

所以从dp[i-1][j-1]+socre[i] , dp[i][j]-score[i]转移

特判j%t=0的情况,此时踩多加分,不踩不多扣分

11 

JLOI2009 二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为:

深度:4 宽度:4(同一层最多结点个数)

结点间距离: ⑧→⑥为8 (3×2+2=8)

⑥→⑦为3 (1×2+1=3)

注:结点间距离的定义:由结点向根方向(上行方向)时的边数×2,

与由根向叶结点方向(下行方向)时的边数之和。

 

输入输出格式

输入格式:

输入文件第一行为一个整数n(1≤n≤100),表示二叉树结点个数。接下来的n-1行,表示从结点x到结点y(约定根结点为1),最后一行两个整数u、v,表示求从结点u到结点v的距离。

输出格式:

三个数,每个数占一行,依次表示给定二叉树的深度、宽度及结点u到结点v间距离。

无耻的借用洛谷的图片

这题就是个智障

首先dfs一下然后bfs一下然后lca一波就行了

一开始忘记讨论深度了然后使劲在那WA。。

//我知道不用写LCA和BFS但我就是想写你打我啊!!!!

BZOJ1878 | SDOI2009 HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入输出格式

输入格式:

第一行:一个整数N,表示项链的长度。

第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。

第三行:一个整数M,表示HH 询问的个数。

接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

输出格式:

M 行,每行一个整数,依次表示询问对应的答案

什么描述啊……

我们可以 简单地 发现对于每次区间询问,如果一种编号出现了多次,那么只有最后一次才是有意义的。

那么离线询问并按照R为第一关键字,L为第二关键字排序。

然后从当前位置指针(初始为1,当然)扫到R统计有没有新出现的和重复出现的

如果是新出现的那么标记一下再扔到树状数组里(哦,忘记了,树状数组是按位置建的,也就是下标和项链是对应的)

如果是重复出现的,那么,有一个数组保存之前出现的位置,get到这个位置然后往树状数组里这个位置扔一个-1就行了。

之后更新前一次出现位置数组并扔进树状数组里。

最后求区间和……

真是一道好题。

#洛谷P2448 无尽的生命

题目描述

逝者如斯夫,不舍昼夜!

叶良辰认为,他的寿命是无限长的,而且每天都会进步。

叶良辰的生命的第一天,他有1点能力值。第二天,有2点。第n天,就有n点。也就是S[i]=i

但是调皮的小A使用时光机,告诉他第x天和第y天,就可以任意交换某两天的能力值。即S[x]<–>S[y]

小A玩啊玩,终于玩腻了。

叶良辰:小A你给我等着,我有100种办法让你生不如死。除非能在1秒钟之内告知有多少对“异常对”。也就是说,最后的能力值序列,有多少对的两天x,y,其中x<y,但是能力值S[x]>S[y]?

小A:我好怕怕啊。

于是找到了你。

对于30%的数据,x_i,y_i <= 2000

对于70%的数据, x_i,y_i <= 100000

对于100%的数据, x_i.y_i <= 2^31-1 k<=100000

逆序对裸题

由于xy这么大我们来离散化

把只要是交换过的(不管几次)都标记下来,排下序(点权为1)

没交换过的一些区间缩成一个点(点权为区间长度)

然后进行离散化操作,离散成新的段,相邻两点间下标严格递增1(还有一个就是开头没被交换的区间对答案没有影响直接扔掉)

我们离线了交换操作,这个时候就二分查找,把原来应该换哪两个点映射成现在应该换哪两个点

全换完之后就是个裸的逆序对问题,按点权建树状数组,然后统计区间和就行了。

·

//注释是做题的时候瞎写的凑合着看看吧,要说的都说了。

JZOJ 3808 | Luogu2103 道路值守

题目描述

Z-Kingdom有着四通八达的现代化交通。时值独立庆典之际,随着来自周边国家旅客的日益增多,犯罪行为也悄无声息开始滋长起来。

特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查,他们得到了一张地图,记载了Z-Kingdom内每一条道路的长度。

显然,为了减少犯罪行为被发现的可能性,犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线,他们希望得知任意两个地点之间,有多少条犯罪分子可能会选择的道路。

输入输出格式

输入格式:

第一行,包含两个整数N,M,表示Z-Kingdom内的地点数和道路数。

接下来N行,每行包含三个整数x,y,z,表示道路连接的两个不同地点的标号,以及道路的长度。道路是双向的。

两个不同地点之间不会有超过一条道路。

输出格式:

输出一行,包含 N (N-1)/2 个整数

其中表示 x 号地点到 y 号地点之间有多少条犯罪分子可能会选择的道路。

先Floyd求出最短路

对于每一个点i:

{

枚举所有点j ,确保i,j联通,且i,j不是一点。

然后检查有多少点k与j有连边,且在i-j的最短路disi,j上。(也就是检查从i到j有多少条满足disi,j上且与j相连

       esumj=∑k1     k∈(g[k][j]!=0 && dis[i][k]+g[k][j]==dis[i][j])

最后考虑DP

枚举一个终点j,再枚举一个k,如果k在i-j的最短路上,那么esum[k]个方案计入C[i][j]。(有esumk条边可以到k点,在最短路上可以选k点,所以要计入方案数目)

}