链接

题意

        一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。
        (2 <= M, N <= 200)
        (1 <= A[i,j] <= 10000)

题解

        将两条路都看做从左上角出发，dp[i][j][k][l]代表第一次走到(i,j)第二次走到（k,l）的最大价值，
        转移方程很好写，看似n^4个状态，但是能够注意到i+j=k+l才是合法状态，于是状态变为n^3

链接

题意

        给n个节点的无根树，边权为1，求树上所有路径长度的和。

题解

        随便找个点作为根，树形dp出son[i]：子树i的节点的个数，再来一遍树形dp就可以求出以i为起点的所有路径长度的和。

链接

题意

        我们把一个数称为有趣的，当且仅当：
        1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
        2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
        3. 最高位数字不为0。
        因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
        请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。

题解

        推转移，得到一个状态机，用矩阵快速幂加速

链接

题意

        给一个长为n的序列，输入一个询问k,l,r,从中选出k个长度介于[l,r]中的不同的区间，最大化 k个子段和 的和，
        n<5e5  20s 

题解

        先想一个暴力算法，我们把所有长度介于[l,r]的子段的和都求出来，放进一个堆，然后取出前k大
        然后来优化它，我们观察取出前k大的方法，是一个一个取出来的，这就说明了，一次只取出了一个，这就是突破点于是我们这样来做，我们对每一种区间按终点分类，显然可能取出来的，一定是以当前终点为终点的所有区间中最大的那一个，那我们就维护数列f[]
        f[i]代表以i为终点的所有可取且未取区间中区间和最大的那一个，于是我们这样来查询，每次取出f数组的最大值，然后更新f数组，如何更新呢？我们再多记录一个信息，记录当前的f[i]是原先所有以i为终点的所有选择中的第几大，假设现在这个是第k大，当我们取出来之后，只要更新f[i]即可，更新可选择的第k+1大
        我们来加速这个过程，发现f可以用堆来维护,用一个三元组: <EndAt,val,kth>分别代表该区间以EndAt为结尾，区间和为val，此区间是所有以EndAt为终点的可选区间的第kth大，此三元祖按照val建堆即可。

链接

题意

        1.求森林任意路径第k大，2.森林合并，森林点个数1e5

题解

        在主席树上加上启发式合并即可，合并的时候更新lca的倍增数组，启发式生成新的主席树，可以证明合并的均摊时间复杂度为lg级别

链接

题意

        在一个只含有a,b的字符串中选一个子序列，
        1.不能是子串
        2.位置和字符都关于某条对称轴对称

题解

        枚举对称轴在下标i处，大致推导如下
        \sum_{x}{[a[i+x]==a[i-x]]}\\
        C-\sum_{x}{(a[i+x]-a[i-x])^2}\\
        C-\sum{(a[I+x]^2+a[i-x]^2-2a[I+x]a[I-x]}\\
        C+2\sum{a[I+x]a[i-x]}
        fft

链接

题意

        给一个序列，长度为n（<1e5)，m个操作，每次删除一个数，删除数后要求你输出删除前整个序列的逆序对的个数

题解

        用树状数组套主席树,维护权值线段树，被删除的数的前面的区间上有多少个数大于被删除数，被删除的数的后面的区间有多少个数小于被删除数，
        这个很容易在线段树上实现，更新的话，是主席树的套路更新。

链接

题意

        那是一张图片

题解

        E_j=\sum_{i=0}^{j-1}{\frac{q_i}{(i-j)^2}}-\sum_{i=j+1}^{n}{\frac{q_i}{(i-j)^2}}\\
         if f[I]=\frac{1}{i*i}\\
        E_j=\sum_{I=0}^{j-1}{q_i*f(j-i)}-\sum_{I=j+1}^{n}{q_i*f(i-j)}\\
        前面一项下标和为定值，后面一项下标差为定值
        fft

链接

题意

        给你很n个时间段以及这一段的权值（n<1e5），m个询问（m<1e5）询问任意时间点上，前k小的权值的和

题解

        离线时间段后，维护每一个时间点点权值线段树，在维护权值线段树的时候多维护一个信息->权值和

链接

题意

        小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

题解

        dp[i][j]前i个数积为j的方案数，答案在dp[N][X]
        dp[i][j]=dp[i-1][j/S[1]]+dp[i-1][j/S[2]]...
        换成原根就成了减法，然后构造一个多项式，发现dp[i]=dp[i-1]*u
        最后dp[i]=dp[1]*u^(n-1)
        用快速幂加速NTT