#669823 (C++17) No.1558 Derby Live

提出ソース
結果

問題	No.1558 Derby Live
コンテスト
ユーザー	bayashiko
提出日時	2021-06-25 23:03:24
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	10,400 bytes
コンパイル時間	5,477 ms
コンパイル使用メモリ	298,784 KB
最終ジャッジ日時	2025-01-22 12:36:13
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 9 TLE * 24
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define flc(x) __builtin_popcountll(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vec vector<lint>
#define nep(x) next_permutation(all(x))
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=3e5+5;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//vector<int> bucket[MAX_N/1000];
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
#include<atcoder/all>
using namespace atcoder;
typedef __int128_t llint;

template<class T>
struct Matrix{
    vector<vector<T>> A;
    Matrix(){};
    Matrix(size_t n,size_t m):A(n,vector<T>(m,0)){};
    Matrix(size_t n):A(n,vector<T>(n,0)){};
    size_t height() const{
        return (A.size());
    }
    size_t width() const{
        return (A[0].size());
    }
    inline const vector<T> &operator[](int k) const{
        return (A.at(k));
    }
    inline vector<T> &operator[](int k){
        return (A.at(k));
    }

    static Matrix I(size_t n) {
        Matrix mat(n);
        rep(i,n) mat[i][i]=1;
        return (mat);
    }

    static Matrix O(size_t n) {
        Matrix mat(n);
        return (mat);
    }

    static Matrix make(vector<vector<T>> tsumugi){
        Matrix mat(tsumugi.size(),tsumugi[0].size());
        rep(i,tsumugi.size()) rep(j,tsumugi[0].size()){
            mat[i][j]=tsumugi[i][j];
        }
        return (mat);
    } 

    Matrix &operator+=(const Matrix &B) {
        size_t n=height(),m=width();
        assert(n==B.height() && m==B.width());
        rep(i,n) rep(j,m) (*this)[i][j]+=B[i][j];
        return (*this);
    }

    Matrix &operator-=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        rep(i,n) rep(j,m) (*this)[i][j] -= B[i][j];
        return (*this);
    }

    Matrix &operator*=(const Matrix &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector< vector< T > > C(n, vector< T >(m, 0));
        rep(i,n) rep(j,m) rep(k,p) C[i][j]=(C[i][j]+(*this)[i][k]*B[k][j]);
        A.swap(C);
        return (*this);
    }

    Matrix &operator^=(long long k) {
        Matrix B=Matrix::I(height());
        while(k>0) {
            if(k&1) B*=*this;
            *this*=*this;
            k>>=1LL;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix &B) const{return (Matrix(*this) += B);}
    Matrix operator-(const Matrix &B) const{return (Matrix(*this) -= B);}
    Matrix operator*(const Matrix &B) const{return (Matrix(*this) *= B);}
    Matrix operator^(const long long k) const{return (Matrix(*this) ^= k);}

    friend ostream &operator<<(ostream &os, Matrix &p) {
        size_t n = p.height(), m = p.width();
        for(int i = 0; i < n; i++) {
            os << "[";
            for(int j = 0; j < m; j++) {
            os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
    return (os);
    }

    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for(int i = 0; i < width(); i++) {
            int idx = -1;
            for(int j = i; j < width(); j++) {
                if(B[j][i] != 0) idx = j;
            }
            if(idx == -1) return (0);
            if(i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for(int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for(int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for(int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};

vector<vector<lint>> mtx{
    {1,0,1},//F(N-1),F(N-2),...,F(N-K)の係数
    {1,0,0},//1は単位元(ex.積なら1,ANDなら2^N-1)
    {0,1,0},//0は零元(ex.積やANDなら0,ORなら2^N-1?)
}; // K次正方行列

vector<vector<lint>> F{{0,0,1}}; //F(1)~F(K)の値


Matrix<lint> MTX;
Matrix<lint> func;

void powerinit(){
    MTX=MTX.make(mtx);
    func=func.make(F);
}

template<class T>
Matrix<T> Maker(vector<vector<T>> base){
    Matrix<T> res=res.make(base);
    return res;
}

template<class T>
Matrix<T> PowMatSum(Matrix<T> A,lint n){ //A+A^2+...+A^Nを返す
    int msize=A.height();
    Matrix<T> B(msize*2);
    rep(i,msize) rep(j,msize) B[i][j]=A[i][j];
    rep(i,msize) B[msize+i][i]=B[msize+i][msize+i]=1;
    B^=n+1;
    rep(i,msize) B[msize+i][i]-=1;
    Matrix<T> res(msize);
    rep(i,msize) rep(j,msize) res[i][j]=B[msize+i][j];
    return res;
}

template<class T>
T calc(lint n,Matrix<T> A,Matrix<T> f){ //F(N)の計算
    if(n==0) return 0;
    A^=n-1;
    T res=0; //零元
    rep(i,A.height()) res+=A[A.height()-1][i]*f[0][A.height()-1-i]; //演算 適宜演算子を変える
    return res;
}

template<class T>
T calc2(Matrix<T> A,Matrix<T> f){ //漸化式じゃない方
    T res=0; //零元
    rep(i,A.height()) res+=A[0][i]*f[0][i]; //演算 適宜演算子を変える
    return res;
}

template<class T>
T calcsum(lint n,Matrix<T> A,Matrix<T> f){ //Σ[i=1..N]F(i)の計算
    if(n==0) return 0;
    int msize=A.height();
    Matrix<T> B(msize*2);
    rep(i,msize) rep(j,msize) B[i][j]=A[i][j];
    rep(i,msize) B[msize+i][i]=B[msize+i][msize+i]=1;
    B^=n;
    rep(i,msize) B[msize+i][i]-=1;
    T res=0; //零元
    rep(i,msize) res+=B[msize*2-1][i]*f[0][msize-1-i]; //演算 適宜演算子を変える
    return res;
}

template<class T>
Matrix<T> rotateR(){//90度右回転
    Matrix<T> res;
    res=res.O(3);
    res[0][1]=1,res[1][0]=-1,res[2][2]=1;
    return res;
}
template<class T>
Matrix<T> rotateL(){//90度左回転
    Matrix<T> res;
    res=res.O(3);
    res[0][1]=-1,res[1][0]=1,res[2][2]=1;
    return res;
}
template<class T>
Matrix<T> flipX(T p){//x=pについて対称移動
    Matrix<T> res;
    res=res.O(3);
    res[0][0]=-1,res[1][1]=1,res[2][2]=1;
    res[0][2]=2*p;
    return res;
}
template<class T>
Matrix<T> flipY(T p){//y=pについて対称移動
    Matrix<T> res;
    res=res.O(3);
    res[0][0]=1,res[1][1]=-1,res[2][2]=1;
    res[1][2]=2*p;
    return res;
}
template<class T>
Matrix<T> move(T x,T y){//(x,y)だけ平行移動
    Matrix<T> res;
    res=res.I(3);
    res[0][2]=x,res[1][2]=y;
    return res;
}
template<class T>
Matrix<T> point(T x,T y){//点(x,y)を表す3×1行列を返す
    Matrix<T> res(3,1);
    res[0][0]=x,res[1][0]=y,res[2][0]=1;
    return res;
}

double EPS=1e-9;

template<class T> int GaussJordan(Matrix<T> &A, bool is_extended = false){
    int m = A.height(), n = A.width();
    int rank = 0;
    for (int col = 0; col < n; ++col) {
        // 拡大係数行列の場合は最後の列は掃き出ししない
        if (is_extended && col == n-1) break;

        // ピボットを探す
        int pivot = -1;
        T ma = EPS;
        for (int row = rank; row < m; ++row) {
            if (abs(A[row][col]) > ma) {
                ma = abs(A[row][col]);
                pivot = row;
            }
        }
        // ピボットがなかったら次の列へ
        if (pivot == -1) continue;

        // まずは行を swap
        swap(A[pivot], A[rank]);

        // ピボットの値を 1 にする
        auto fac = A[rank][col];
        for (int col2 = 0; col2 < n; ++col2) A[rank][col2] /= fac;

        // ピボットのある列の値がすべて 0 になるように掃き出す
        for (int row = 0; row < m; ++row) {
            if (row != rank && abs(A[row][col]) > EPS) {
                auto fac = A[row][col];
                for (int col2 = 0; col2 < n; ++col2) {
                    A[row][col2] -= A[rank][col2] * fac;
                }
            }
        }
        ++rank;
    }
    return rank;
}

template<class T>
vector<T> linear_equation(Matrix<T> mat,vector<T> num){
    int m=mat.height(),n=mat.width();
    Matrix<T> M(m,n+1);
    rep(i,m) rep(j,n) M[i][j]=mat[i][j];
    rep(i,m) M[i][n]=num[i];
    int rank=GaussJordan(M,true);
    vector<T> res;
    for(int row=rank;row<m;row++) if(abs(M[row][n])>EPS) return res;
    res.assign(n,0);
    rep(i,rank) res[i]=M[i][n];
    return res;
}

int N,M,Q;

Matrix<lint> op(Matrix<lint> a,Matrix<lint> b){
    return a*b;
}
Matrix<lint> e(){
    return MTX.I(N);
}

int fix(int p){
    return M-1-p;
}

int main(void){
    cin >> N >> M >> Q;
    segtree<Matrix<lint>,op,e> seg(M);
    while(Q--){
        int t;
        cin >> t;
        if(t==1){
            Matrix<lint> use=MTX.O(N);
            int D;
            cin >> D;
            D--;
            D=fix(D);
            int P[N];
            rep(j,N) cin >> P[j],P[j]--;
            rep(j,N) use[P[j]][j]=1;
            seg.set(D,use);
        }
        else if(t==2){
            int S;
            cin >> S;
            S--;
            Matrix<lint> res=seg.prod(fix(S),M);
            vector<lint> init(N);
            rep(i,N) init[i]=i;
            vector<lint> ans(N);
            rep(i,N) rep(j,N) ans[i]+=res[i][j]*init[j];
            rep(i,N) cout << ans[i]+1 << " ";
            cout << endl;
        }
        else{
            int L,R;
            cin >> L >> R;
            L--,R--;
            Matrix<lint> res=seg.prod(fix(R),fix(L)+1);
            vector<lint> init(N);
            rep(i,N) init[i]=i;
            vector<lint> ans(N);
            rep(i,N) rep(j,N) ans[i]+=res[i][j]*init[j];
            int ans2=0;
            rep(i,N) ans2+=abs(i-ans[i]);
            cout << ans2 << endl;
        }
    }
}
yukicoder

結果

ソースコード
