题目描述

Given a matrix of size n\times mn×m and an integer {k}k, where A_{i,j} = lcm(i, j)A i,j=lcm(i,j), the least common multiple of {i}i and {j}j. You should determine the sum of the maximums among all k\times kk×k submatrices.

输入

Only one line containing three integers n,m,k~(1\leq n,m \leq 5000, 1 \leq k \leq \min{n, m})n,m,k (1≤n,m≤5000,1≤k≤min{n,m}).

输出

Only one line containing one integer, denoting the answer.

样例输入

3 4 2

样例输出

38

题目大意

给定一个矩阵A(n,m)，每个元素的值为该元素横纵坐标的最小公倍数，求该矩阵中每个k*k的矩阵中的最大值的和。

分析

这题数据大小看着就不太对果断放弃暴力，但又非求出整个A矩阵不可（若k=1呢？），所以采用一种类似于素数筛（互质筛？）的方法求出：

for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++){if(!a[i][j]){for(int k=1;k*i<=n&&k*j<=m;k++) a[k*i][k*j]=i*j*k;}}
}

不难证明：若lcm(x,y)=z，则lcm(kx,ky)=kz
然后对每行进行单调队列+滑动窗口维护每个k区间内的最大值并存在b数组中，接着对每列进行单调队列+滑动窗口即可求出每个k*k矩阵的最大值。

代码

#include<bits/stdc++.h>using namespace std;int a[5005][5005],b[5005][5005];
deque<int>q;int main()
{int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!a[i][j]) for(int k=1;k*i<=n&&k*j<=m;k++) a[k*i][k*j]=i*j*k;for(int i=1;i<=n;i++){while(!q.empty()) q.pop_back();q.push_back(0);for(int j=1;j<k;j++){while(q.size()&&a[i][q.front()]<=a[i][j]) q.pop_back();q.push_back(j);}for(int j=k;j<=m;j++){while(q.size()&&q.front()<=j-k) q.pop_front();while(q.size()&&a[i][q.back()]<=a[i][j]) q.pop_back();q.push_back(j);b[i][j]=max(b[i][j],a[i][q.front()]);}}long long ans=0;for(int j=k;j<=m;j++){while(!q.empty()) q.pop_back();q.push_back(0);for(int i=1;i<k;i++){while(q.size()&&b[q.front()][j]<=b[i][j]) q.pop_back();q.push_back(i);}for(int i=k;i<=n;i++){while(q.size()&&q.front()<=i-k) q.pop_front();while(q.size()&&b[q.back()][j]<=b[i][j]) q.pop_back();q.push_back(i);ans+=b[q.front()][j];}}printf("%lld",ans);
}

-----原创文章，仅供参考