【hiho一下 第146周】子矩阵求和

【题目链接】:http://hihocoder.com/contest/hiho146/problem/1

【题意】

【题解】

设s[i][j]表示左上角的坐标为(i,j)的n*m的矩阵的和;
有s[i][j]=s[i-1][j-1]+n*m;
不信自己看;
而且
对于i>=max(n,m)
s[i][j]=s[i+1][j];
对于j>=max(n,m)
s[i][j]=s[i][j+1];
而每一行从左到右的元素和;
每一列从上刀下的元素的和是有规律的；
就是前x个数是等差,后面全都相等;
然后根据这个
我们只要算出
s[1][1..max(n,m)]
和s[1..max(n,m)][1]
然后算出这2*max(n,m)个对角线上的各个位置作为左上角的矩阵的和就好;
当然不能强算了；
根据
s[i][j]=s[i-1][j-1]+n*m;
我们知道
s[i][j]之后;
相当于要求最小的x
使得
(s[i][j]+x*n*m%k)==0
这里我们可以预处理出最小的使得x*n*m%k==t的x;
记录下每个t对应的x就好;(当然有一些t可能没办法得到);
这样根据s[1][1..max(n,m)]和s[1..max(n,m)][1]算出每个对角线上有没有可能有有符合要求的点;
每次往下走的时候只会改变一行或一列的和;
所以可以做到O(1)算出来;

【Number Of WA】

17

【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
const int K = 1e6+100;

int n,m,k,need[K],px,py;

void pre()
{
    ms(need,-1);
    LL now = 0;int x = 0;
    while (need[now]==-1)
    {
        need[now] = x;
        now = (now+1LL*n*m)%k;
        x++;
    }
}

int get_sum(int idx,int len)
{
    if (len<=idx)
        return  (1LL*(1+len)*len/2)%k;
    else
        return (1LL*(1+idx)*idx/2 + 1LL*(len-idx)*idx)%k;
}

void gengxin(int x,int y)
{
    if (px==-1 && py==-1)
    {
        px = x,py = y;
        return;
    }
    if (x+y<px+py)
    {
        px = x,py = y;
    }
    else
        if (x+y==px+py && x<px)
        {
            px = x,py = y;
        }
}

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while (Q--)
    {
        px=-1,py=-1;
        cin >> n >> m >> k;
        pre();
        //左上角n行m列的矩阵和
        LL sum = 0,tsum;
        rep1(i,1,m)
            sum=(sum+get_sum(i,n))%k;//相当于加上第i列的n行元素
        tsum = sum;
        int ma = max(m,n);
        rep1(nowy,1,ma)
        {
            int t = (k-sum)%k;
            if (need[t]!=-1)
                gengxin(1+need[t],nowy+need[t]);
            sum=(sum-get_sum(nowy,n)+k+get_sum(nowy+m,n))%k;
        }
        sum = tsum;
        rep1(nowx,1,ma)
        {
            int t = (k-sum)%k;
            if (need[t]!=-1)
            {
                int x = nowx+need[t],y = 1+need[t];
                gengxin(x,y);
            }
            sum=(sum-get_sum(nowx,m)+k+get_sum(nowx+n,m))%k;
        }
        if (px==-1)
            cout <<-1<<endl;
        else
            cout <<px <<' '<<py<<endl;
    }
    //printf("
%.2lf sec 
", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}