[PYTHON] yukicoder contest 259 Review

result

Impressions

A I felt that the problem was difficult and ran away. It's not difficult if you follow the basics, so I regret it. In the B problem, I made a mistake in the constant and lost time. I'm sorry ... The C problem was a kind of problem that I hadn't done much, but I solved it. I'm glad I was sticky.

Problem A

(1) The range of $ t $ depends on $ D $, and $ D $ is ** extremely large. ** It is necessary to find the ** minimum value ** $ T $ of that $ t $. (2) It holds for $ t <T $. Since there is ** monotonicity ** that holds for $ t> T $, $ T $ may be obtained by binary search because of these two conditions. Also, if the total distance traveled by each slime in a certain $ t $ is calculated by $ O (N) $, the amount of calculation will be $ O (N \ log {D}) $, so if you can write a program in time. I thought.

Now consider the total distance traveled by all slimes in $ t $, but when the two slimes (speeds are $ v_1 $, $ v_2 $) are combined into one slime, the speed of the remaining slime The result is $ v_1 + v_2 $. Therefore, ** pay attention to the total distance traveled **, even if each slime does not coalesce, it does not change, so considering how far all slimes travel up to $ t $ (when not coalescing), $ O It can be calculated by (N) $.

Also, please refer to this article for binary search. In addition, this problem can be solved with $ O (N) $ instead of $ O (N \ log {D}) $ (Main Solution editorial)).

A.py

n,d=map(int,input().split())
x=list(map(int,input().split()))
v=list(map(int,input().split()))
s=sum(v)

def f(k):
    return s*k

#l is false,r is true
l,r=0,1000000000000
while l+1<r:
    k=l+(r-l)//2
    if f(k)>=d:
        r=k
    else:
        l=k
print(r)

Problem B

First, since the ** primality test is performed by the query, all the prime numbers that can be judged by the Eratosthenes sieve ** are checked (this makes the query primality test $ O (1) $). Here, if it is determined that $ p $ is not a prime number, $ -1 $ can be output, so the discussion below assumes that $ p $ is a prime number.

Under this, if you simply ask for $ A ^ {P!} \ (Mod \ P) $ as $ ((A ^ 1) ^ 2) ^ 3… $, it will not be in time even under the condition of $ mod \ P $. Hmm. What should be remembered here is ** Fermat's Little Theorem **. I think you should keep in mind that it is common sense in problems related to the power of $ remainder $. In this theorem, ** $ A ^ {p-1} = 1 \ (mod \ p) $ ** holds for $ A $, which is not a multiple of $ p $ for the prime number $ p $. Here, $ A ^ {p!} = (A ^ {p-1}) ^ x \ (x = 1,2,…, p-2, p) $ holds, so ($ \ because \ p $ is $ 2 $ or more than a prime number), $ A ^ {p!} = 0 \ (mod \ P) $ if $ A $ is a multiple of $ p $, $ A ^ {p!} = 1 \ otherwise It will be (mod \ P) $.

To summarize the above, $ -1 $ when $ p $ is not a prime number, $ 0 $ when $ p $ is a prime number and $ A % p = 0 $, and $ A % p \ when $ p $ is a prime number. When neq is 0 $, $ 1 $ should be output.

** I forgot to change the range of MAXRR in the code and issued WA **. It was painful. This took a lot of time.

B.cc

//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 6000000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

#define PN true //Prime number
#define NPN false //Not a prime number
//Non-essence
#define MAXRR 3000 //√ Set a number greater than or equal to MAXR

//Assume that integers up to MAXR are prime numbers(Shave from here)
vector<bool> PN_chk(MAXR+1,PN);//0index corresponds to the i-th integer i(0~MAXR)
//Prepare an array to store prime numbers
vector<ll> PNs;

void se(){
    //0 and 1 are not prime numbers
    PN_chk[0]=NPN;PN_chk[1]=NPN;

    FOR(i,2,MAXRR){
        //A prime number if it is assumed to be a prime number when you arrive
        if(PN_chk[i]) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=NPN;}
    }
    FOR(i,2,MAXR){
        if(PN_chk[i]) PNs.PB(i);
    }
}

ll modpow(ll a,ll n,ll p){
    if(n==0)return 1;
    ll t=modpow(a,n/2,p);
    t=t*t%p;
    if(n&1)t=t*a%p;
    return t;
}

signed main(){
    //Code for speeding up input
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    se();
    ll t;cin>>t;
    REP(_,t){
        ll a,p;cin>>a>>p;
        if(!PN_chk[p]){
            cout<<-1<<endl;
            continue;
        }
        if(a%p==0){
            cout<<0<<endl;
            continue;
        }
        cout<<1<<endl;
    }
}

