hihocoder1286 : 子矩阵求和

http://hihocoder.com/problemset/problem/1286

题解

NB分析题。

首先我们令(s[i][j])表示以((i,j))为左上角的矩形的权值和。

因为(a[i][j]+1=a[i+1][j+1])。

所以(s[i][j]+n*m=s[i+1][j+1])。

再有当(igeq m)时(s[i][1]=s[i+1][1])。

(jgeq n)时(s[1][i]=s[1][i+1])。

那么我们若知道一个((i,j))值，那么所有的((i+x,j+x))中最小的合法解可以通过解同余方程求出。

根据发现的性质，只需要枚举(n+m)个((i，j))即可。

代码

#include<bits/stdc++.h>
#define N 200009
using namespace std;
typedef long long ll;
ll n,m,k;
ll dp[N];
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
struct node{
	int x,y;
	inline bool operator <(const node &b)const{
		if(x+y!=b.x+b.y)return x+y<b.x+b.y;
		return x<b.x;
	}
}ans;
inline ll Sum(ll n){return n*(n+1)/2;}
inline ll sum(ll n,ll m){
	if(!n||!m)return 0;
	if(n>m)swap(n,m);
    return dp[n]*2-Sum(n)+(m-n)*Sum(n);
}
inline ll calc(ll x,ll y,ll n,ll m){
   return sum(x+n-1,y+m-1)-sum(x-1,y+m-1)-sum(x+n-1,y-1)+sum(x-1,y-1);
}
inline void prework(ll n){
	for(int i=1;i<=n;++i)dp[i]=dp[i-1]+1ll*i*(i+1)/2;
}
ll xx,yy,g;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void exgcd(ll a,ll b){
	if(!b){
      xx=1;yy=0;
      return;
	}
	exgcd(b,a%b);
    ll k=xx;
    xx=yy;
    yy=k-(a/b)*yy;
}
inline int solve(ll x,ll y,ll k){
	x%=k;y%=k;
	x=k-x;
	if(x%g)return -1;
    ll o=(xx*(x/g)%(k/g)+(k/g))%(k/g);
    return o;
}
int main(){
    int Q=rd();
    prework(200000);
    while(Q--){
    	n=rd();m=rd();k=rd();
    	g=gcd(1ll*n*m%k,k);
    	exgcd(1ll*n*m%k,k);/
    	bool tag=0;
    	int aa=1e9;
    	ans=node{aa,aa};
    	for(int i=1;i<=n;++i){
    		int x=solve(calc(1,i,n,m),1ll*n*m,k);
            if(x!=-1){
            	tag=1;
            	node du=node{1+x,i+x};
            	if(du<ans)ans=du;
            }
    	}
    	for(int i=1;i<=m;++i){
    		int x=solve(calc(i,1,n,m),1ll*n*m,k);
    		if(x!=-1){
    			tag=1;
    			node du=node{i+x,1+x};
            	if(du<ans)ans=du;;
    		}
    	}
    	if(tag){
          printf("%d %d
",ans.x,ans.y);
    	}
    	else puts("-1");
    }
    return 0;
}