HackerRank Algebra – Cross Matrix

Challenge: Cross Matrix

Subdomeniu: Algebra (algebra)

Scor cont: 120.0 / 120

Submission status: Accepted

Submission score: 1.0

Submission ID: 464834972

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/cross-matrix/problem

Cerință

Cod sursă

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

// Cross Matrix - HackerRank
// Count ordered pairs of overlapping all-ones submatrices such that neither contains the other.

static const int MOD = 1000000007;
static inline int addmod(int a,int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
static inline int submod(int a,int b){ a-=b; if(a<0) a+=MOD; return a; }

static vector<int> genUBound(const vector<string>& mat){
    int n = (int)mat.size();
    vector<int> ub(n*n, 0);
    for(int i=0;i<n;i++){
        int rowOff = i*n;
        int prevOff = (i-1)*n;
        for(int j=0;j<n;j++){
            if(mat[i][j]=='1'){
                ub[rowOff + j] = (i==0 ? 1 : ub[prevOff + j] + 1);
            }
        }
    }
    return ub;
}

static void reverseEachRow(vector<int>& a, int n){
    for(int i=0;i<n;i++){
        auto it = a.begin() + i*n;
        reverse(it, it + n);
    }
}

static vector<int> genCounter(const vector<int>& ub, int n){
    vector<int> counter(n*n, 0);
    vector<int> left(n), st(n);

    for(int i=0;i<n;i++){
        int end = -1;
        int base = i*n;
        for(int j=0;j<n;j++){
            int h = ub[base + j];
            left[j] = j;
            while(end >= 0 && h <= ub[base + st[end]]){
                left[j] = left[st[end]];
                end--;
            }
            if(end==-1 || h != ub[base + st[end]]) st[++end] = j;

            long long val = 1LL*(j - left[j] + 1) * h;
            if(left[j] > 0) val += counter[base + left[j] - 1];
            counter[base + j] = (int)(val % MOD);
        }
    }
    return counter;
}

static vector<int> genSum(vector<int> counter, int n){
    for(int i=0;i<n;i++){
        int base = i*n;
        for(int j=1;j<n;j++){
            counter[base + j] = addmod(counter[base + j], counter[base + j - 1]);
        }
    }
    for(int i=1;i<n;i++){
        int base = i*n;
        int prev = (i-1)*n;
        for(int j=0;j<n;j++){
            counter[base + j] = addmod(counter[base + j], counter[prev + j]);
        }
    }
    return counter;
}

static long long comb3(long long t){
    if(t < 3) return 0;
    __int128 v = (__int128)t * (t-1) * (t-2);
    v /= 6;
    return (long long)(v % MOD);
}
static long long comb4(long long t){
    if(t < 4) return 0;
    __int128 v = (__int128)t * (t-1) * (t-2) * (t-3);
    v /= 24;
    return (long long)(v % MOD);
}

static int containPairs(const vector<int>& ub, int n){
    int H = n, W = n;
    vector<int> diff((H+1)*(W+1), 0); // can be negative

    vector<int> left(W+1), st(W+1);

    for(int i=0;i<n;i++){
        int end = -1;
        int base = i*n;
        for(int j=0;j<=n;j++){
            int cHeight = (j==n ? 0 : ub[base + j]);
            left[j] = j;

            while(end >= 0 && cHeight < ub[base + st[end]]){
                int height = ub[base + st[end]];
                left[j] = left[st[end]];
                int width = j - left[st[end]];
                end--;
                int mHeight = (end >= 0) ? max(cHeight, ub[base + st[end]]) : cHeight;

                diff[height*(W+1) + width] += 1;
                diff[mHeight*(W+1) + width] -= 1;
            }
            if(end == -1 || cHeight > ub[base + st[end]]){
                st[++end] = j;
            }
        }
    }

    int maxDim = n + 5;
    vector<long long> cm3(maxDim+1, 0), cm4(maxDim+1, 0);
    for(int i=0;i<=maxDim;i++){
        cm3[i] = comb3(i);
        cm4[i] = comb4(i);
    }

    long long total = 0;
    for(int h=1; h<=H; h++){
        for(int w=1; w<=W; w++){
            int v = diff[h*(W+1) + w];
            if(v==0) continue;
            long long term = cm3[h+2] * cm4[w+3] % MOD;
            total = (total + term * (long long)v) % MOD;
        }
    }
    if(total < 0) total += MOD;
    return (int)total;
}

static int solveCrossMatrix(vector<string> mat){
    int n = (int)mat.size();
    const int inv2 = (MOD + 1) / 2;

    // original
    vector<int> ub = genUBound(mat);
    vector<int> counter = genCounter(ub, n);
    int contain = containPairs(ub, n);

    // mirrored (to count bottom-left)
    reverseEachRow(ub, n);
    vector<int> counterRev = genCounter(ub, n);

    // vertical flip for top-corner related counting
    reverse(mat.begin(), mat.end());
    vector<int> ubRev = genUBound(mat);
    vector<int> sumRev = genSum(genCounter(ubRev, n), n);

    // also horizontal flip => rotation 180 => top-left related
    reverseEachRow(ubRev, n);
    vector<int> sum = genSum(genCounter(ubRev, n), n);

    int total = sum[n*n - 1]; // total #submatrices of ones (mod)

    contain = submod(contain, total); // remove (R,R)

    long long deviation = 0;

    // count disjoint unordered pairs (with diagonal double-count)
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int down = (n - i - 2 >= 0) ? sum[(n - i - 2)*n + (n - 1)] : 0;
            int right = (n - j - 2 >= 0) ? sum[(n - 1)*n + (n - j - 2)] : 0;
            int rightDown = (n - i - 2 >= 0 && n - j - 2 >= 0) ? sum[(n - i - 2)*n + (n - j - 2)] : 0;

            int other = right;
            other = addmod(other, down);
            other = submod(other, rightDown);

            deviation = (deviation + 1LL * counter[i*n + j] * other) % MOD;
        }
    }

    // subtract diagonal cases counted twice
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int c = counterRev[i*n + j];
            if(c==0) continue;
            if(n - i - 2 < 0 || n - j - 2 < 0) continue;
            int leftUp = sumRev[(n - i - 2)*n + (n - j - 2)];
            deviation = (deviation - 1LL * c * leftUp) % MOD;
        }
    }
    if(deviation < 0) deviation += MOD;

    long long res = 1LL * total * (total - 1) % MOD * inv2 % MOD; // unordered pairs
    res = (res - contain - deviation) % MOD;
    if(res < 0) res += MOD;

    res = res * 2 % MOD; // ordered
    return (int)res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> mat(n);
    for(int i=0;i<n;i++) cin >> mat[i];

    cout << solveCrossMatrix(mat) << "\n";
    return 0;
}