Proficient.
Put your skills to the test.

Problem summary

A table has m rows and n columns and contains 1 through mn in row order. A cell’s weight is the sum on its four diagonal rays, each including the starting cell. Find the sum of every cell’s weight modulo 10¹² + 39.

Constraints

3 ≤ m, n ≤ 5000.

Worked example

An independently prepared example for this explanation.

3 4

520

Solution analysis

1. Count how often a fixed cell contributes to the answer instead of constructing every ray. It contributes to every origin that can see it diagonally. The relation is symmetric, so the number of such occurrences is the number of cells on its own four rays, counting itself four times.
2. With zero-based coordinates (r,c), the four ray lengths excluding the origin are min(r,c), min(r,n−1−c), min(m−1−r,c), and min(m−1−r,n−1−c). Add four for the four occurrences at the origin, then multiply by the cell’s value rn+c+1.
3. For a 3 by 4 table the occurrence counts by row are [6,7,7,6], [6,8,8,6], [6,7,7,6]. Multiplying these by 1 through 12 and adding gives 520. Reduce each accumulated contribution modulo the required modulus.

Why it works

Every occurrence in a weight is a pair consisting of an origin and a cell on one of its diagonal rays. Reversing the diagonal direction is a bijection between origins that include a fixed cell and positions on that cell’s rays. The four min expressions count precisely those positions, with the prescribed four copies of the origin. Summing their contributions therefore equals the sum of all weights.

Watch out. The origin contributes four times. Use 64-bit integers and reduce the running sum; the unreduced grand total need not fit.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
using namespace std;
int main(){
    int rows,columns;
    cin>>rows>>columns;
    const long long mod=1000000000039LL;
    long long answer=0;
    for(int row=0;row<rows;++row){
        for(int column=0;column<columns;++column){
            // Count all origins whose rays contain this cell.
            long long copies=4+min(row,column)+min(row,columns-1-column)+
                min(rows-1-row,column)+min(rows-1-row,columns-1-column);
            long long value=1LL*row*columns+column+1;
            answer=(answer+value*copies)%mod;
        }
    }
    cout<<answer<<'\n';
}