题解 | 矩形计数

#include <iostream>
#include <vector>
using namespace std;
constexpr long long mod=1e9+7;

long long qpow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n,m;
   cin>>n>>m;
   vector<vector<bool>> arr(n,vector<bool>(m));
   long long res=0;
   for(int i=0;i<n;i++){
    long long zero=0,one=0;
    for(int j=0;j<m;j++){
        int t;
        cin>>t;
        if(t==0){arr[i][j]=false;zero++;}
        else {arr[i][j]=true;one++;}
    }
    res+=(qpow(2,zero,mod)-1+mod)%mod;
    res+=(qpow(2,one,mod)-1+mod)%mod;
   }
   for(int c=0;c<m;c++){
    long long zero=0,one=0;
    for(int r=0;r<n;r++){
        if(arr[r][c]==false){zero++;}
        else{one++;}
    }
    res+=(qpow(2,zero,mod)-1+mod)%mod;
    res+=(qpow(2,one,mod)-1+mod)%mod;
   }
   res = (res - (long long)n * m % mod + mod) % mod;
   cout<<res;
   return 0;
}