Hdu5226 Tom and matrix
2024-10-16 19:06:44
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=Cji
ai,j=Cji
if i < j, ai,j=0
Tom 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
1 1 2 2 13
1 0 2 1 2
Sample Output
3
4
1
4
1
Source
Recommend
题目大意:若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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; typedef long long ll; ll x3, y3, x4, y4, p, ans;
ll sum[], ni[], nijie[]; ll qpow(ll a, ll b)
{
ll res = ;
while (b)
{
if (b & )
res = (res * a) % p;
a = (a * a) % p;
b >>= ;
}
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 ;
return qpow(sum[b], p - ) * qpow(sum[a - b], p - ) % p * sum[a] % p;
} ll C(ll a, ll b)
{
if (a < b)
return ;
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[] = ;
ni[] = ;
sum[] = ;
nijie[] = ;
nijie[] = ;
for (ll i = ; i <= min(x4 + , p); i++)
{
sum[i] = (sum[i - ] * i) % p;
ni[i] = (p - p / i) * ni[p % i] % p;
nijie[i] = (nijie[i - ] * ni[i]) % p;
}
ans = ;
for (ll i = y3; i <= y4; i++)
{
ans += C(x4 + , i + );
ans %= p;
}
for (ll i = y3; i <= y4; i++)
{
ans = (ans - C(x3, i + ) + p) % p;
ans %= p;
}
printf("%lld\n", (ans + p) % p);
} return ;
}
最新文章
- 2014优秀的好用的20款免费jQuery插件推荐
- Couchbase 介绍 - 更好的 Cache 系统
- autocapticalize和autocorrect
- java 引用资源-ClassLoader.getResource()方法
- python模块介绍- multi-mechanize 性能测试工具
- 【百度地图API】小学生找哥哥——小学生没钱打车,所以此为公交查询功能
- A comparison of local caches (2) 【本地缓存之比较 (2)】
- [SQL]LeetCode262.行程和用户 | Trips and Users
- 【从零开始自制CPU之学习篇07】最简单的ALU—全加器
- Windows10 引导修复
- Docker 学习笔记(持久化数据的备份,还原)
- 给出一百分制成绩,要求输出成绩等级’A’、’B’、’C’、’D’、’E’。
- jQuery相关用法
- vmware 里MAC 鼠标能移动 无法单击
- Zookeeper3.4.10 + ActiveMQ-5.15.0 集群搭建
- python摸爬滚打之day09----初识函数
- CentOS6.x 下安装Python pyyaml模块
- javascript: Math.sin() cos() 用法
- Sql Server 2008 清除日志
- 修改MySQL的默认密码的四种小方法