ACM - ICPC Regionals 2014 Bangkok 亚洲区域赛 国外某数学题
ACM-ICPC Live Archive Regionals 2014 >> Asia - Bangkok
6844 - Combination
=====
艰辛坎坷的探索历程
设 $ {f(n)=C_{n}^{r}(n∈N^{ * },r∈[0,n])} $中奇数的个数。
题意是说，求出 $ \sum f(k),k∈[low,high] $
庞大的数据， $ n≤16\times{10^{11}}. $
step1
判断给定 $ n∈N^{ * } $时 $ C_n^r(r∈[0,n]) $的奇偶性。 不难往n,r的二进制表示方向考虑。
查阅他人博客获得结论： $ n{ & }r==r $时 $ C_n^r $为奇数。 然而本题中无需直接应用这一“定理”，所要做的是统计。
拿出纸笔推算发现，若n的二进制表示中有d个1，则 $ C_n^r(r∈[0,n]) $中存在 $ 2^d $个奇数。
step2
研究 $ f(n) $ 的递推关系及通项。 编写暴力程序 $ O(n^2) $ ，打表观察 $ n∈[0,64) $ 时 $ f(n) $ 的取值：
1
2
2 4
2 4 4 8
2 4 4 8 4 8 8 16
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 4 8 8 16 8 16 16 32 8 16 16 32 16 32 32 64
第一行 $ f(0)=1 $ 作为边界条件， 第二行 $ f(1)=2 $ ，随后各行的第k行的 $ 2^{k-2} $ 个数分别表示 $ f(2^{k-2}),f(2^{k-2}+1),…,f(2^{k-1}-1) $ 。
通过不懈的努力，观察发现从第3行开始，每行的前半部分与前一行完全一致，每行的后半部分的各个f值恰为前半部分对应位置的f值的2倍。
step3
出于数列直觉，我们尝试求解各行的和构成的数列的递推以及通项。
$ a_1=1 $
$ a_2=2 $
$ a_3=a_2+2\times{a_2}=3\times{a_2}=6 $
…
$ a_n=a_{n-1}+2\times{a_{n-1}}=3\times{a_{n-1}}(n\geq 3) $（递推公式）
通项公式:
$$
\begin{equation} a_n= \begin{cases} 1 &\mbox{$n=1$}\newline 2 &\mbox{$n=2$}\newline 2\times3^{n-2} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$
$$
\begin{equation} S_n=\sum\limits_{i=1}^{n} {a_i}= \begin{cases} 1 &\mbox{$n=1$}\newline 3 &\mbox{$n=2$}\newline 3+6\times\frac{1-3^{n-2}}{1-3}=3+3\times{(3^{n-2}-1)}=3^{n-1} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$
$$
S_n=3^{n-1}（a_n的前n项和的公式）
$$
化简后上面这个公式样子够好看了吧？
step4
再看一下第2步发现的规律，应用“二分”手段高效地求解，而且真的可以二分求解。
具体地说，就是先置求解区间 $ [l,r) $ (左闭右开)的端点于每行的头尾( $ l=2^{i-2},r=2^{i-1} $ )，利用上一步所得公式计算该区间的 $ 左端点前缀和U=\sum\limits_{k=1}^{2^{i-2}} {f(k)} $ 与 $ 右端点前缀和V=\sum\limits_{k=1}^{2^{i-1}-1} {f(k)} $ 后，不断地对区间折半，总可以确定新区间的左端点前缀和与右端点前缀和。
当区间缩至一点时， $ U==V==f(k) $，即能得到我们所求，而无需计算出[1..n]的每个函数值。
step5
以上所解决的并不是最终答案，而是前缀和 $ \sum\limits_{k=1}^{n} {f(k)} $ ；
不过走到这一步已经很好办了， $ ans=\sum\limits_{k=low}^{high} {f(k)}=\sum\limits_{k=1}^{high} {f(k)}-\sum\limits_{k=1}^{low-1} {f(k)} $
PS:写完代码后，用极大的n值测试一下，事实上 $ \sum\limits_{k=1}^{n} {f(k)} $已经超出了int64的范围。其他的细节不必多说了。
1.319s AC java代码：
1 | /** |
0.279s AC cpp代码：
1 |
|
ACM - ICPC Regionals 2014 Bangkok 亚洲区域赛 国外某数学题