Submission #7144218


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
//#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

class UnionFind{
private:
    ::std::vector<int_fast32_t> par, edge;
    size_t n;

public:
    UnionFind(){}
    UnionFind(size_t n):n(n){
        par.resize(n, -1);
        edge.resize(n, 0);
    }

    uint_fast32_t find(uint_fast32_t x){
        return par[x] < 0 ? x : par[x] = find(par[x]);
    }

    size_t size(uint_fast32_t x){
        return -par[find(x)];
    }

    bool unite(uint_fast32_t x, uint_fast32_t y){
        x = find(x);
        y = find(y);
        edge[x] += 1;
        if(x == y) return false;
        if(size(x) < size(y)) std::swap(x, y);
        par[x] += par[y];
        edge[x] += edge[y];
        par[y] = x;
        return true;
    }

    bool same(uint_fast32_t x, uint_fast32_t y){
        return find(x) == find(y);
    }

    size_t esize(uint_fast32_t x) {
        return edge[find(x)];
    }
};

int64 mod;

class ModInt{
private:
    using value_type = ::std::uint_fast64_t;
    value_type n;
public:
    ModInt() : n(0) {}
    ModInt(value_type n_) : n(n_ % mod) {}
    ModInt(const ModInt& m) : n(m.n) {}

    ModInt& operator=(const ModInt& m) {
        n = m.n;
        return *this;
    }
    ModInt& operator=(const value_type& x) {
        n = x;
        return *this;
    }

    template<typename T>
    explicit operator T() const { return static_cast<T>(n); }
    value_type get() const { return n; }

    friend ::std::ostream& operator<<(::std::ostream &os, const ModInt &a) {
        return os << a.n;
    }

    friend ::std::istream& operator>>(::std::istream &is, ModInt &a) {
        value_type x;
        is >> x;
        a = ModInt(x);
        return is;
    }

    bool operator==(const ModInt& m) const { return n == m.n; }
    bool operator!=(const ModInt& m) const { return n != m.n; }
    ModInt& operator*=(const ModInt& m){ n = n * m.n % mod; return *this; }

    ModInt pow(value_type b) const{
        ModInt ans = ModInt(1), m = ModInt(*this);
        while(b){
            if(b & 1) ans *= m;
            m *= m;
            b >>= 1;
        }
        return ans;
    }

    ModInt inv() const { return (*this).pow(mod-2); }
    ModInt& operator+=(const ModInt& m){ n += m.n; n = (n < mod ? n : n - mod); return *this; }
    ModInt& operator-=(const ModInt& m){ n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
    ModInt& operator/=(const ModInt& m){ *this *= m.inv(); return *this; }
    ModInt operator+(const ModInt& m) const { return ModInt(*this) += m; }
    ModInt operator-(const ModInt& m) const { return ModInt(*this) -= m; }
    ModInt operator*(const ModInt& m) const { return ModInt(*this) *= m; }
    ModInt operator/(const ModInt& m) const { return ModInt(*this) /= m; }
    ModInt& operator++(){ n += 1; return *this; }
    ModInt& operator--(){ n -= 1; return *this; }
    ModInt operator++(int){
        ModInt old(n);
        n += 1;
        return old;
    }
    ModInt operator--(int){
        ModInt old(n);
        n -= 1;
        return old;
    }
    ModInt operator-() const { return ModInt(mod-n); }
};

template<typename T>
class Matrix{
private:
    using size_type = ::std::size_t;
    using Row = ::std::vector<T>;
    using Mat = ::std::vector<Row>;

    size_type R, C; // row, column
    Mat A;

    void add_row_to_another(size_type r1, size_type r2, const T k){ // Row(r1) += Row(r2)*k
        for(size_type i = 0;i < C;i++)
            A[r1][i] += A[r2][i]*k;
    }

    void scalar_multiply(size_type r, const T k){
        for(size_type i = 0;i < C;i++)
            A[r][i] *= k;
    }

