首页 > 代码库 > 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(思维)