hihoCoder [Offer收割]编程练习赛3 D子矩阵求和

逃离我推掉我的手 2021-12-23 15:25 194阅读 0赞

[子矩阵求和][Link 1]

[http://hihocoder.com/discuss/question/3005][http_hihocoder.com_discuss_question_3005]

声明一下：

n是和x一起的，m是和y一起的

x是横着的，y是纵着的，x往右为正，y往下为正

（非常反常规的定义）

性质好题

看起来无从下手。

两个关键性质：

![1399631-20190616104516765-109657497.png][]

证明挺显然的。画画图

![1399631-20190616104736237-360173894.png][]

同余方程exgcd即可

子矩阵和？

先算出(0,0)的，每次平移，加减一行一列前n或m个，

细节：

1.纵向要循环到n，横向循环到m

2.注意开long long

3.反常规的设定真讨厌

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    // #define int long long 
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    namespace Modulo{
    const int mod=998244353;
    il int ad(int x,int y){
        return x+y>=mod?x+y-mod:x+y;}
    il int sub(int x,int y){
        return ad(x,mod-y);}
    il int mul(int x,int y){
        return (ll)x*y%mod;}
    il void inc(int &x,int y){x=ad(x,y);}
    il void inc2(int &x,int y){x=mul(x,y);}
    il int qm(int x,int y=mod-2){
        int ret=1;while(y){
        if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
    template<class ...Args>il int ad(const int a,const int b,const Args &...args) {
        return ad(ad(a,b),args...);}
    template<class ...Args>il int mul(const int a,const int b,const Args &...args) {
        return mul(mul(a,b),args...);}
    }
    // using namespace Modulo;
    namespace Miracle{
    ll n,m,P;
    ll exgcd(ll a,ll b,ll &x,ll &y){
        if(!b){
            x=1;y=0;return a;
        }
        ll ret=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return ret;
    }
    ll ch(ll x){
        if(m<=x) return m*(m+1)/2;
        return x*(x+1)/2+(m-x)*x;
    }
    ll cl(ll y){
        if(n<=y) return n*(n+1)/2;
        return y*(y+1)/2+(n-y)*y;
    }
    // ll calc()
    ll ax,ay;
    int main(){
        int t;rd(t);
        while(t--){
            rd(n);rd(m);rd(P);
            swap(n,m);
            ax=0;ay=0;
    
            ll S=0;
            for(reg d=1;d<=min(n,m);++d){
                S+=(ll)d*(1+m-d+n-d);
            }
            ll ns=S;
            ll s0=n*m;
            ll k,x,g;
            g=exgcd(s0,P,x,k);
            x=(x%(P/g)+(P/g))%(P/g);
    
            for(reg i=1;i<=m;++i){
                ll tmp=P-(ns%P);
                // cout<<" ii -------- "<<i<<" : "<<ns<<endl;
                if(tmp%g==0){
                    ll nx=x*(tmp/g);
                    nx=(nx%(P/g)+(P/g))%(P/g);
                    ll tx=1+nx,ty=i+nx;
                    // cout<<" tx "<<tx<<" ty "<<ty<<" : "<<ns+nx*s0<<endl;
                    if(!ax||(ax+ay>tx+ty)||((ax+ay==tx+ty)&&(tx<ax))){
                        ax=tx;ay=ty;
                    }
                }    
                ns-=ch(i);
                ns+=ch(i+n);
            }
    
            ns=S;
            for(reg j=1;j<=n;++j){
                ll tmp=P-(ns%P);
                // cout<<" J ----------"<<j<<" ns "<<ns<<endl;
                if(tmp%g==0){
                    ll nx=x*(tmp/g);
                    nx=(nx%(P/g)+(P/g))%(P/g);
                    ll tx=j+nx,ty=1+nx;
                    // cout<<" tx "<<tx<<" ty "<<ty<<" : "<<ns+nx*s0<<endl;
                    if(!ax||(ax+ay>tx+ty)||((ax+ay==tx+ty)&&(tx<ax))){
                        ax=tx;ay=ty;
                    }
                }    
                ns-=cl(j);
                ns+=cl(j+m);
            }
            if(!ax){
                puts("-1");
            }else{
                printf("%lld %lld\n",ax,ay);
            }
        }   
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

矩阵非常对称，

这个性质挖的好啊。

然后就比较简单了。

转载于:https://www.cnblogs.com/Miracevin/p/11030243.html

[Link 1]: http://hihocoder.com/contest/hihointerview5/problem/4
[http_hihocoder.com_discuss_question_3005]: http://hihocoder.com/discuss/question/3005
[1399631-20190616104516765-109657497.png]: /images/20211223/2a7ad18d3e2e4ce09cdab445158fb45c.png
[1399631-20190616104736237-360173894.png]: /images/20211223/3d1aae5c256c42279337b37ce14eb679.png