    void scalar_division(size_type r, const T k){
        for(size_type i = 0;i < C;i++)
            A[r][i] /= k;
    }

public:
    Matrix(){}
    Matrix(size_type r, size_type c) : R(r), C(c), A(r, Row(c)) {}
    Matrix(const Mat &m) : R(m.size()), C(m[0].size()), A(m) {}
    Matrix(const Mat &&m) : R(m.size()), C(m[0].size()), A(m) {}
    Matrix(const Matrix<T> &m) : R(m.R), C(m.C), A(m.A) {}
    Matrix(const Matrix<T> &&m) : R(m.R), C(m.C), A(m.A) {}
    Matrix<T> &operator=(const Matrix<T> &m){
        R = m.R; C = m.C; A = m.A;
        return *this;
    }
    Matrix<T> &operator=(const Matrix<T> &&m){
        R = m.R; C = m.C; A = m.A;
        return *this;
    }
    static Matrix I(const size_type N){
        Matrix m(N, N);
        for(size_type i = 0;i < N;i++) m[i][i] = ModInt(1);
        return m;
    }

    const Row& operator[](size_type k) const& { return A.at(k); }
    Row& operator[](size_type k) & { return A.at(k); }
    Row operator[](size_type k) const&& { return ::std::move(A.at(k)); }

    size_type row() const { return R; } // the number of rows
    size_type column() const { return C; }

    T determinant(){
        assert(R == C);
        Mat tmp = A;
        T res = 1;
        for(size_type i = 0;i < R;i++){
            for(size_type j = i;j < R;j++){ // satisfy A[i][i] > 0
                if (A[j][i] != 0) {
                    if (i != j) res *= -1;
                    swap(A[j], A[i]);
                    break;
                }
            }
            if (A[i][i] == 0) return 0;
            res *= A[i][i];
            scalar_division(i, A[i][i]);
            for(size_type j = i+1;j < R;j++){
                add_row_to_another(j, i, -A[j][i]);
            }
        }
        swap(tmp, A);
        return res;
    }

    Matrix inverse(){
        assert(R == C);
        assert(determinant() != 0);
        Matrix inv(Matrix::I(R)), tmp(*this);
        for(size_type i = 0;i < R;i++){
            for(size_type j = i;j < R;j++){
                if (A[j][i] != 0) {
                    swap(A[j], A[i]);
                    swap(inv[j], inv[i]);
                    break;
                }
            }
            inv.scalar_division(i, A[i][i]);
            scalar_division(i, A[i][i]);
            for(size_type j = 0;j < R;j++){
                if(i == j) continue;
                inv.add_row_to_another(j, i, -A[j][i]);
                add_row_to_another(j, i, -A[j][i]);
            }
        }
        (*this) = tmp;
        return inv;
    }

    Matrix& operator+=(const Matrix &B){
        assert(column() == B.column() && row() == B.row());
        for(size_type i = 0;i < R;i++)
            for(size_type j = 0;j < C;j++)
                (*this)[i][j] += B[i][j];
        return *this;
    }

    Matrix& operator-=(const Matrix &B){
        assert(column() == B.column() && row() == B.row());
        for(size_type i = 0;i < R;i++)
            for(size_type j = 0;j < C;j++)
                (*this)[i][j] -= B[i][j];
        return *this;
    }

    Matrix& operator*=(const Matrix &B){
        assert(column() == B.row());
        Matrix M(R, B.column());
        for(size_type i = 0;i < R;i++) {
            for(size_type j = 0;j < B.column();j++) {
                M[i][j] = 0;
                for(size_type k = 0;k < C;k++) {
                    M[i][j] += (*this)[i][k] * B[k][j];
                }
            }
        }
        swap(M, *this);
        return *this;
    }

    Matrix& operator/=(const Matrix &B){
        assert(C == B.row());
        Matrix M(B);
        (*this) *= M.inverse();
        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 Matrix &B) const { return (Matrix(*this) /= B); }

    bool operator==(const Matrix &B) const {
        if (column() != B.column() || row() != B.row()) return false;
        for(size_type i = 0;i < row();i++)
            for(size_type j = 0;j < column();j++)
                if ((*this)[i][j] != B[i][j]) return false;
        return true;
    }
    bool operator!=(const Matrix &B) const { return !((*this) == B); }

    Matrix pow(size_type k){
        assert(R == C);
        Matrix M(Matrix::I(R));
        while(k){
            if (k & 1) M *= (*this);
            k >>= 1;
            (*this) *= (*this);
        }
        A.swap(M.A);
        return *this;
    }

