传送门  BZOJ2154  题意： 求 ∑ni=1∑mj=1lcm(i,j)  ∑ i = 1 n ∑ j = 1 m l c m ( i , j )  Solution: 看到此题首先想到这步：    ∑i=1n∑j=1nlcm(i,j)=∑i=1n∑j=1nijgcd(i,j)  ∑ i = 1 n ∑ j = 1 n l c m ( i , j ) = ∑ i = 1 n ∑ j = 1 n i j g c d ( i , j )   然后开始拼命化简，未果 听完dalao的提示：莫比乌斯反演题一定要想办法搞掉分母，想办法枚举约数 想到了下一步：  =∑min(n,m)d=1d∑⌊nd...

权限题。 题意： 给定a,b,c,求满足方程 Ax+By<=C 的非负整数解  A,B<=109,C<=min(A,B)∗109  Solution: 类欧几里得算法模板题 没学过的点击这里 变形一下这个式子：  y<=C−AxB  但是这个式子如果直接套用类欧几里得是包含负数的，我们需要想办法帮他变变形：考虑这个式子的几何意义：线段 y=C−AxB 和x轴，y轴所围成的图形中的整点的个数，我们再考虑类欧几里得的几何意义：一条倾斜直线与x=0和x=n两条铅垂线组成的直角梯形内整点数量，因此我们想办法变a为正，调整截距使得新直线在x轴上的切点>-1且<0（避免...

题意：  小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。  为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。  施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修...

改编题意：  有n杯水排成一行，第i杯水中有 wi 单位体积的水. 他会选择一个区间 [l,r] ，  并拿一个初始为空的杯子（杯子的容积无限大），他可以重复无限次以下操作：  • 选定任意一杯水i， i∈[l,r] ．  • 使i和它拿着的杯子里的水的体积变为它们的平均值．  小C希望进行若干操作后最大化杯子里的水的体积，设 g(l,r) 为这个最大值．你需要求：     ∑l=1n∑r=lng(l,r)n2    精度误差不超过   10−6  Solution: 对于一段区间 [l,r] ，设倒数第i次操作中选的数为 ai .那么最终产生的价值为： ∑r−l+1i=1ai2i   因此我...

传送门 题意： 幽香要修建幻想乡的公路。幻想乡有 N 个城市，之间原来没有任何路。幽香向选民承诺要减税，所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司，她打算让每个建筑公司都负责一条路来修。  每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算选择 N-1 条能够连接幻想乡所有城市的边，然后每条边都交给一个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修一条边。幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它们要么修的边的集合不同，要么边的分配方式不同。 Solution： 给出一个图，求这个图的生成树个数...

传送门  题意：  给你一棵树，有三种操作：  1. 给一个点及其子孙赋值为1  2. 给一个点及其祖先赋值为0  3. 求一个点是1还是0 Solution：  这道题显然可以用树剖做，但是复杂度不优秀（两个log），这里说一种一个log的做法：  先跑出树的dfs序，对dfs序建一棵线段树，那么操作1就变的非常简单，我们重点需要考虑的是操作2：暴力给每个点赋值是会T的，我们可以先只修改一个最下面的点，即这个点本身，那么就需要把3操作改为查询这个点的子树是否全1，因为如果这个点的子树中不是全1，那么这个点一定是0，只是这个点并没有被更新到而已，同时，在操作1中，如果我们选中的这个点为0，那么...

题意： 一个数是非回文数当且仅当不包含长度大于1的回文数。比如16276是无回文数，而17276因为含有727而不是。  求区间内有多少个非回文数。 Solution： 非常经典的数位dp问题，一开始想到f[len][pre][pre2][0/1]表示第len位，第len-1位是pre，第len-2位是pre2，是否到达上界的方案数，但是发现这种状态下前导零会影响答案，那么我们多存储两个状态：f[len][pre][pre2][zero1][zero2][0/1]表示第len位，第len-1位是pre，第len-2位是pre2，第len-1位是否是前导零，第len-2位是否是前导零，是否到达上...

传送门  题意： 给定n及m个数a[1…m],再给定一个模数P，求  ∑ni=1Cain−∑i−1j=1aj%P  ( 1≤n≤109,1≤m≤5 ,设 P=pc11∗pc22∗pc33∗…∗pctt ， pi 为质数, 1≤pcii≤105 ) Solution: 扩展lucas定理模板题 这个算法理解起来比较方便，但是写的时候就不是那么好写了… 我们把p拆成 pc11∗pc22∗pc33∗…∗pctt 的形式，这样我们只需要求出每个 C(n,m)%pcii ,再用CRT合并即可 而C(n,m)可以转化成阶乘及阶乘的逆元的乘积，由于扩欧求逆元要求互质，所以说我们计算阶乘时需要提取出和 pci...

