题意:给定一个n,求 sigma(i^(n-i)).

思路:全部的公式推导 http://blog.csdn.net/knight_kaka/article/details/38403973

首先这个题目,我感觉特别的神奇,这种递推公式是怎么发现的呢?我找到了叉姐,询问了出题的过程,他说是偶尔在OEIS中看到的。

推导的过程中,有一些地方是没有公式直接推导过来的,而是充分利用了异或的特点。

比如在n=2k + 1,(2*i)^(n – 2*i)这一步的转化。

(2i)^ (2k+1-2i),在这个方程中,2i相当于 i左移一位,最后一位一定是0。2k+1-2i则是k-i 左移一位 + 1 也就是最后一位多了1

化简的时候。就是  2*(i ^(k-i)) + 1。先异或再左移再加一。结果是相同的。

 

 

HDU 4790 Just Random(容斥 + 数学推导 + 规律)

题意:从[a,b]内选一个数x,从[c,d]内选一个数y,问有多少对(x+y)%p = m。 思路:因为第一个区间和第二个区间是不同的。所以让他尽量相同,可以利用容斥原理...

阅读全文

HDU 5407 CRB and Candies(数学公式,组合数的最小公倍数)

题意:给你一个n,求lcm(C(n,0),C(n,1),….C(n,n))。 思路:直接 OEIS 搜的公式,证明可以看这里http://arxiv.org/pdf/0906.2295v2.pdf lc...

阅读全文

HDU 4814 Golden Radio Base(数学模拟题)

题意:把一个十进制转化为黄金进制。 思路:这题虽然很水,但是一开始题意就很难读,并且也不知道给的俩公式是干啥用的。。看了题解之后才发现自己对进制的理...

阅读全文

欢迎留言

*