题意
把题面搬这里了
细节
- 仅关键点范围在({0,...,d-1})
- 本身值域是无限的
- (a_ile 2.5 imes 10^5)，这说明(20)维，(d=4)时，实际关键点高维是(0)...这里坑死了...
做法
下面讨论(d=4)的情况
若以原点出发，本质不同的关键点是不多的，记一个点为状态({d_0,d_1,d_2,d_3})，走(K)步的方案为(dp_{b_1,b_2,b_3})
在处理(dp)数组前，先预处理一些东西
- (f_{i,j,k})为在(j)维空间中，从原点走(k)步到((i,i,...,i))的方案数
- (h_{i,j})为只考虑(b_0,...,b_i)下，走(j)步到达该点的方案数
- (g_i)为走恰好(i)步到达({b_0,b_1,b_2,b_3})
(dp_{b_1,b_2,b_3}=sumlimits_{i}g_i imes 40^{K-i})
然后(O(N^2))算坐标差就好了
考虑优化算差过程
在手玩(d=2)时发现是异或，如果凭直觉(d=4)也是异或就全完了...
定义(oplus)为差运算，实际对于某一位来说，是算(|a_i-b_i|)
对数组定义(oplus)，(a=foplus g)：$$a_{x}=sumlimits_{i,j}[ioplus j=x]f_i imes g_j$$
在(d)进制下，记(a_i)为数组(a)最高位为(i)的子数组，有
(egin{aligned}\
a_0&=f_0oplus g_0+f_1oplus g_2+f_3oplus g_3\
a_1&=f_0oplus g_1+f_1oplus g_0+f_1oplus g_2+f_2oplus g_1+f_2oplus g_3+f_3 oplus g_2\
a_2&=f_0oplus g_2+f_2oplus g_0+f_1oplus g_3+f_3oplus g_1\
a_3&=f_0oplus g_3+f_3oplus g_0\
end{aligned})
(x'=(f_0+f_1+f_2+f_3)oplus (g_0+g_1+g_2+g_3),~~y'=(f_0-f_1+f_2-f_3)oplus (g_0-g_1+g_2-g_3))
则(x=a_0+a_2=(x'+y')/2,~~y=a_1+a_3=(x'-y')/2)
类似的，可以将(a_0,a_2)和(a_1,a_3)分开
复杂度(T(n)=O(N)+6T(N/4)=N^{log_46})