#928487 (C++17) No.2017 Mod7 Parade

提出ソース
結果

問題	No.2017 Mod7 Parade
ユーザー	asaringo
提出日時	2023-11-13 00:16:48
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,050 ms / 2,000 ms
コード長	12,876 bytes
コンパイル時間	3,241 ms
コンパイル使用メモリ	235,388 KB
実行使用メモリ	11,904 KB
最終ジャッジ日時	2024-09-26 03:08:23
合計ジャッジ時間	16,589 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	811 ms 9,984 KB
testcase_04	AC	544 ms 7,680 KB
testcase_05	AC	402 ms 6,528 KB
testcase_06	AC	893 ms 10,624 KB
testcase_07	AC	110 ms 5,376 KB
testcase_08	AC	507 ms 7,424 KB
testcase_09	AC	194 ms 5,376 KB
testcase_10	AC	513 ms 7,552 KB
testcase_11	AC	708 ms 9,216 KB
testcase_12	AC	625 ms 8,320 KB
testcase_13	AC	1,033 ms 11,776 KB
testcase_14	AC	1,034 ms 11,904 KB
testcase_15	AC	1,050 ms 11,776 KB
testcase_16	AC	1,032 ms 11,776 KB
testcase_17	AC	1,033 ms 11,776 KB
testcase_18	AC	1,017 ms 11,776 KB
testcase_19	AC	222 ms 11,776 KB
testcase_20	AC	2 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e ...) e
#define overload5(a, b, c, d, e, f ...) f
#define overload6(a, b, c, d, e, f, g ...) g
#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
typedef long long ll;
typedef long double ld;
#define chmin(a,b) a = min(a,b);
#define chmax(a,b) a = max(a,b);
#define bit_count(x) __builtin_popcountll(x)
#define leading_zero_count(x) __builtin_clz(x)
#define trailing_zero_count(x) __builtin_ctz(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)
#define rep1(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl;
#define print(...) printall(__VA_ARGS__);
#define debug(a) cout << #a << " " << a << endl;
#define all(a) a.begin(), a.end()
#define endl "\n";
#define v1(T,n,a) vector<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}

const int mod = 1000000007 ;

template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using modint = ModInt< mod >;

const int mod2 = 7 ;

template< int mod2 >
struct ModInt2 {
    int x;

    ModInt2() : x(0) {}

    ModInt2(int64_t y) : x(y >= 0 ? y % mod2 : (mod2 - (-y) % mod2) % mod2) {}

    ModInt2 &operator+=(const ModInt2 &p) {
        if((x += p.x) >= mod2) x -= mod2;
        return *this;
    }

    ModInt2 &operator-=(const ModInt2 &p) {
        if((x += mod2 - p.x) >= mod2) x -= mod2;
        return *this;
    }

    ModInt2 &operator*=(const ModInt2 &p) {
        x = (int) (1LL * x * p.x % mod2);
        return *this;
    }

