首页 > 代码库 > ZOJ 3955：Saddle Point（思维）
ZOJ 3955：Saddle Point（思维）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3955
题意：给出一个n*m的矩阵，定义矩阵中的特殊点Aij当且仅当Aij是这一行最小的唯一元素，是这一列最大的唯一元素。删除一些行和列，剩下的元素构成的矩阵一共有（2^n-1）* （2^m-1）种，求这些矩阵的特殊点的个数。
思路：对于这种问题，可以考虑每一个点对答案的贡献。
其实就只是对于每一个点，找出在该行大于它的点的数目a，在该列大于它的点的数目b，然后该点对于答案的贡献就是2^a * 2^b，用快速幂处理一下。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 1010 4 const int MOD = 1e9 + 7; 5 typedef long long LL; 6 LL mp[N][N], se[N], col[N][N], row[N][N]; 7 LL f_pow(LL a, LL b) { 8 LL ans = 1; 9 while(b) {10 if(b & 1) ans = (ans % MOD * a) % MOD;11 a = a * a % MOD;12 b >>= 1;13 }14 return ans % MOD;15 }16 int main() {17 int t; scanf("%d", &t);18 while(t--) {19 int n, m; scanf("%d%d", &n, &m);20 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%lld", &mp[i][j]);21 for(int i = 1; i <= n; i++) {22 for(int j = 1; j <= m; j++) se[j] = mp[i][j];23 sort(se + 1, se + m + 1);24 for(int j = 1; j <= m; j++) row[i][j] = m - (upper_bound(se + 1, se + 1 + m, mp[i][j]) - se) + 1;25 }26 for(int i = 1; i <= m; i++) {27 for(int j = 1; j <= n; j++) se[j] = -mp[j][i];28 sort(se + 1, se + n + 1);29 for(int j = 1; j <= n; j++) col[j][i] = n - (upper_bound(se + 1, se + 1 + n, -mp[j][i]) - se) + 1;30 }31 LL res = 0;32 for(int i = 1; i <= n; i++) {33 for(int j = 1; j <= m; j++) {34 // printf("%d - %d : %lld - %lld\n", i, j, row[i][j], col[i][j]);35 res = (res % MOD + f_pow(2LL, row[i][j]) * f_pow(2LL, col[i][j]) % MOD) % MOD;36 }37 }38 printf("%lld\n", res % MOD);39 }40 return 0;41 }
ZOJ 3955：Saddle Point（思维）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。