( exttt{D1T1})
有一个 (n imes n) 的矩阵，重复 (k) 次，每次同时把 (a_{i,j}) 赋值为 赋值为 (i) 这⾏的和加上 (j) 这列的和，注意 到 (a_{i,j}) 自己的贡献是算两遍的。
求出 (k) 次变化后的矩阵对一个模数 (p) (不一定是质数)取模的结果.
(1leq nleq 1000,0 leq k leq 10^9,2 leq p leq 10^9)
( exttt{题解})
考虑一个 (a_{x,y}) 对 (a_{i,j}) 的贡献。
把平面上的点分为四类 : ((i,j)) , ((i,x)(x eq j)) , ((x,j) (x eq i)) , ((x,y) (x eq i,y eq j)) 然后随便讨论一下贡献就行。
复杂度 (Theta(n^2))
( exttt{D1T2})
初始有一个长度为 (n) 的序列 ，每次给定区间 ([l,r]) 并执行以下两种操作之一：
(1.) 令 (i) 从 (L) 循环到 (R-1) ，将 (a_i) 赋值为 (max(a_i,a_{i+1}))
(2.) 查询 ([l,r]) 从左往右前缀 (max) 单调栈元素之和
( exttt{题解})
考虑记 (r_i) 为一开始数列上的 (a_i) 往左延伸到的位置。
维护 (r_i) 不难，修改的时候区间 (-1) 即可，可以线段树维护。
考虑查询，先找到 ([l,r]) 对应一开始数列上的区间，这个可以在线段树上二分实现; 接下来套用楼房重建的做法即可。
接下来考虑，有一些位置可能消失，消失的情况，一定是被一个比它大的数字覆盖了。
覆盖只可能在每次修改的 (l) 位置发生，因此直接 (check) 就行，然后就是支持删除的楼房重建了，复杂度 (Theta(nlog^2n))
( exttt{D1T3})
德州扑克
( exttt{题解})
这种题真的能做?
( exttt{D2T1})
给一颗树,记 (x) 到 (y) 的树上距离为 (f(x,y))
现在删去 (k) 条边然后加上 (k) 条边，保证原图还是树，
求所有⽅案所得树权值之和对 (998244353) 取模的结果.
(nleq 10^5,k ∈ {0,1})
( exttt{题解})
(k = 0) 随便做。
(k = 1) 考虑每条边的贡献和贡献变化，子树和祖先链上分别递推一下就行
复杂度 (Theta(n))
( exttt{D2T2})
有 (n) 个物品，第 (i) 个价值为 (a_i) ，有一种代金券，如果花了 (c) 块钱就给你一张代金券 你可以用一张代金券来换一块钱，注意换出来的钱是不可以继续参与代金券的兑换的。
也就是你可以用掉 (b) 张代金券（前提是你有 (b) 张），再花 (a_i-b) 元，拿到 (lfloor frac{a_i-b}{c} floor) 张代金券。 有 (q) 次单点修改，每次改完你都要求出，当前按顺序购买最少花的钱数。
(1leq n,q leq 3 imes 10^5,a_i,c leq 10^{12})
( exttt{题解})
二分一个位置 (i) 使得后缀 ([i+1,n]) 全用代金券解决，这个位置必然是唯一的。
接下来考虑前缀 ([1,i)) 当中应该如何使用代金券。 (i) 这个位置需要一些分类讨论。
首先，如果我们破坏了 ([1,i)) 中的获取代金券的机会，这是不赚的，肯定是拿到 (i) 这个位置破坏。
前缀 ([1,i)) 中代金券的使用也很简单，当我们去掉后缀 ([i+1,n]) 需求的代金券数目之后，我们只需要查询类似 (min(sum d_i-sum e_i)) 的东西就行，其中 (d_i= lfloor frac{a_i}{c} floor,e_i=a_i-d_ic)
复杂度 (Theta(q log n))
( exttt{D2T3})
有 (n) 个 ([0,m]) 的随机变量，求满足以下条件的概率 ： 任何⼀个长度为 (k) 的区间内包含的随机变量不超过 (2) 个.
(1leq k leq m leq 150, 1leq n leq 50)
( exttt{题解})
首先将每个数字分为整数部分和小数部分，由于小数部分相等的概率 (=0) , 所以小数部分可以记成一个排列。
那么不难有这么一个 (dp) 状态 :
(f[n][m1][n1][m2][n2]) 表示前两个数字的整数部分分别为 (m1,m2) , 小数部分的排名为 (n1,n2) , 且已经放了 (n) 个数的方案数。
看起来状态是 (Theta(n^3m^2)) 的，但实际上整数部分如果距离 (>k) 那么这个状态是没有意义的，所以状态总数是 (Theta(n^3mk)) 的. 又因为 (nk) 是不超过 (O(m)) 的所以状态总数 (Theta(n^2m^2))
转移就直接枚举下一个是什么，需要特殊考虑整数部分相同时的贡献。
可以用前缀和优化， (Theta(n^2m^2))。经过卡常的暴力转移应该也能通过。