    ModInt2 &operator/=(const ModInt2 &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt2 operator-() const { return ModInt2(-x); }

    ModInt2 operator+(const ModInt2 &p) const { return ModInt2(*this) += p; }

    ModInt2 operator-(const ModInt2 &p) const { return ModInt2(*this) -= p; }

    ModInt2 operator*(const ModInt2 &p) const { return ModInt2(*this) *= p; }

    ModInt2 operator/(const ModInt2 &p) const { return ModInt2(*this) /= p; }

    bool operator==(const ModInt2 &p) const { return x == p.x; }

    bool operator!=(const ModInt2 &p) const { return x != p.x; }

    ModInt2 inverse() const {
        int a = x, b = mod2, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt2(u);
    }

    ModInt2 pow(int64_t n) const {
        ModInt2 ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt2 &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt2 &a) {
        int64_t t;
        is >> t;
        a = ModInt2< mod2 >(t);
        return (is);
    }

    static int get_mod() { return mod2; }
};

using modint2 = ModInt2< mod2 >;

template<typename T> struct Matrix{
    int row, col;
    vector<vector<T>> mat ;

    private:
        void init_(vector<vector<T>> A){
            row = A.size();
            col = A[0].size();
            mat = A;
        }
        
        void init_(vector<T> A, bool row_matrix = false){
            if(row_matrix) {
                col = (int)A.size();
                row = 1;
                mat.resize(1);
                mat[0] = A;
            }
            else {
                col = 1;
                row = (int)A.size();
                mat.resize(row,vector<T>(1));
                rep(i,row) mat[i][0] = A[i];
            }
        }

        Matrix<T> pow_(ll k){
            assert(row == col);
            vector<vector<T>> E(row,vector<T>(row,0));
            rep(i,row) rep(j,row) if(i == j) E[i][j] = 1;
            Matrix<T> res(E);
            Matrix<T> X(mat);
            while(k > 0){
                if(k & 1) res *= X;
                X *= X;
                k >>= 1 ;
            }
            return res;
        }

        void transpose_() {
            vector<vector<T>> res(col,vector<T>(row));
            rep(i,row) rep(j,col) res[j][i] = mat[i][j];
            mat = res;
            swap(row,col);
        }

        void concat_col_(vector<T> &Y) {
            Matrix X(Y);
            concat_col_(X);
        }
        void concat_col_(vector<vector<T>> &Y) {
            Matrix X(Y);
            concat_col_(X);
        }
        void concat_col_(Matrix &Y) {
            assert((int)Y.row == row);
            col += Y.col;
            rep(i,row) {
                rep(j,Y.col) mat[i].push_back(Y.mat[i][j]);
            }
        }

        void concat_row_(vector<T> &Y) {
            Matrix X(Y,true);
            concat_row_(X);
        }
        void concat_row_(vector<vector<T>> &Y) {
            Matrix X(Y);
            concat_row_(X);
        }
        void concat_row_(Matrix &Y) {
            assert((int)Y.col == col);
            row += Y.row;
            rep(i,Y.row) mat.push_back(Y.mat[i]);
        }

        void print_() {
            rep(i,row){
                rep(j,col) cout << mat[i][j] << " "; cout << endl;
            }
        }

    public:

        inline Matrix &operator+=(const Matrix Y) {
            rep(i,row) rep(j,col) mat[i][j] += Y.mat[i][j];
            return *this ;
        }

        inline Matrix &operator-=(const Matrix Y) {
            rep(i,row) rep(j,col) mat[i][j] -= Y.mat[i][j];
            return *this ;
        }

        inline Matrix &operator*=(const Matrix Y) {
            int x = row, y = Y.col, n = col;
            vector<vector<T>> res(x,vector<T>(y));
            rep(i,x) rep(j,y) rep(k,n) res[i][j] += mat[i][k] * Y.mat[k][j];
            swap(mat,res);
            row = x;
            col = y;
            return *this ;
        }

        inline Matrix operator-() const {
            rep(i,row) rep(j,col) mat[i][j] *= -1;
            return *this ;
        }

        inline Matrix operator+(const Matrix Y) const { return Matrix(*this) += Y; }

        inline Matrix operator-(const Matrix Y) const { return Matrix(*this) -= Y; }

        inline Matrix operator*(const Matrix Y) const { return Matrix(*this) *= Y; }

        inline bool operator==(const Matrix Y) const { return mat == Y.mat; }

        inline bool operator!=(const Matrix Y) const { return mat != Y.mat; }

        inline vector<T>&operator[](int i) { return mat[i] ; }

        Matrix(int n): row(n), col(0) { mat.resize(row); }
        Matrix(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }
        Matrix(vector<vector<T>> A){ init_(A); }
        void init(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }
        void init(vector<vector<T>> A) { init_(A); }
        size_t row_size() { return row; }
        size_t col_size() { return col; }
        Matrix pow(ll k){ return pow_(k); }
        void transpose() { transpose_(); }
        void concat_col(vector<vector<T>> &Y) { concat_col_(Y); }
        void concat_col(vector<T> &Y) { concat_col_(Y); }
        void concat_col(Matrix &Y) { concat_col_(Y); }
        void concat_row(vector<vector<T>> &Y) { concat_row_(Y); }
        void concat_row(vector<T> &Y) { concat_row_(Y); }
        void concat_row(Matrix &Y) { concat_row_(Y); }
        // void print() { print_(); }
};
// function                     : return              : description
// -----------------------------------------------------
// init(vector<T>, row_matrix)    : void                : 1次元ベクトルに対して行列化する, 列行列か行行列を選択できる
// init(vector<vector<T>>)        : void                : 2次元ベクトルに対して行列化する
// row_size()                     : int                 : 行の大きさ
// col_size()                     : int                 : 列の大きさ
// pow(k)                         : Matrix              : 行列をk乗する(n * n 行列であること)
// transpose()                    : void                : 転置する
// concat_col(vector<vector<T>>)  : void                : 列に関して結合する
// concat_col(vector<T>)          : void                : 列に関して結合する
// concat_col(Matrix)             : void                : 列に関して結合する
// concat_row(vector<vector<T>>)  : void                : 列に関して結合する
// concat_row(vector<T>)          : void                : 列に関して結合する
// concat_row(Matrix)             : void                : 列に関して結合する
// print()                        : void                : 行列を出力する
// *注意* 取り敢えず全てをコピペすることを奨励

// verify
// https://atcoder.jp/contests/dp/tasks/dp_r

int n;

void solve(){
    cin >> n;
    vector<ll> D(n), L(n);
    rep(i,n) cin >> D[i] >> L[i];
    vector<vector<modint>> dp(n+1,vector<modint>(7,0));
    dp[0][0] = 1;
    rep(i,n){
        ll d = D[i];
        ll l = L[i];
        modint2 ten = 10;
        modint2 vt = ten.pow(l);
        vector<vector<modint2>> A = {
            {10, 1},
            {0, 1},
        };
        vector<modint2> b = {0, d};
        Matrix<modint2> mat(A), B(b);
        auto M = mat.pow(l) * B;
        auto val = M[0][0].x;
        auto vtn = vt.x;
        rep(j,7){
            dp[i+1][j] += dp[i][j];
            dp[i+1][(j * vtn + val)%7] += dp[i][j];
        }
    }
    modint res = 0;
    rep(i,7) {
        res += dp[n][i] * i;
    }
    pt(res)
}

int main(){
    fast_io
    int t = 1;
    // cin >> t;
    rep(i,t) solve();
}
yukicoder

結果

テストケース

ソースコード
