#889704 (C++17) No.2448 一次変換と面積

提出ソース

結果

問題	No.2448 一次変換と面積
ユーザー	tko919
提出日時	2023-07-11 04:55:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	38 ms / 2,000 ms
コード長	13,263 bytes
コンパイル時間	2,823 ms
コンパイル使用メモリ	226,452 KB
実行使用メモリ	4,476 KB
最終ジャッジ日時	2023-10-10 01:35:26
合計ジャッジ時間	4,201 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,352 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	1 ms 4,352 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,352 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	1 ms 4,348 KB
testcase_07	AC	2 ms 4,352 KB
testcase_08	AC	2 ms 4,352 KB
testcase_09	AC	2 ms 4,352 KB
testcase_10	AC	1 ms 4,348 KB
testcase_11	AC	2 ms 4,352 KB
testcase_12	AC	1 ms 4,348 KB
testcase_13	AC	2 ms 4,352 KB
testcase_14	AC	2 ms 4,352 KB
testcase_15	AC	2 ms 4,352 KB
testcase_16	AC	1 ms 4,348 KB
testcase_17	AC	2 ms 4,476 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	2 ms 4,352 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	37 ms 4,348 KB
testcase_24	AC	38 ms 4,352 KB
testcase_25	AC	36 ms 4,352 KB
testcase_26	AC	37 ms 4,352 KB
testcase_27	AC	36 ms 4,348 KB
testcase_28	AC	36 ms 4,348 KB
testcase_29	AC	36 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) lower_bound(ALL(v),(x))-(v).begin()
#define UB(v,x) upper_bound(ALL(v),(x))-(v).begin()

using ll=long long int;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}

// g++-11 -std=c++1z -o a.out hoge.cpp -I .
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__int128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__uint128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__int128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__uint128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        if(space)_write(' ');
        _write(head);
        write<ln,true>(tail...); 
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

#line 2 "library/Math/fastdiv.hpp"

struct FastDiv{
    using u64=uint64_t;
    using u128=__uint128_t;
    constexpr FastDiv():m(),s(),x(){}
    constexpr FastDiv(int _m)
        :m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){}
    constexpr int get(){return m;}
    constexpr friend u64 operator/(u64 n,const FastDiv& d){
        return (u128(n)*d.x>>d.s)>>64;
    }
    constexpr friend int operator%(u64 n,const FastDiv& d){
        return n-n/d*d.m;
    }
    constexpr pair<u64,int> divmod(u64 n)const{
        u64 q=n/(*this);
        return {q,n-q*m};
    }
    int m,s; u64 x;
};

/**
 * @brief Fast Division
*/
#line 3 "library/Math/dynamic.hpp"

