Lianjie 化简一下公式：      p   =   1    0   9    +   7    p=10^9+7   p=109+7       ∑    i   =   1    n     ∑    j   =   1    m     (   i   j    (   n   %   i   )     (   m   %   j   )    )    %   p    \sum ^{n}_{i=1}\sum ^{m}_{j=1}\left( ij\left( n\% i\right) \left( m\% j\right) \right) \% p   ∑i=1n​∑j=1m...

题目链接 大意：给你一个长度为n的数组，m个询问，每次询问给你一个区间     [   l   ,   r   ]    [l,r]   [l,r]，给你一个p 设长度为     r   −   l   +   1    r-l+1   r−l+1的数组S，其中      S   i    =   ∣   p   −    a    l   +   i   −   1     ∣   ,   i   ∈   [   1   ,   r   −   l   +   1   ]    S_i=|p-a_{l+i-1}|,i\in[1,r-l+1]   Si​=∣p−al+i−1​∣,i∈[1,r−...

题目链接 大意：给你两个字符串a,b，问你第一个字符串有多少子序列的十进制表示大于第二个字符串的十进制表示 思路：考虑     d   p    dp   dp      d   p   [   i   ]   [   [   0   ]   表   示   a   字   符   串   中   长   度   为   i   的   子   序   列   等   于   b   的   个   数    dp[i][[0]表示a字符串中长度为i的子序列等于b的个数   dp[i][[0]表示a字符串中长度为i的子序列等于b的个数      d   p   [   i   ]   [   ...

题目链接 大意：给你一个长度为n的数组和一个k，让你将数组连续的分成k段(可以丢弃末尾)，使得每段和的最大值最小。 思路：先将前缀和离散化，然后考虑二分答案，对每个mid，我们考虑dp来check， 枚举每个数     i   ,   i   ∈   [   1   ,   n   ]    i,i\in[1,n]   i,i∈[1,n]，如果     s   u   m   [   i   ]   ≤   m   i   d   ，    sum[i]\leq mid，   sum[i]≤mid，那么显然     d   p   [   i   ]    dp[i]   dp[i]最小是1，...

题目链接 大意：给你一个数组，让你求出最长的 字典序最大和最小的(先升后降)单峰子序列 思路：考虑dp      L   [   i   ]   [   0   ]   表   示   a   [   i   ]   一   定   取   ，   序   列   a   [   1..   i   ]   的   最   长   上   升   子   序   列   长   度   。    L[i][0]表示 a[i]一定取，序列a[1..i]的最长上升子序列长度。   L[i][0]表示a[i]一定取，序列a[1..i]的最长上升子序列长度。      L   [   i   ]   ...

蔡勒公式（日期->星期）     <mstyle displaystyle="true" scriptlevel="0">  w   =    (   y   +    [    y   4    ]    +    [    c   4    ]    −   2   c   +    [     26   (   m   +   1   )    10    ]    +   d   −   1   )        m   o   d     7   <...

题目链接 大意：给你两个数n，k，让你求出n的所有全排列中差异序列字典序第k小的排列 差异序列为      p   i    =    a    i   +   1     −    a   i    ,   i   ∈   [   1   ,   n   )    p_i=a_{i+1}-a_i,i\in[1,n)   pi​=ai+1​−ai​,i∈[1,n) 思路：直接dfs枚举差异序列从小往大搜，然后对不合法的情况去掉(差异序列中元素的最大-最小<n-1才合法，重复的也不合法) 细节见代码： #include<bits/stdc++.h> #define LL lon...

题目链接 题意:给你一个一个式子      ∑    i   =   1    n    ∣    a   i    ∗   x   +    b   i    ∣   =   c    \sum_{i=1}^n|a_i*x+b_i|=c   ∑i=1n​∣ai​∗x+bi​∣=c，让你求出x的所有解，从小到大排序。 思路：因为给的n个一次函数的零点是唯一的，我们对n个函数按照零点从大到小排序，然后遍历n个点，显然当遍历到k时，[1,k]都会取得相反数，然后我们判断当前解是否合法，再判断是否是无穷多解。 讨论完成之后就是对所有解排序，去个重就行了 #include<bits/stdc++...

题目链接 很早就想学的模板，由于懒拖到现在（其实是菜） 树链剖分其实是将树形结构处理成线性序列然后用数据结构来维护树的一个东西。可以解决很多树上问题。 具体重要的三个函数为： 一.dfs1 第一遍dfs遍历这颗树，处理出每个点的子树大小（包含自己）为     s   i   z    siz   siz，节点的父亲节点为     f   a    fa   fa，节点的深度为     d   e    de   de,还有每个节点的重儿子(siz值最大的儿子) void dfs1(int now,int pre,int d){ siz[now]=1; fa[now]=pre; de[now]=...

题目链接 思路：我们考虑合并区间     [   l   ,   r   ]   ，   r   >   l    [l,r]，r>l   [l,r]，r>l在不精炼的情况下的贡献是一定的，我们用数组     A    A   A记录这个的前缀和， 用数组     L    L   L记录以     i    i   i结尾的精炼一个后缀的最小贡献， 那么     L   [   i   ]   =   m   i   n   (   L   [   i   −   1   ]   +   k   ∗   k   ∗   p   [   i   −   1  ...

题目链接 大意：给你一个      2   n    ∗    2   n     2^n*2^n   2n∗2n的正方形，你每次可以选择一个边长大于1的正方形等分成四份，现在让你切k次，使得左下角到右上角存在一个路径，路径上的正方形边长都相同。 思路：枚举边长，判断k是否在最小最大的范围内 推荐这个博客 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace st...

题目链接 大意：给你两个字符串     a   ,   b    a,b   a,b，让你在a中删除一个子串，使得b仍然是新a串的一个子序列 思路：我们用a正着跑一下序列自动机，然后倒着跑一次序列自动机。然后我们思考一下，假设我们删除的子串位于     [   l   ,   r   ]    [l,r]   [l,r]这个区间，那么子序列如果分成了两部分的话，那么一部分的子序列就在     [   1   ,   l   )    [1,l)   [1,l)，一部分在     (   r   ,   l   e   n   g   t   h   ]    (r,length]   (r,l...

题目链接 大意：现在有n个人，每个回合都有一对人成为朋友，让你在首回合开始前和每回合结束后输出选4个人，每个人都不是朋友的方案。 思路：显然正着的情况我们不好讨论，我们可以计算出不合法的情况，然后用全部的减去不合法的。 全部的显然是     C    (   n   4    )    C(_n^4)   C(n4​), 不合法的情况我们分几类出来 x表示朋友组的人数 1.从所有大于等于2的一组朋友选2个人，另外的随便选两个      ∑    x   ≥   2     C    (   x   2    )   ∗   C    (    n   −   x    2    )    \s...

题目链接 大意：给你n个木块，k个人。每个人有三个参数     l   ,   p   ,   s    l,p,s   l,p,s,分别表示每个人最多加工的木块数，每个人加工一个木块的贡献，每个人加工木块区间必须包含的 木块编号 思路：先看题，考虑     d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]表示第i个人加工到j号木块的最大贡献，     T   [   i   ]    T[i]   T[i]表示加工i个木块的最大贡献 然后我们每次遍历i转移就是      d   p   [   i   ]   [   j   ]   =...