一道奇妙的题=。=(161031)

=。=结果今天心血来潮来只有雪舞喵会来的网站上看看,突然想到了昨天一道奇妙的题,于是就来写上一写我的心路历程。

试题名叫or,题面大概是这样的,输入一个n,求f(n)对1e9+7取模的值。其中f(n)定义如下

\[f(n)=\sum_{i=0}^n\sum_{j=i}^nbit(i|j)\]

其中|代表二进制或,bit表示二进制表示中1的个数。 \((n \le 2^{1000000})\) 并且n以二进制形式给出。

(其实雪舞喵总觉得这题在哪见过)正解是数位dp,看起来很麻烦的样子,于是在模拟中雪舞喵花了两个小时打表找规律+推奇妙的公式,搞了一个O(logn)时间O(1)空间复杂度的辣鸡公式。

首先因为个人感觉上面那个公式看着很难受,于是就尝试把公式变个形什么的,首先

\[f(x)-f(x-1)=\sum_{i=0}^x\sum_{j=i}^xbit(i|j)-\sum_{i=0}^{x-1}\sum_{j=i}^{x-1}bit(i|j)=\sum_{i=0}^xbit(i|x)\]

得到了这样一个东西。然后呢由于这道题的复杂度显然是logn的,这个O(n)的递推式并没有什么卵用。所以就把他递推转通项一下,得到

\[f(x)=\sum_{i=1}^x\sum_{j=0}^ibit(i|j)\]

不知道为什么这个式子看起来顺眼多了,然而这还是并没有什么卵用,因为接下来要推的东西用前面那个公式也能推。然而根据雪舞喵个人的喜好还是决定用下面这个公式推。

由于复杂度显然是logn的,雪舞喵一想,如果知道f(x)能在O(1)的时间内推出f(2x)和f(2x+1)事情不就解决了喵。于是雪舞喵尝试推了一推,首先按照公式模拟一下循环,以3作为样例,把每一次循环的二进制形式都写下来。像这样

第一层循环: 第二层循环 - 对答案的贡献
1: 0 1 - 2
10: 0 1 10 - 4
11: 0 1 10 11 - 8

雪舞喵看了一下,如果在以上的每一项循环的后面都加个0,那么对答案的贡献并不会改变。于是雪舞喵从这个角度继续想,如果在每一项后面加个1呢,发现对答案的贡献增加了一个等差数列的和,数值上增加了 \(\frac{x(x+3)}{2}\)

接下来需要考虑的就是在第一层循环和第二层循环后面加的数字不一样的问题,首先很简单的是在第一层循环的数字后加1并在第二层数字后加0答案和都加1是相等的,然而在第一层加0第二层加1却出现了问题,因为有j<=i的限制,每一层的最后一个数字不能被计算在内,大概变成这样

第一层循环: 第二层循环 - 对答案的贡献
10: 1 (11) - 1
100: 1 11 (101) - 3
110: 1 11 101 (111) - 7

其中括号包含的数字不能被计算在内。首先重新计算一下等差数列,发现和变成了 \(\frac{x(x+1)}{2}\) ,接下来还额外减少了 \(\sum_{i=1}^xbit(i|i)=\sum_{i=1}^xbit(i)\) 。没关系,只要定义 \(s(x)=\sum_{i=1}^xbit(i)\) 这样就解决了。

除了刚才那四部分,最后还会多出一个1:0 1的循环,这个对答案的贡献是常数2,加上即可。于是终于得到了第一个递推式

\[f(2x+1)=4f(x)+x(x+3)+\frac{x(x+1)}{2}-s(x)+2\]

接下来考虑一下f(2x),发现只是f(2x+1)中少了这么一层循环

第一层循环: 第二层循环 - 对答案的贡献
111: 0 1 10 11 100 101 110 111 - 24

因此定义 \(b(x)=\sum_{i=0}^xbit(i|x)\) 之后就可以表示f(2x)啦

\[f(2x)=f(2x+1)-b(2x+1)\]

好啦,这样雪舞喵只要能在O(logn)的时间内递推s(x)和b(x)就能解决问题啦。对于这两个函数雪舞喵仿照刚才模拟在后面+0+1的方法很快得到了递推式

\[b(2x+1)=2b(x)+2x+2\]

\[b(2x)=b(2x+1)-bit(x)-1\]

\[s(2x+1)=2s(x)+x+1\]

\[s(2x)=s(2x+1)-bit(x)-1\]

显然 \(bit(2x)=bit(x),bit(2x+1)=bit(x)+1\)

然后就做完了喵,代码比标程短好多=。=

然而雪舞喵推这个公式推了好长好长时间导致T2时间不够了随手写了个暴力(由于数据水暴力居然得了60分)

附上一份代码

2016.10.31

Yukimai

(^=。=^)

发表评论