题意
做法
定义0：(c_i,d_i)与题意中相同；令(D)为题意中的(k)，即维数。
定义1：令((i,j))为第(i)轮第(j)步。
定义2：对于((i,j))，如果存在位置此时走出界限，则称其为最值。令最值集合为(S)。
定义3：令向量(vec{v})为一轮后各维的增量
定义4：容易发现，(forall (i,j)in S)，(exists {(l_1,r_1),(l_2,r_2),cdots,(l_k,r_k)})
出界位置为：({(x_1,x_2,cdots,x_D)|l_ile x_ile r_i,iin[1,D]})（易得(l_{c_j}=r_{c_j})）。
令向量(vec{w_{i,j}}={r_1-l_1+1,r_2-l_2+1,cdots,r_D-l_D+1})。
结论1：对于(ige 3)，若(forall (i,j)in S)，则((i-1,j)in S)，且满足：
（1）
对于(i=1)，((i,j)in S)，其贡献为(j(prodlimits_{k=1}^{D}len_k))
（2）
对于(i=2)，((i,j)in S)，令(len_k=vec{w_{i,j}}_k)，其贡献为((n+j)(prodlimits_{k=1}^{D} len_k))
根据结论1，若((i+lambda,j)in S)，其贡献为((lambdacdot n+j)(prodlimits_{k=1,k
eq c_j}^D (len_k-lambdacdot n)))
根据结论1,(exists limit,s.t.~(i+lambda,j)in S(lambdain[0,limit]))
总贡献为
我们将((lambda cdot n+j)(prodlimits_{k=1,k
eq c_j}^D (len_k-lambdacdot n)))写成关于(lambda)的(D)次多项式(F(lambda)=sumlimits_{k=0}^D f_klambda^k)。
那么总贡献为
(egin{aligned}
sumlimits_{lambda=0}^{limit}F(lambda)&=sumlimits_{lambda=0}^{limit}sumlimits_{k=0}^D f_klambda^k\
&=sumlimits_{k=0}^D f_ksumlimits_{lambda=0}^{limit}lambda^k\
end{aligned})
具体讲一下代码流程：
(O(nD))算((i=1,j)in S)的贡献
(O(D^2))预处理，(kin[0,D])的自然数幂和多项式系数
(O(nD^2))算((i=2,j)in S)的(F(lambda))，(O(nD^2))求(sumlimits_{lambda=0}^{limits}F(lambda))
总复杂度(O(nD^2))