题意:从[a,b]内选一个数x,从[c,d]内选一个数y,问有多少对(x+y)%p = m。

思路:因为第一个区间和第二个区间是不同的。所以让他尽量相同,可以利用容斥原理,变成这样:

[a,b]+[c,d] (从这两个区间内选出满足题意的对数) = ([0,b] + [0,d]) – ([0,a]+ [0,d-1]) – ([0,c] + [0, b-1]) + ([0, a]+[0,c])

所以现在问题到了再[0,a]+[0,b] 这个区间内有多少对数 (x+y)%p =m.转化为 x + y = kp + m

经过一顿乱搞。 竟然发现了规律。。

假设 a>b. 那么当kp+m <= b 的时候 从第一项m开始是一个单调增的等差数列,且对于每一项 含有 kp+m+1对x,y。

当 b<=kp+m<=a的时候。是一个恒定值。

在kp+m>a的时候是一个单调减的等差数列。 然后就是看有多少项推公式就可以了。

 

HDU 4919 Exclusive or(推公式+记忆化)

题意:给定一个n,求 sigma(i^(n-i)). 思路:全部的公式推导 http://blog.csdn.net/knight_kaka/article/details/38403973 首先这个题目,我感觉特别的神奇...

阅读全文

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(数学模拟题)

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

阅读全文

欢迎留言

*