题解 P6306 【「Wdsr-1」小铃的书】

· · 题解

更好的阅读体验 -> 推销博客

前言

这是一篇暴力乱搞题解，我不保证它在任何时候都能通过本题（事实上现在就不能了），但这并不意味着你无法从这篇题解中学到一些有用的东西，请在知悉这些的前提下往后阅读。

正文

首先有一个众所周知显而易见的结论：如果 k=2 的话答案就是所有数异或起来。

我们可以类比这个推广到对任意 k 的结论，也就是把 a 转化为 k 进制数做不进位加法，答案就是最终得到的数。

据此可以写出代码：

int n,k; u64 SPRB[64],x,ans;
while(n--) {
    x=read_ull(); int now(0);
    while(x) { SPRB[now++]+=x%k; x/=k; }
} for(int i=0;i!=64;++i) SPRB[i]%=k;
for(int i=63;~i;--i) ans=ans*k+SPRB[i];

显然这个做法的复杂度是 O(n\log A) 的，A 为值域，看上去无法通过此题，于是我们选择思考正解开始乱搞。

真正的正文

我们看到这段代码充斥着取模和除法运算，并且除数固定。

众所周知取模和除法特别慢，我们考虑优化掉它们。

这里介绍一下 Barrett Reduction 算法：

假设 b 为字长，对于一个除数 M(2\le M<2^b)，令 s=\left\lfloor\log_2(M-1)\right\rfloor，X=\left\lceil\frac{2^{b+s}}{M}\right\rceil，我们有 X<2^b，并且对于任意的 N\in[0,2^{b-1})，有：

\left\lfloor\frac{N}{M}\right\rfloor=\left\lfloor\frac{NX}{2^{b+s}}\right\rfloor

这意味着我们将一次除法运算转化为了一次乘法运算和一次按位右移运算，而众所周知

N\bmod{M}=N-M\cdot\left\lfloor\frac{N}{M}\right\rfloor

于是取模也被优化到了两次乘法、一次按位右移、一次减法。

使用这个技巧优化一下上面进制转换的部分就可以通过考试时的数据了。

证明

这里搬运了 Min_25 给出的证明，原文在此（全日文警告）。

又由于： $$ 2^s<M\le2^{s+1}\Rightarrow2^s\le M-1<2^{s+1} $$ 我们有： $$ X=\frac{2^b2^s+r}{M}\le\frac{2^b(M-1)+r}{M}<\frac{2^bM}{M}=2^b $$ 由此 $X<2^b$ 得证。 接下来我们考虑证明下面这个式子： $$ 0\le\frac{NX}{2^{b+s}}-\frac{N}{M}<\frac{1}{M} $$ 可以发现，这个式子得证则原式得证。 首先由 $X$ 的定义我们可以发现大于等于 $0$ 是显然的，接下来我们证明右边的小于。 $$ \left(\frac{NX}{2^{b+s}}-\frac{N}{M}\right)-\frac{1}{M}=\left(\frac{N\frac{2^{b+s}+r}{M}}{2^{b+s}}-\frac{N}{M}\right)-\frac{1}{M} $$ $$ =\frac{Nr}{M2^{b+s}}-\frac{1}{M} $$ $$ =\frac{Nr-2^{b+s}}{M2^{b+s}} $$ 又因为： $$ Nr<NM<2^{b+s}(M\le2^{s+1},N<2^{b-1}) $$ 原式得证。 --- # 最后 是否提交这篇题解我是斟酌过的，毕竟它已经无法通过这道题了。但是最后我还是决定提交，因为我认为对一道题目的研究不应该仅仅是通过这道题，更重要的是从这道题中学到些什么。如果你认为你从这篇题解里学到了东西，欢迎点赞让更多的人看见它。