-
题意
给定数组\(a_{N,M}\)和\(b_N\),定义序列\({c_N}\)满足:
\[c_i=\sum_{j=0}^{N-1} a_{j,b_{i\times j\bmod N}} \]求第\(K\)大的\(c_i\)
\(N < 2.5\times 10^5,M \leq 4,a_i,b_i \in [0,1024)\)且保证\(N\)为质数
-
题解
注意到\(M \leq 4\),所以\(c_i\)可以写成这样:
\[c_i=\sum_{k=0}^{M-1} \sum_{j=0}^{N-1} a_{j,k}[b_{i\times j\bmod N}=k] \]因为\(N\)为质数,所以此时可以运用经典套路,设\(N\)的原根为\(g\),将每个\(i \to i'(g^{i'} \equiv i\pmod N)\)所以有
\[c_i=\sum_{k=0}^{M-1}\sum_{j=0}^{N-2} a_{j,k}[b_{(i+j)\bmod (N-1)}=k] \]我们令\(g_i=[b_{i\bmod (N-1)}=k]\),第一层循环不看,就有
\[ \sum_{j=0}^{N-2} a_jg_{i+j}
\]
这显然是一个卷积的形式,可以考虑翻转或倍长。
这样就做完了,时间复杂度\(O(MN\log N)\)
-
一些细节
因为\(0\)无法用原根的幂表示,所以对于下标为\(0\)的特殊处理一下。如果有更简单的方法或者说我写的有问题,欢迎大家指出。