struct Fp{
    using u64=uint64_t;
    int v;
    static int get_mod(){return _getmod();}
    static void set_mod(int _m){bar=FastDiv(_m);}
    Fp inv() const{
        int tmp,a=v,b=get_mod(),x=1,y=0;
        while(b){
            tmp=a/b,a-=tmp*b;
            swap(a,b);
            x-=tmp*y;
            swap(x,y);
        }
        if(x<0){x+=get_mod();}
        return x;
    }
    Fp():v(0){}
    Fp(ll x){
        v=x%get_mod();
        if(v<0)v+=get_mod();
    }
    Fp operator-()const{return Fp()-*this;}
    Fp pow(ll t){
        assert(t>=0);
        Fp res=1,b=*this;
        while(t){
            if(t&1)res*=b;
            b*=b;
            t>>=1;
        }
        return res;
    }
    Fp& operator+=(const Fp& x){
        v+=x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator-=(const Fp& x){
        v+=get_mod()-x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator*=(const Fp& x){
        v=(u64(v)*x.v)%bar;
        return *this;
    }
    Fp& operator/=(const Fp& x){
        (*this)*=x.inv();
        return *this;
    }
    Fp operator+(const Fp& x)const{return Fp(*this)+=x;}
    Fp operator-(const Fp& x)const{return Fp(*this)-=x;}
    Fp operator*(const Fp& x)const{return Fp(*this)*=x;}
    Fp operator/(const Fp& x)const{return Fp(*this)/=x;}
    bool operator==(const Fp& x)const{return v==x.v;}
    bool operator!=(const Fp& x)const{return v!=x.v;}
private:
    static FastDiv bar;
    static int _getmod(){return bar.get();}
};
FastDiv Fp::bar(998244353);

/**
 * @brief Dynamic Modint
 */
#line 2 "library/Math/matrix.hpp"

template<class T>struct Matrix{
    int h,w; vector<vector<T>> val; T det;
    Matrix(){}
    Matrix(int n):h(n),w(n),val(vector<vector<T>>(n,vector<T>(n))){}
    Matrix(int n,int m):h(n),w(m),val(vector<vector<T>>(n,vector<T>(m))){}
    vector<T>& operator[](const int i){return val[i];}
    Matrix& operator+=(const Matrix& m){
        assert(h==m.h and w==m.w);
        rep(i,0,h)rep(j,0,w)val[i][j]+=m.val[i][j];
        return *this;
    }
    Matrix& operator-=(const Matrix& m){
        assert(h==m.h and w==m.w);
        rep(i,0,h)rep(j,0,w)val[i][j]-=m.val[i][j];
        return *this;
    }
    Matrix& operator*=(const Matrix& m){
        assert(w==m.h);
        Matrix<T> res(h,m.w);
        rep(i,0,h)rep(j,0,m.w)rep(k,0,w)res.val[i][j]+=val[i][k]*m.val[k][j];
        *this=res; return *this;
    }
    Matrix operator+(const Matrix& m)const{return Matrix(*this)+=m;}
    Matrix operator-(const Matrix& m)const{return Matrix(*this)-=m;}
    Matrix operator*(const Matrix& m)const{return Matrix(*this)*=m;}
    Matrix pow(ll k){
        Matrix<T> res(h,h),c=*this; rep(i,0,h)res.val[i][i]=1;
        while(k){if(k&1)res*=c; c*=c; k>>=1;} return res;
    }
    vector<int> gauss(int c=-1){
        if(val.empty())return {};
        if(c==-1)c=w;
        int cur=0; vector<int> res; det=1;
        rep(i,0,c){
            if(cur==h)break;
            rep(j,cur,h)if(val[j][i]!=0){
                swap(val[cur],val[j]);
                if(cur!=j)det*=-1;
                break;
            }
            det*=val[cur][i];
            if(val[cur][i]==0)continue;
            rep(j,0,h)if(j!=cur){
                T z=val[j][i]/val[cur][i];
                rep(k,i,w)val[j][k]-=val[cur][k]*z;
            }
            res.push_back(i);
            cur++;
        }
        return res;
    }
    Matrix inv(){
        assert(h==w);
        Matrix base(h,h*2),res(h,h);
        rep(i,0,h)rep(j,0,h)base[i][j]=val[i][j];
        rep(i,0,h)base[i][h+i]=1;
        base.gauss(h);
        rep(i,0,h)rep(j,0,h)res[i][j]=base[i][h+j]/base[i][i];
        return res;
    }
    bool operator==(const Matrix& m){
        assert(h==m.h and w==m.w);
        rep(i,0,h)rep(j,0,w)if(val[i][j]!=m.val[i][j])return false;
        return true;
    }
    bool operator!=(const Matrix& m){
        assert(h==m.h and w==m.w);
        rep(i,0,h)rep(j,0,w)if(val[i][j]==m.val[i][j])return false;
        return true;
    }
    friend istream& operator>>(istream& is,Matrix& m){
        rep(i,0,m.h)rep(j,0,m.w)is>>m[i][j];
        return is;
    }
    friend ostream& operator<<(ostream& os,Matrix& m){
        rep(i,0,m.h){
            rep(j,0,m.w)os<<m[i][j]<<(j==m.w-1 and i!=m.h-1?'\n':' ');
        }
        return os;
    }
};

/**
 * @brief Matrix
 */
#line 6 "sol.cpp"

template<typename T>T det(Matrix<T>& a){
    return a[0][0]*a[1][1]-a[0][1]*a[1][0];
}

FastIO io;
void solve(int _rot){
    // io.write<false>("Case #"+to_string(_rot)+": ");
    ll n,mod;
    io.read(n,mod);
    Fp::set_mod(mod);
    Matrix<__int128_t> a(2,2);
    rep(i,0,2)rep(j,0,2)io.read(a[i][j]);

    // value
    ll nn=n;
    Matrix<Fp> A(2,2),res(2,2),add(2,2),pw(2,2);
    rep(i,0,2)rep(j,0,2)A[i][j]=pw[i][j]=a[i][j];
    add[0][0]=add[1][1]=1;
    while(nn){
        if(nn&1){
            res*=pw;
            res+=add;
        }
        add+=add*pw;
        pw*=pw;
        nn>>=1;
    }
    res*=A;
    Fp ret=res[0][0]*res[1][1]-res[0][1]*res[1][0];
    cerr<<ret.v<<'\n';

    // sign
    bool sign=0;
    Matrix<__int128_t> ae=a;
    ae[0][0]--; ae[1][1]--;
    if(det(ae)!=0){
        if(det(a)<0)sign^=1;
        if(det(ae)<0)sign^=1;
        ll A=a[0][0],B=a[0][1],C=a[1][0],D=a[1][1];
        if((A-D)*(A-D)+B*C*4>=0){
            Matrix<__int128_t> base(2,2);
            rep(i,0,2)rep(j,0,2)base[i][j]=a[i][j];
            if(n%2==0)base*=a;
            base[0][0]--; base[1][1]--;
            if(det(base)<0)sign^=1;
        }
    }
    else{
        if(n&1){
            if(det(a)<0)sign^=1;
        }
    }
    if(sign)ret=-ret;
    io.write(ret.v);
}

int main(){
    int t;
    io.read(t);
    rep(rot,0,t)solve(rot+1);
    return 0;
}

yukicoder

結果

テストケース

ソースコード