    friend ::std::ostream &operator<<(::std::ostream &os, Matrix &p){
        for(size_type i = 0;i < p.row();i++){
            for(size_type j = 0;j < p.column();j++){
                os << p[i][j] << " ";
            }
            os << ::std::endl;
        }
        return os;
    }
};


int main(void) {
    int64 L, A, B, M;
    cin >> L >> A >> B >> M;
    mod = M;
    using Mat = Matrix<ModInt>;
    ModInt ten = ModInt(10);
    int64 a = 1;
    ModInt res(0);
    ModInt nxt(A);
    REP(i, 18) {
        int64 l = (a-1-A), r = (a*10-1-A);
        if (l >= 0) l = l / B + 1;
        else l /= B;
        if (r >= 0) r = r / B + 1;
        else r /= B;
        chmax(l, 0); chmax(r, 0); chmin(r, L);
        int64 num = r-l;
        if (l > L) break;
//        cout << l << " " << r << endl;
        if (num) {
//            cout << l << " " << r << endl;
            Mat m({{ten, ModInt(1), ModInt(0)},
                   {ModInt(0), ModInt(1), ModInt(1)},
                   {ModInt(0), ModInt(0), ModInt(1)}});
            Mat x({{res}, {ModInt(nxt)},{ModInt(B)}});
            Mat ret = m.pow(num);
            ret = ret*x;
            res = ret[0][0];
            nxt = ret[1][0];
        }
        a *= 10;
        ten *= ModInt(10);
    }
    cout << res << endl;
}

Submission Info

Submission Time
Task F - Takahashi's Basics in Education and Learning
User maze1230
Language C++14 (GCC 5.4.1)
Score 600
Code Size 10833 Byte
Status
Exec Time 2 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 600 / 600 sample_01.txt, sample_02.txt, sample_03.txt, sub1_killer_01.txt, sub1_killer_02.txt, sub1_killer_03.txt, sub1_killer_04.txt, sub1_killer_05.txt, sub1_killer_06.txt, sub1_killer_07.txt, sub1_large_01.txt, sub1_large_02.txt, sub1_large_03.txt, sub1_large_04.txt, sub1_large_05.txt, sub1_large_06.txt, sub1_large_07.txt, sub1_large_08.txt, sub1_large_09.txt, sub1_rand_01.txt, sub1_rand_02.txt, sub1_rand_03.txt, sub1_rand_04.txt, sub1_rand_05.txt, sub1_rand_06.txt, sub1_rand_07.txt, sub1_rand_08.txt, sub1_rand_09.txt, sub1_rand_10.txt, sub1_small_01.txt, sub1_small_02.txt, sub1_small_03.txt, sub1_small_04.txt, sub1_small_05.txt, sub1_small_06.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sub1_killer_01.txt 1 ms 256 KB
sub1_killer_02.txt 1 ms 256 KB
sub1_killer_03.txt 2 ms 256 KB
sub1_killer_04.txt 1 ms 256 KB
sub1_killer_05.txt 1 ms 256 KB
sub1_killer_06.txt 1 ms 256 KB
sub1_killer_07.txt 1 ms 256 KB
sub1_large_01.txt 2 ms 256 KB
sub1_large_02.txt 1 ms 256 KB
sub1_large_03.txt 1 ms 256 KB
sub1_large_04.txt 2 ms 256 KB
sub1_large_05.txt 2 ms 256 KB
sub1_large_06.txt 2 ms 256 KB
sub1_large_07.txt 2 ms 256 KB
sub1_large_08.txt 2 ms 256 KB
sub1_large_09.txt 2 ms 256 KB
sub1_rand_01.txt 1 ms 256 KB
sub1_rand_02.txt 1 ms 256 KB
sub1_rand_03.txt 1 ms 256 KB
sub1_rand_04.txt 1 ms 256 KB
sub1_rand_05.txt 1 ms 256 KB
sub1_rand_06.txt 1 ms 256 KB
sub1_rand_07.txt 2 ms 256 KB
sub1_rand_08.txt 1 ms 256 KB
sub1_rand_09.txt 1 ms 256 KB
sub1_rand_10.txt 1 ms 256 KB
sub1_small_01.txt 1 ms 256 KB
sub1_small_02.txt 1 ms 256 KB
sub1_small_03.txt 1 ms 256 KB
sub1_small_04.txt 1 ms 256 KB
sub1_small_05.txt 1 ms 256 KB
sub1_small_06.txt 1 ms 256 KB