この問題の愚直な解法として、すべての \((i,j)\) の組を探索してそれぞれの組に対し \(A_{i,k}=A_{j,k}\) を満たす\(k (1 \leq k \leq M)\) の個数を求めてそれが奇数である場合は答えに加算するというのがあります。しかし、これは計算量が \(O(N^2M)\) となり、実装方法によってはこの問題では実行時間制限に間に合いません。

この問題では、bitset高速化というテクニックを利用することで定数倍に \(\frac{1}{64}\) がつき、\(\frac{2000^{3}}{64} = 125000000 \simeq 10^{8}\) であるため十分高速になります。

具体的には、\(B_{i,j}\) を \(A_{i,k}=A_{j,k}\) となる \(k\) の個数の偶奇と定義すると、\(B_1,B_2,\ldots,B_N\) をそれぞれbitsetにすることができます。実際に計算する際は\(k\) を \(1\) から \(M\) まで、それぞれの \(k\) について \(A_{i,k}\) の値ごとにまとめて、bitsetのxorなどを適切に用いることで実装出来ます。

詳しくは実装例を参考にしてください。

実装例(C++):

#include<bits/stdc++.h>
using namespace std;

static constexpr size_t maxN=2000;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    vector<vector<int>>a(n,vector<int>(m));
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin>>a[i][j];
        }
    }
    
    vector<bitset<maxN>>bt(n);
    vector<bitset<maxN>>bs(1000);
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            bs[a[j][i]].set(j);
        }
        for(int j=0;j<n;++j){
            bt[j]^=bs[a[j][i]];
        }
        for(int j=0;j<n;++j){
            bs[a[j][i]].reset(j);
        }
    }

    int ans=0;
    for(int i=0;i<n;++i)ans+=bt[i].count();
    if(m&1)ans-=n;
    cout<<ans/2<<endl;
}