权限题 题意： 有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。这两个串已经老化了，每个串都有不同程度的残缺。 你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?  1<=m<=n<=300000  1 <= m <= n <= 300000  Solution： 神奇的FFT解决字符串问题…. 我们把 ∗  ∗ 看成0，定义一个两个长度相等的串之间的距离为：   dis(a,b)=∑len−1i=0(a[i]−b[i])2∗a[i]∗b...

权限题。 题意： 给出一颗n个节点的树，要给每一条边染一个1~n-1的颜色，染颜色i的代价为i，要求同一个节点连出的所有边所染颜色都互不相同，求一个为整棵树染色的方案，使得代价之和尽量小  n<=150  n <= 150  Solution: 网络流真的是万能的…  f[x][i]  f [ x ] [ i ] 表示节点x向其父亲连的边为i时x的子树所产生的最小贡献 看似非常不好转移 实际上就是非常不好转移 所以说我们另辟蹊径——费用流！ 我们对于每个点x枚举向它其父亲连的边col 每次我们把S向x的儿子节点连费用为0，流量为1的边，对于f数组的第二维建n-1个节点，除了我们枚举...

传送门 题意： Z国是一棵树，为了使Z国的交通更加便利顺畅，现决定在Z国的公路系统中确定若干条规划路线，将其中的公路全部改建为铁路。我们定义每条规划路线为一个长度大于1的城市序列，每个城市在该序列中最多出现一次。任意两条规划路线不能有公共部分。一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首都。我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的次数，而Z国的交通系统的“不便利值”为所有城市的不便利值的最大值。 1.确定规划路线修...

传送门 题意： 给你k和一棵n个点的树，每个边边权为1，对每个点i求 ∑nj=1dis(i,j)k  ∑ j = 1 n d i s ( i , j ) k   n≤50000 k≤150  n ≤ 50000   k ≤ 150  Solution: 首先有一个结论： xn=∑ni=1Cix∗Sin∗i!  x n = ∑ i = 1 n C x i ∗ S n i ∗ i !  组合意义上的证明： xn  x n 表示在x个不同的盒子里放n个不同的球 然后我们枚举放在几个盒子里， Cix  C x i 表示在x个盒子里选i个要放球的盒子， Sin  S n i 表示把这n个球分配到这i个不...

传送门 题意： “简单无向图”是指无重边、无自环的无向图（不一定连通）。 一个带标号的图的价值定义为每个点度数的k次方的和。 给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。 因为答案很大，请对998244353取模输出。  1≤n≤109,1≤k≤200000  1 ≤ n ≤ 10 9 , 1 ≤ k ≤ 200000  Solution： 易知每个点的贡献是一样的 所以我们只需考虑一个点的贡献： 枚举这个点的度数，剩下的边可以随意填  sum=2(n−2)∗(n−1)∗∑i≤n−1i=0Cin−1∗ik  s u m = 2 ( n − 2 ) ∗ ( n − 1 ) ∗ ∑...

传送门 题意： 令 (1+2–√)n=e(n)+f(n)∗2–√  ( 1 + 2 ) n = e ( n ) + f ( n ) ∗ 2 ,其中 e(n),f(n)  e ( n ) , f ( n ) 都是整数。 令 g(n)  g ( n ) 表示 f(1),f(2)…f(n)  f ( 1 ) , f ( 2 ) … f ( n ) 的最小公倍数. 给定两个正整数n和p,其中p是质数，并且保证 f(1),f(2)…f(n)  f ( 1 ) , f ( 2 ) … f ( n ) 在模p意义下均不为0 请计算 ∑ni=1i∗g(i),1<=i<=n  ∑ i = 1 n i...

