hdu5226专题

hdu5226 Tom and matrix 公式,Lucas

题意:给定x1,y1,x2,y2,求和C(i,j),(x1<=i<=x2,y1<=j<=y2),结果%p。 分析:因为\sum_{i=a}^{b}C_{i}^{k}=C_{b+1}^{k+1}-C_{a}^{k+1}∑​i=a​b​​C​i​k​​=C​b+1​k+1​​−C​a​k+1​​ 所以求同一列的数的和可以变成求两个组合数的差。由于p可能很小,当除数为p的倍数时就为0了,直接乘逆元会出