牛客多校联盟 第四场总结  A B Interval Revisited Chiaki Sequence Reloaded DAnother Distinct Values       牛客多校联盟 第四场总结 本场是找规律场，我个菜鸡找不到，我心好累 A 遇到0时直接去掉  假设遇到1时，已经走了 t，消除这个1的效果还需要 t+2  假设遇到2时，已经走了t，消除这个2的效果还需要  3∗(2t+1−1)−t    3   ∗   (    2    t   +   1     −   1   )   −   t  （怎么找到的，打表找规律）  假设共有n个2且最后一个是2，那么解的形式就...

欧拉降幂公式与证明  欧拉降幂公式 证明      欧拉降幂公式与证明 转载自D-Tesla 欧拉降幂公式     AK≡AK%ϕ(m)+ϕ(m)( mod m)K>ϕ(m)     A   K    ≡    A    K   %   ϕ   (   m   )   +   ϕ   (   m   )     (  <mtext>   </mtext>  m   o   d  <mtext>   </mtext>  m   )   K   >   ϕ   (   m   )    证明 今天在牛客多校的群里看一个数学大佬写的证明，不...

FFT  FFT FFT的全称是 Fast Fourier Transform 即快速傅里叶变换 傅里叶变换是复变函数的重要内容，傅里叶变换分为离散和连续傅里叶变换 傅里叶变换实现从时域到频域的转换，是信号与系统重要的分析工具 连续傅里叶变换 ![此处输入图片的描述][1] 离散傅里叶变换(DFT discrete Fourier transform) 将离散的序列值进行频域到时域的转换，就叫做离散傅里叶变换 如果有      x   (   n   )   =    {     <mstyle displaystyle="true" scriptlevel=&quo...

2018牛客多校第三场个人总结  A PACM Team 2 B Expected Number of Nodes 3 C Shuffle Cards D Encrypted String Matching E Sort String F Sum Of Digit G Coloring Tree H Diff-prime Pairs I Expected Size of Random Convex Hull J Distance to Work     2018牛客多校第三场个人总结 A PACM Team 背包dp经典题，也不算是太复杂的变形，直接dp就行了，注意卡空间，用short  #i...

杭电多校第一场 1007 Chiaki Sequence Revisited      1007 Chiaki Sequence Revisited  题意 求前缀和        杭电多校第一场 1007 Chiaki Sequence Revisited 1007 Chiaki Sequence Revisited 题意   给定  an     a   n    的递推式，求  an     a   n   的前缀和 打表  1 1  2 2  3  4 4 4  5  6 6  7  8 8 8 8  9  10 10  11 12 12 12  13  14 14  15  16 1...

2018 牛客多校第二场 个人总结+部分题解    1 dp 入门题 B discount C message D money E tree F trade G transform H travel I car J farm K carpet        2018 牛客多校第二场 个人总结+部分题解 1 dp 入门题 dp[j][i] 表示 到i这个点是跑过来还是走过来的，走过来就是1，跑过来就是0  转移方程  上一次是跑过来或者走过来，这一次都可以走      dp[0][i+1]+=(dp[0][i]+dp[1][i])    d   p   [   0   ]   [   i   +...

多校联盟主要有 杭州电子科技大学好牛客网举办的比赛，各自十场 牛客多校 牛客多校第一场  牛客多校第二场  牛客多校第三场  牛客多校第十场 杭电多校 杭电多校第一场  杭电多校第二场  杭电多校第三场  杭电多校第四场  杭电多校第七场

const int maxn = 5e5+1000; LL N,T; LL x[maxn],a[maxn],sum[maxn],sumd[maxn]; //  sum[i] 表示到第i个点，共有多少product //  sumd[i] 表示到第i个点，把这些点上所有的货物运送到0点需要的cost //  把[l,r] 区间内的货物移到 l 则  ca1(l,r) = sumd[r]-sumd[l-1]-(sum[r]-sum[l-1])*d[l] //  把[l,r] 区间内的货物移到 r 则  ca2(l,r) = (sum[r]-sum[l-1])*(x[r]-x[l])-ca1(l,r...

G transform 货仓选址问题 题意 在数轴上有n个箱子，第i个箱子里有      a   i     a_i   ai​ 的货物，距离原点的距离是      x   i     x_i   xi​, 移动一个货物从箱子i到j的花费是     a   b   s   (    x   i    −    x   i    )    abs(x_i-x_i)   abs(xi​−xi​)，要求在总花费 不超过 T的情况下把尽量多的货物移动到一个箱子里，求货物的最大数量ans 分析 前提 1. 首先来分析我们把货物移动到一个箱子，那么这些货物所在的区间一定是连续的区间，不可能是分立的，区间左...

文章目录    1004 Distinct Values  题意 做法 参考代码      1004 Distinct Values 题意 构造一个字典序最小的数组，其中m个区间中的数不能相同 做法 考虑每一个位置当前能放的数中的最小数，所以我们需要记录从 当前要放的位置 到 往前多少是这个不能重复的区间的边界，不能和这个区间里面的重复 所以用pre数组记录最远，然后之前pre[i] 之前的数就能继续用了加入到set或者优先队列里，每次取最小 这个需要画图，我画工不好，就不献丑了，可以看看代码，有助于理解 参考代码 dls（杜老师讲题解的时候是用set实现的，优先队列大概快200ms的样子） ...

文章目录     1 Maximum Multiple 2 Balanced Sequence 3 Triangle Partition 4 Distinct Values 5 Maximum Weighted Matching 6 Period Sequence 7 Chiaki Sequence Revisited 8 RMQ Similar Sequence 9 1009. Lyndon Substring 10 Turn Off The Light 11 Time zone      1 Maximum Multiple 这一题上去就想错了，本来想靠队友，结果队友也想错了，没办法破罐子...

文章目录     什么是拉格朗日插值法 模板 例题  1 CF622F BZOJ2665 BZOJ4559       什么是拉格朗日插值法 本文转载自 https://riteme.github.io/blog/2017-3-18/lagrange-interpolation.html 大佬写的太好了   当然求自然幂数和有很多种方法 Acdreamer 模板 namespace polysum { #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) const ...

A Monotonic Matrix   感谢楼下指正@Ruger      先备知识   LGV 算法 (Lindström–Gessel–Viennot lemma)   求以上矩阵的行列式，其中 e(a,b) 是从a到b的方法数，带入求行列式即可得到(a1,a2,...an) 到 (b1,b2,...bn) 的所有不相交路径的种数   思路   考虑01和12的分界线 是(n, 0)到(0，m)的两条不相交（可重合）路径 分界线以及分界线以上的点是一种，分界线下是一种 平移其中一条变成(n-1, -1)到(-1，m-1); 变成      然后进行预处理打表前2*n的阶乘和阶乘逆元就行了...

A Monotonic Matrix 先备知识 LGV 算法 (Lindström–Gessel–Viennot lemma)[LGV 算法就是求从     {    a   1    ,    a   2    ,   .   .   .    a   n    }    \{a_1,a_2,...a_n\}   {a1​,a2​,...an​} 到     {    b   1    ,    b   2    ,   .   .   .    b   n    }    \{b_1,b_2,...b_n\}   {b1​,b2​,...bn​} 的不交路径的条数  求以上矩阵的行列式，其...