传送门 题意： 定义二元运算 opt 满足    x opt y={ x+yx−y,,x<yx≥y  x   o p t   y = { x + y , x < y x − y , x ≥ y   现在给定一个长为 n 的数列 a 和一个长为 m 的数列 b ，接下来有 q 次询问。每次询问给定一个数字 c  你需要求出有多少对 (i, j) 使得  ai opt bj=c  a i   o p t   b j = c  。 Solution： 首先我们抛开限制来看： 如果只考虑加法的话，对于每个询问k， ans=∑ki=0ai∗bk−i  a n s = ∑ i = 0 k a ...

题意： [0,x]中全是1，判断[1,n]中的点i中是0还是1需要权值 ai  a i ，最坏情况下求得到x的最小权值  n<=2000  n <= 2000  Solution:  f[i][j]  f [ i ] [ j ] 表示只考虑[i,j]，最坏情况下求得到x的最小权值 那么 f[i][j]=minjk=i(max(f[i][k−1],f[k+1][j])+a[k])  f [ i ] [ j ] = m i n k = i j ( m a x ( f [ i ] [ k − 1 ] , f [ k + 1 ] [ j ] ) + a [ k ] )  这样就得到了一个 ...

传送门 题意： 在炉石传说中有这样的一个场面：n个随从，血量为1~n，现在去除m个随从，然后开始释放“亵渎”。每使用一张“亵渎”会获得一定的分数，分数计算如下：在使用一张“亵渎”之后，每一个被亵渎造成伤害的怪会产生 xk  x k 的分数，其中x是造成伤害前怪的血量，k是需要杀死所有怪物所需的“亵渎”的张数。  n≤1013m≤50  n ≤ 10 13 m ≤ 50  Solution: 可以发现这是若干个形如 Sum(n,k)=∑ni=1ik  S u m ( n , k ) = ∑ i = 1 n i k 的式子组成的 这就是经典的自然数幂和问题了 可以用累加法： 首先有一个式子： (n...

传送门 题意： 有 2 个技能： 1.锁定：对一名指定的敌方单位使用，以 p 的概率对该单位造成 1 点伤害。 2.结界：在一片区域施放结界，让该区域内的所有其他单位无法动弹。 如果一个单位的生命值降至 0 或 0 以下，那么该单位就会死亡。  现在有 n 个敌方单位（编号从 1 至 n），编号为 i 的敌方单位有  mi  m i  点生命值。  按顺序施放 Q 个技能： 1.对于锁定技能：针针会指定一个敌方单位 id，并对它施放。由于决定概率系数 p 的因素很多，因此每次的 p 都不一定相同。特别地，如果该敌方单位已经死亡，那么该技能不会造成任何效果。 2.对于结界技能：对 k 个指定的敌...

传送门 题意： 给出n,k,m，问有多少个序列组 (A0,A1,...,An)  ( A 0 , A 1 , . . . , A n ) 满足以下条件：  序列 Ai  A i 的长度恰好为i  所有元素均在 [1,k]  [ 1 , k ] 的范围内   Ai−1  A i − 1 是 Ai  A i 的子序列   Ai  A i 的字典序大于 Ai−1  A i − 1   答案模m输出。   n,k≤300  n , k ≤ 300  Solution： 我们考虑在一个长为n的序列中加入一个数x，使得新的序列的字典序要比之前的大 那么这个x只能加在某个比x小的数y的左边或者是序列末尾（如...

传送门 题意： 给定两个正整数数列，你要用它们来做一个游戏：你需要对数列进行若干次操作，每一次操作，应选择两个正整数 k1  k 1 和 k2  k 2  ，并删除第一个数列的最后 k1  k 1 个数，计算出它们的和 s1  s 1 ；删除第二个数列的最后 k2  k 2 个数，计算出它们的和 s2  s 2 。这一次操作的得分就是 (s2−k2)∗(s1−k1)  ( s 2 − k 2 ) ∗ ( s 1 − k 1 ) 。两个数列应同时被清空，不允许一个数列空了，而另一个数列中还有数。游戏的总得分就是每一次操作的得分总和。 求最小的总得分。 Solution: 首先我们把两个数列的权值...

传送门 题意： 这棵树上有 n 个节点，每个点的初始颜色为  ci  c i  。 接下来进行 q 个操作： 1.修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。 2.对于给定的树上某个点集 S ，定义某个点集内的点的权值为：  Wi=∑j∈ST(i,j)  W i = ∑ j ∈ S T ( i , j )  其中T(i,j)表示i到j的路径上的颜色的段数 每次指定树上 m 个节点作为点集，询问这 m 个节点的权值。  ，，，1≤n,q≤100000，ci,y≤109，∑m≤200000，m≤n  ， ， ， 1 ≤ n , q ≤ 100000 ， c i , y ≤ 10 9 ， ...

传送门 题意： n-1个数，分别为2~n，现从中取出若干数放入两个集合中，使A集合中所有数都和B集合中的所有数互质，求满足条件的方案数。  n≤500  n ≤ 500  Solution: 根据题意，在一个集合中选择一个数相当于选择了这个数的质因子集合，所以说两个集合的质因子集合的交集必须为空。 一个很简单的想法就是状压DP  f[i][S][T]  f [ i ] [ S ] [ T ] 表示第一个集合的质因子集合为S，第二个集合的质因子集合为T，满足上述条件只考虑前i个数的方案数，转移即为  f[i+1][S|Si][T]+=f[i][S][T],Si∩T=0  f [ i + 1 ] ...