vjudge传送门 题意： 有一个公差集合{D}，有n个数字  每次执行以下操作：  1. 在当前剩下的有序数组中选择x(x≥2)个连续数字；  2. 检查1选择的x个数字是否构成等差数列，且公差 d∈{D} ;  3. 如果2满足，可以在数组中删除这x个数字；  4. 重复 1−3 步，直到无法删除更多数字。  问最多能删掉多少个数字。 Solution： 一看就是区间dp，f[l][r]表示区间[l,r]中最多能删多少个数，因为所有的等差数列最终都可以拆成长度为2和3的数列，所以转移时我们只需要考虑长度为2和3的序列即可：预处理所有长度为2和3的区间，dp时分成两种情况：左右各成为等差序列...

传送门 题意： 从区间[L,H]（L和H为整数）中选取N个整数，求N个整数最大公约数刚好为K的选取方案有多少个，答案模1e9+7  1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5 Solution： 并不是非常理解莫反怎么做= = 注意到H-L≤10^5  尝试在这上面做文章  首先简化题意：   [⌈Lk⌉,⌊Hk⌋] 中可重复的选出N个数使其gcd=1  那么我们可以用f[i]表示在区间中选出的数的最大公约数为i且选出的数不全相同的方案数，我们先求出区间中i的倍数个数x，暂时令 f[i]=xN−x   但是此时的f[i]实际上是最大公约数为i及i的倍数的方案数，所以说我们需要...

题意： 给一个n,m的矩阵dx,y,构造一张小于300个点的有向图，边上的权值范围为[0,100]，也可以是未知整数x或y，要求给出固定的S，T，当x分别取[1,n]，y分别取[1,m]时，S到T的最短路为 dx,y    1≤n,m≤10    1≤dx,y≤100(1≤x≤n,1≤y≤m)  Solution: 正解为贪心建图然后重新计算d矩阵看和原来矩阵是否相同，复杂度 O(n3)   自己YY了一个做法：  S到T每条路径所对应的值为 ax+by+c ，这个值对应d数组，一定满足 ax+by+c≥dx,y ,那么我们可以枚举a,b,c，枚举x,y，遇到符合条件的a,b,c就把他存入一个...

传送门 题意： 给出一个n个数的数列 ai​  a i ​ ,考虑其中所有gcd大于1的集合，每个集合的贡献是gcd乘上集合的大小，求这个数列的总贡献%1e9+7  (1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000000)  ( 1   ≤   n   ≤   200000 , 1   ≤   a i   ≤   1000000 )  Solution: 一开始一直在想与n有关的复杂度的算法没想到最后跟a的大小有关… 遇到这种需要求有关集合这种dp和数据结构都不好使的题，我们需要想到用容斥和组合数来求！！！ 我们用cnt[i]来表示a中是i的倍数的数的个数 f[i]表示gcd为i的集...

题意： 给出a,b,计算 C[k]=∑n−1i=ka[i]∗b[i−k]  C [ k ] = ∑ i = k n − 1 a [ i ] ∗ b [ i − k ] , n<=1e5  n <= 1 e 5  Solution: 回想多项式乘法： ∑2n−2k=0(∑k=i+jai∗bj)xk  ∑ k = 0 2 n − 2 ( ∑ k = i + j a i ∗ b j ) x k  如果相乘的两个式子下标和为定值，那么我们就可以使用FFT优化了 但是题目中的式子并不是定值啊 翻转一下b数组，式子就会变化为 ∑n−1i=ka[i]∗b[n−i+k]=∑i+j=n+ka[i]∗...

传送门 题意： 给出n个数 qi  q i ,F和E的定义如下：   Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2  F j = ∑ i < j q i q j ( i − j ) 2 − ∑ i > j q i q j ( i − j ) 2  求 Ei(n≤1e5,q≤1e9)  E i ( n ≤ 1 e 5 , q ≤ 1 e 9 )  Solution: 化简式子： Ej=∑i<jqi(i−j)2−∑i>jqi(i−j)2  E j = ∑ i < j q i ( i − j ) 2 − ∑ i > j q i ( ...