C problem

If I knew the similar subject, I could do my best to implement it, so I felt the power of devotion.

First, if you put $ r_i and c_i $ as shown below, you can divide them into the four parts shown in the figure below.

Based on this, we can see that the answer to be obtained is to find the product of the products of the numbers contained in each of the rectangles ①, ②, ③, and ④. For the part included in such a rectangle, query processing can be performed with $ O (1) $ by pre-calculating with ** two-dimensional accumulation **.

In creating a table by pre-calculation, ** in the case of two-dimensional cumulative sum ** is as follows. Also, each cell is $ a [x] [y] $, and the following are all 0-indexed.

$ s [x] [y]: = [0, x) × [0, y) The sum of the rectangular intervals of $ s[x+1][y+1] = s[x][y+1] + s[x+1][y] - s[x][y] + a[x][y]

Therefore, in the case of ** two-dimensional cumulative product **, if you do the same, it will be as follows.

$ s [x] [y]: = [0, x) × [0, y) The product of the rectangular intervals of $ s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

Therefore, this ** two-dimensional cumulative product can be defined in four directions **, and the remaining three rectangular intervals are as follows. The expression of the interval is different from the definition of mathematics, but I hope you can understand the atmosphere. (I was trying to do it in an atmosphere without describing the following. ** I will thoroughly describe the policy **.)

$ s [x] [y]: = [w-1, x) × [0, y) The product of the rectangular intervals of $ s[x-1][y+1] = s[x][y+1] \times s[x-1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [0, x) × [h-1, y) The product of the rectangular intervals of $ s[x+1][y-1] = s[x][y-1] \times s[x+1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [w-1, x) × [h-1, y) The product of the rectangular intervals of $ s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

If you can implement this, you can write a program by ** noting that it is an open interval **. Also, I used my modint library because I only need to find the remainder divided by $ 10 ^ 9 + 7 $.

Postscript (8/2)

Dividing by zero is troublesome if you divide the filled part from the whole, so it seems better to be aware that ** the problem of finding the product of multiple numbers is expressed only by the product **.

C.cc

//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

template<ll mod> class modint{
public:
    ll val=0;
    //constructor
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Copy constructor
    modint(const modint &r){val=r.val;}
    //Arithmetic operator
    modint operator -(){return modint(-val);} //unary
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    //Assignment operator
    modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    modint &operator /=(const modint &r){
        ll a=r.val,b=mod,u=1,v=0;
        while(b){
            ll t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        val=val*u%mod;
        if(val<0)val+=mod;
        return *this;
    }
    //Equivalence comparison operator
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
};

using mint = modint<MOD>;

//I / O stream
istream &operator >>(istream &is,mint& x){//Do not add const to x
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Exponentiation
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}



signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll h,w;cin>>h>>w;
    vector<vector<ll>> A(h,vector<ll>(w,0));
    REP(i,h)REP(j,w)cin>>A[i][j];
    vector<vector<vector<mint>>> s(4,vector<vector<mint>>(h+1,vector<mint>(w+1,1)));
    REP(j,h){
        REP(k,w){
            ll x,y;
            x=j;y=k;
            s[0][x+1][y+1]=s[0][x+1][y]*s[0][x][y+1]/s[0][x][y]*A[x][y];
        }
    }
    REP(j,h){
        REP(k,w-1){
            ll x,y;
            x=j;y=w-1-k;
            s[1][x+1][y-1]=s[1][x+1][y]*s[1][x][y-1]/s[1][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w){
            ll x,y;
            x=h-1-j;y=k;
            s[2][x-1][y+1]=s[2][x-1][y]*s[2][x][y+1]/s[2][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w-1){
            ll x,y;
            x=h-1-j;y=w-1-k;
            s[3][x-1][y-1]=s[3][x-1][y]*s[3][x][y-1]/s[3][x][y]*A[x][y];
        }
    }
    #if 0
    REP(i,4){
        REP(j,h){
            REP(k,w){
                cout<<s[i][j][k]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    #endif
    ll q;cin>>q;
    REP(_,q){
        ll r,c;cin>>r>>c;
        mint ans=1;
        ll x,y;
        x=r-1;y=c-1;
        ans*=s[0][x][y];
        //x=r;y=w-c;
        ans*=s[1][x][y];
        //x=h-r;y=c;
        ans*=s[2][x][y];
        //x=h-r;y=w-c;
        ans*=s[3][x][y];
        cout<<ans<<endl;
    }
}