Ruudukko

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
 
using ll = long long;
 
ll mod = 1000000000 + 7;
// ll mod = 2;
 
struct Index {
    ll value;
    int idx;
};
 
class Sums {
public:
    Sums(ll n_): n(n_) {
        rowsum.resize(n, 0);
        colsum.resize(n, 0);
    }
 
    ll size() const { return n; }
 
    static ll do_mod(ll x) {
        if (x >= mod) x %= mod;
        return x;
    }
 
    ll sum_at(ll row, ll col) { return (rowsum[row] + colsum[col]) % mod; }
    ll sum_at(ll i) { return sum_at(i / n, i % n); }
 
    ll n;
 
    std::vector<ll> rowsum;  // jokaisen rivin summa
    std::vector<ll> colsum;  // jok. kolumnin summa
};
 
struct Array {
public:
    Array(ll n_): n(n_) { array.resize(n * n, 0); }
 
    ll& operator()(ll row, ll col) { return array[row * n + col]; }
    ll& operator[](ll i) { return array[i]; }
    ll operator[](ll i) const { return array[i]; }
 
    ll size() const { return n; }
 
    const ll n;
    std::vector<ll> array;
};
 
Array read_input() {
    ll n;
    std::cin >> n;
    Array array{ n };
 
    for (ll i = 0; i < n * n; ++i) {
        ll v;
        std::cin >> v;
        array[i] = v;
    }
    return array;
}
 
auto create_indices(Array const& array) {
    std::vector<Index> indices;
    const int n2 = array.size() * array.size();
    indices.reserve(n2);
    for (int i = 0; i < n2; ++i) { indices.push_back({ array[i], i }); }
    std::sort(indices.begin(), indices.end(), [](Index a, Index b) { return a.value < b.value; });
    return indices;
}
 
int main() {
    std::cin.sync_with_stdio(false);
 
    auto array = read_input();
    //    Array array(2);
    //    array.array = { 1, 2, 3, 4 };
 
    const auto indices = create_indices(array);
 
    Sums sums(array.size());
 
    ll res      = 0;
    const ll n2 = array.size() * array.size();
    ll i        = 0;
    ll cur_val  = 0;
    while (i < n2) {
        auto tmp_sums = sums;
        while (indices[i].value == cur_val) {
            ll idx = indices[i].idx;
            ll row = idx / array.size();
            ll col = idx % array.size();
 
            res += 1 + sums.rowsum[row] + sums.colsum[col];
            tmp_sums.rowsum[row] += 1 + sums.rowsum[row] + sums.colsum[col];
            tmp_sums.colsum[col] += 1 + sums.colsum[col] + sums.rowsum[row];
            res %= mod;
            tmp_sums.rowsum[row] %= mod;
            tmp_sums.colsum[col] %= mod;
 
            ++i;
            //
        }
        sums    = std::move(tmp_sums);
        cur_val = indices[i].value;
    }
 
    std::cout << res << "\n";
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED