hdu6304如何运用打表公式解题？

本文共计1340个文字，预计阅读时间需要6分钟。

探讨了许久。这个题目可以先将an提出来。观察到从1到n的出现次数，去掉1后，出现次数呈二进制形式。求和即可。

推了好久。。。

这个题肯定是先把an打出来。。1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9

发现从小到大出现，而且除了1，出现次数为二进制形式最低位的位数。。

然后是求和。。既然和二进制有关，优先考虑n=2^k的情况。。发现an都是n/2。。然后就要考虑前n/2怎么推出n了。。

1 2 2 3 4 4 4

5 6 6 7 8 8 8

贴一下 2-8和9-15（因为第一项不符合最低位的规律）可以发现他们都只差了4，由a[n/2]和a[n]的关系可以推出差值为a[n]-a[n/2]=n/4

然后就可以yy公式了。。设s为前缀和。。

s[n]={s[n/2]}+{(s[n/2]-1)+(n/2-1)*(n/4)}+{n/2}

其中第一项为前n/2的和；第二项为n+1~n-1的和，可以在2~n/2的基础上+项数*n/4得到；第三项就是n/4了。。

这样就解决了s[2^k]了。。

然后其他的呢？其实可以先把n表示成二进制。。然后设最高位为m

前2^m可以先算出来，剩下的减去a[2^m]，可以发现会变成从2开始的a序列。。（和算2^k的思想类似）然后补上一个1就变成了另一个s。。

这样按位减可以依次得到答案了。。