首先把问题转化为将每一天中 还存活的起点数量 计入贡献。
然后考虑单独一维 j j j的情况。
注意到从第 2 2 2轮开始，每次死的起点数是固定的。设最后 i i i步新死的起点数是 f j f_j fj（事实上 f j f_j fj和进行的轮数无关，只和维度 j j j有关），那么事实上这是个一次函数。
首先第 1 1 1轮单独算。然后第 T + 2 T+2 T+2轮贡献 ∏ j = 1 k ( w j − r j + l j − T × v − f j ) \prod_{j=1}^k(w_j-r_j+l_j-T\times v-f_j) ∏j=1k(wj−rj+lj−T×v−fj)是 k k k次多项式，求其前缀和为 k + 1 k+1 k+1次多项式。
基于以上观察，我们可以拉插求解，复杂度 O ( n k 2 ) O(nk^2) O(nk2)。
总结：问题的关键在于想到周期性的规律，然后大力多项式。（ y l y yly yly说这是最基础的题了。。。）
#include拉插做法比较复杂。滚回去学多项式基础了
考虑简单 d p dp dp。然后是关键的观察：
1.1 1.1 1.1 从 [ 0 , m ] [0,m] [0,m]中选 n n n个数，满足非零数单调递增的方案数是 ( n + m n ) \binom{n+m}{n} (nn+m)
证明：考虑枚举 0 0 0的个数，答案是 ∑ i = 0 n ( n i ) ( m n − i ) \sum_{i=0}^n\binom{n}{i}\binom{m}{n-i} ∑i=0n(in)(n−im)。容易发现它等价于从 n + m n+m n+m个数中选取 n n n个数，也就是 ( n + m n ) \binom{n+m}{n} (nn+m)。
如果钦定第 n n n个数非零的话，答案是 ( n + m n ) − ( n + m − 1 n − 1 ) \binom{n+m}{n}-\binom{n+m-1}{n-1} (nn+m)−(n−1n+m−1) 。
设 f i , j f_{i,j} fi,j表示第 i i i个学校派出的划艇数目在第 j j j段的方案数。显然维护前缀和转移。复杂度 O ( n 3 ) O(n^3) O(n3)。
其实做到这一步可以想到拉插，形式化的说，每一段 [ a i , a i + 1 ) [a_i,a_{i+1}) [ai,ai+1)对应一个 n n n次多项式。
怎么观察到这一步的呢。注意看每一段里面具体的 j j j只影响组合数的值，前面公共的那一坨可以看成常数，而组合数又是与 j j j有关的多项式，于是可以拉插。自然一段内的前缀和也是 n + 1 n+1 n+1次多项式。
具体实现看代码。
我信仰什么，我便实现哪种方法。
#include大常数拉插。好逊啊
#include这题挺烦的。
把 a i a_i ai, a i − K a_i-K ai−K, b i b_i bi, b i − K b_i-K bi−K塞进去离散化，很容易看出这是一个分段多项式。对每一段分别求答案，实现时还是对前缀和插值。
树 d p dp dp求链的时候在 L C A LCA LCA处统计答案。第一个问题的多项式次数是 n + 1 n+1 n+1，第二个问题的多项式次数是 n + 2 n+2 n+2。
复杂度 O ( n 3 ) O(n^3) O(n3)。
细节贼多。恶心死我了。
#include玄学 d p dp dp优化。。。
不难看出这是一个区间 d p dp dp/kk
记 f l , r , M f_{l,r,M} fl,r,M表示区间 [ l , r ] [l,r] [l,r]中每个位置高度均不大于 M M M的方案数。
注意到从区间最大高度出发能移动到整个区间，并且将整个区间分成了两个独立的子问题，那么 f l , r , M = ∑ k = 1 M f l , m i d − 1 , k × f m i d + 1 , r , k − 1 [ a m i d ≤ k ≤ b m i d ] f_{l,r,M}=\sum_{k=1}^Mf_{l,mid-1,k}\times f_{mid+1,r,k-1}[a_{mid}\le k\le b_{mid}] fl,r,M=∑k=1Mfl,mid−1,k×fmid+1,r,k−1[amid≤k≤bmid]。答案是 f 1 , n , max b i f_{1,n,\max b_i} f1,n,maxbi。时间复杂度 O ( n 2 A ) O(n^2A) O(n2A)。
注意到答案是分段多项式。因此对于一段区间只需维护 n n n项取值。复杂度 O ( n 4 ) O(n^4) O(n4)。
注意到有用区间只有大概 O ( n ) O(n) O(n)个，因此总复杂度 O ( n 3 ) O(n^3) O(n3)。
代码比较恶心。