Hdu5226 Tom and matrix

Hdu5226 Tom and matrix

Tom and matrix Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 867    Accepted Submission(s): 284 Problem Description Tom was on the way home from school. He saw a matrix in the sky. He found that if we numbered rows and columns of the matrix from 0, then,ai,j=Cjiif i < j, ai,j=0Tom suddenly had an idea. He wanted to know the sum of the numbers in some rectangles. Tom needed to go home quickly, so he wouldn't solve this problem by himself. Now he wants you to help him.Because the number may be very large, output the answer to the problem modulo a prime p.     Input Multi test cases(about 8). Each case occupies only one line, contains five integers, x1、y1、x2、y2、p.x1≤x2≤105,y1≤y2≤105,2≤p≤109.You should calculate ∑x2i=x1∑y2j=y1ai,j mod p     Output For each case, print one line, the answer to the problem modulo p.     Sample Input 0 0 1 1 7 1 1 2 2 13 1 0 2 1 2     Sample Output 3 4 1     Source BestCoder Round #40     Recommend hujie   |   We have carefully selected several similar problems for you:  6242 6241 6240 6239 6238  题目大意：若i ≥ j,那么a[i][j] = C(i,j),否则a[i][j] = 0,给一个子矩阵(x1,y1,x2,y2),问矩阵和. 分析：ans = sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1). sum(x,y)表示(0,0,x,y)矩阵的和.           怎么计算sum呢？画一个图可以发现对答案有贡献的区域是一个三角形，非常像是杨辉三角，结合Hdu3037的方法，可以把每一列的答案变成1个组合数.接下来就是组合数的计算问题了.可以预处理出阶乘和逆元的阶乘，直接取模运算.但是p是会变的，如果p特别小的话，答案就会出现0，事实上并不是0，因为n!,m!,(n-m)!都有p这个因子，但是p是可以被约分掉的，直接用逆元乘的话是保留了这个p的，所以会WA.           当p比较小的时候,划定一个界限：C(n,m) % p,p ≤ n,如果用lucas定理就能解决这一问题.当p比较大的时候，直接算就可以了. 坑点：下标是从0开始的. 经验教训：当模数p小于n/m，且p为质数时，用lucas定理就能有效避免包含p这个因子而出现的问题. #include #include #include #include using namespace std; typedef long long ll; ll x3, y3, x4, y4, p, ans; ll sum[100010], ni[100010], nijie[100010]; ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % p; a = (a * a) % p; b >>= 1; } return res; } ll solve2(ll a, ll b) { ll temp1 = sum[a]; ll temp2 = nijie[b] * nijie[a - b] % p; return temp1 * temp2 % p; } ll solve(ll a, ll b) { if (b > a) return 0; return qpow(sum[b], p - 2) * qpow(sum[a - b], p - 2) % p * sum[a] % p; } ll C(ll a, ll b) { if (a < b) return 0; if (a >= p) return solve(a % p, b % p) * C(a / p, b / p) % p; else return solve2(a, b); } int main() { while (cin >> x3 >> y3 >> x4 >> y4 >> p) { sum[0] = 1; ni[1] = 1; sum[1] = 1; nijie[1] = 1; nijie[0] = 1; for (ll i = 2; i <= min(x4 + 1, p); i++) { sum[i] = (sum[i - 1] * i) % p; ni[i] = (p - p / i) * ni[p % i] % p; nijie[i] = (nijie[i - 1] * ni[i]) % p; } ans = 0; for (ll i = y3; i <= y4; i++) { ans += C(x4 + 1, i + 1); ans %= p; } for (ll i = y3; i <= y4; i++) { ans = (ans - C(x3, i + 1) + p) % p; ans %= p; } printf("%lld\n", (ans + p) % p); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。