結果

問題 No.1580 I like Logarithm！
ユーザー GraphiumGraphium
提出日時 2021-07-02 22:22:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 106 ms / 2,000 ms
コード長 10,438 bytes
コンパイル時間 3,211 ms
コンパイル使用メモリ 221,828 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-11 22:28:54
合計ジャッジ時間 7,953 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 41 ms
4,380 KB
testcase_07 AC 101 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 8 ms
4,380 KB
testcase_10 AC 13 ms
4,376 KB
testcase_11 AC 62 ms
4,380 KB
testcase_12 AC 69 ms
4,376 KB
testcase_13 AC 55 ms
4,376 KB
testcase_14 AC 99 ms
4,376 KB
testcase_15 AC 77 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 106 ms
4,380 KB
testcase_27 AC 105 ms
4,376 KB
testcase_28 AC 105 ms
4,376 KB
testcase_29 AC 105 ms
4,380 KB
testcase_30 AC 105 ms
4,376 KB
testcase_31 AC 104 ms
4,376 KB
testcase_32 AC 105 ms
4,376 KB
testcase_33 AC 101 ms
4,376 KB
testcase_34 AC 105 ms
4,376 KB
testcase_35 AC 103 ms
4,380 KB
testcase_36 AC 105 ms
4,380 KB
testcase_37 AC 105 ms
4,376 KB
testcase_38 AC 104 ms
4,380 KB
testcase_39 AC 105 ms
4,376 KB
testcase_40 AC 104 ms
4,380 KB
testcase_41 AC 104 ms
4,380 KB
testcase_42 AC 104 ms
4,380 KB
testcase_43 AC 104 ms
4,376 KB
testcase_44 AC 105 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include <atcoder/all>  //atcoder
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// using namespace atcoder;  // atcoder
// using mint = mint1000000007;  // atcoder
// using mint = static_modint<1000>;
template <typename T>
using vec = vector<T>;
template <typename T>
using vec2 = vec<vec<T>>;
template <typename T>
using pq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vi2 = vector<vector<ll>>;
using si = set<ll>;
using pii = pair<ll, ll>;
using pdd = pair<long double, long double>;
using mii = map<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1ll << 60;
const long double LPI = acos(-1.0);
const double PI = acos(-1.0);
ll mod = 1000000007;

#define MP(a, b) make_pair((a), (b))
#define MT(...) make_tuple(__VA_ARGS__)
#define sz(x) (int)(x).size()

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, x) for (ll i = 0; i < (int)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (ll i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((int)(x)); i > 0; i--)

#define endl "\n"
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SORT(v) sort(ALL(v));
#define RSORT(v) sort(RALL(v));
#define REV(v) reverse(ALL(v))
#define IN(type, a) \
    type a;         \
    cin >> a;
#define LN(a) \
    ll a;     \
    cin >> a;
#define VIN(type, a, n) \
    vector<type> a(n);  \
    cin >> a;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define COUT(x) cout << (x) << endl;
#define CERR(x) cerr << (x) << endl;
#define DCOUT(x, n) cout << fixed << setprecision(n) << (x) << endl;
#define ENDL cout << endl;
#define SP cout << " ";
#define Dump(x) cout << #x << " : " << x << endl;
#define PB(x) emplace_back(x)

#define HOGE COUT("HOGE")
#define AJA COUT("AJA")

template <typename T>
inline T max(vector<T> &v) {
    return *max_element(v.begin(), v.end());
}
template <typename T>
inline T min(vector<T> &v) {
    return *min_element(v.begin(), v.end());
}
template <typename T>
istream &operator>>(istream &i, vector<T> &v) {
    REP(j, sz(v)) i >> v[j];
    return i;
}
template <typename T>
string join(const vector<T> &v, const string &d = "") {
    stringstream s;
    REP(i, sz(v))(i ? s << d : s) << v[i];
    return s.str();
}
template <typename T>
ostream &operator<<(ostream &o, const vector<T> &v) {
    if (sz(v)) o << join(v, " ");
    return o;
}
template <typename T1, typename T2>
istream &operator>>(istream &i, pair<T1, T2> &v) {
    return i >> v.fi >> v.se;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &o, const pair<T1, T2> &v) {
    return o << v.fi << "," << v.se;
}

template <typename T>
inline bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T>
inline bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T>
inline T gcd(T a, T b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
template <typename T>
inline T lcm(T a, T b) {
    return a * b / gcd(a, b);
}
template <typename T>
inline bool isPrime(T a) {
    if (a <= 1) {
        return false;
    }
    for (T i = 2; i * i <= a; i++) {
        if (a % i == 0) {
            return false;
        }
    }
    return true;
}
template <typename T>
inline T ord(T p, T n) {
    T ans = 0;
    while (n % p == 0) {
        n /= p;
        ans++;
    }
    return ans;
}
template <typename T>
struct Matrix {
    vector<vector<T>> m;
    ll h = 0;
    ll w = 0;
    inline Matrix(ll h_, ll w_)
        : m(vector<vector<T>>(h_, vector<T>(w_, 0))), h(h_), w(w_) {}
    inline Matrix(ll h_, ll w_, ll v_)
        : m(vector<vector<T>>(h_, vector<T>(w_, v_))), h(h_), w(w_) {}
    inline Matrix(vector<T> v) : m(vector<vector<T>>(v.size(), vector<T>(1))) {
        h = v.size();
        w = 1;
        REP(i, h) { m[i][0] = v[i]; }
    }
    inline Matrix(vector<vector<T>> v) : m(v) {
        h = v.size();
        w = v[0].size();
    }

    inline vector<T> operator[](const ll i) const { return m[i]; }  //読み取り
    inline vector<T> &operator[](const ll i) { return m[i]; }  //書き込み
    inline Matrix &operator=(const Matrix &other) {
        h = other.h;
        w = other.w;
        m = other.m;
        return *this;
    }
    inline Matrix operator+(const Matrix &other) {
        assert(h == other.h && w == other.w);
        Matrix<T> res(h, w);
        REP(i, h) REP(j, w) res.m[i][j] = m[i][j] + other.m[i][j];
        return res;
    }
    inline Matrix operator-(const Matrix &other) {
        assert(h == other.h && w == other.w);
        Matrix<T> res(h, w);
        REP(i, h) REP(j, w) res.m[i][j] = m[i][j] - other.m[i][j];
        return res;
    }
    inline Matrix operator*(const Matrix &other) {
        assert(w = other.h);
        Matrix<T> res(h, other.w);
        REP(i, h) {
            REP(j, other.w) {
                REP(k, w) { res.m[i][j] += m[i][k] * other.m[k][j]; }
            }
        }
        return res;
    }
    inline Matrix &operator+=(const Matrix &other) {
        assert(h == other.h && w == other.w);
        REP(i, h) REP(j, w) m[i][j] += other.m[i][j];
        return *this;
    }
    inline Matrix &operator-=(const Matrix &other) {
        assert(h == other.h && w == other.w);
        REP(i, h) REP(j, w) m[i][j] -= other.m[i][j];
        return *this;
    }
    inline Matrix &operator*=(const Matrix &other) {
        *this = *this * other;
        return *this;
    }
    inline void show() {
        REP(i, h) {
            REP(j, w) {
                cout << m[i][j];
                if (j < w - 1) cout << " ";
            }
            ENDL;
        }
    }
};

template <typename T>
inline Matrix<T> RotMat2(ld t) {
    vector<T> v = {{cos(t), -sin(t)}, {sin(t), cos(t)}};
    Matrix<T> res(v);
}

template <typename T>
inline Matrix<T> RotMat3(ld t, ll a) {
    // x軸:0 y軸:1 z軸:3
    Matrix<T> res(3, 3);
    res[a][a] = 1;
    res[(a + 1) % 3][(a + 1) % 3] = cos(t);
    res[(a + 1) % 3][(a + 2) % 3] = -sin(t);
    res[(a + 2) % 3][(a + 1) % 3] = sin(t);
    res[(a + 2) % 3][(a + 2) % 3] = cos(t);
    return res;
}

template <typename T>
inline Matrix<T> DiagMat(ll n, T v) {
    Matrix<T> res(n, n);
    REP(i, n) res[i][i] = v;
    return res;
}

template <typename T>
inline Matrix<T> pow(Matrix<T> m, ll n) {
    if (n == 0) return DiagMat(m.h, 1ll);
    auto res = pow(m, n / 2);
    res *= res;
    if (n % 2 == 1) res *= m;
    return res;
}
struct mint {
    ll x;
    inline mint(ll x_ = 0) : x((x_ % mod + mod) % mod) {}
    inline mint &operator=(const mint &other) {
        x = other.x;
        return *this;
    }
    template <typename T>
    inline mint &operator=(const T &other) {
        *this = mint(other);
        return *this;
    }
    inline mint operator+() { return *this; }
    inline mint operator-() { return mint(-x); }
    inline mint &operator+=(const mint &other) {
        if ((x += other.x) >= mod) x -= mod;
        return *this;
    }
    template <typename T>
    inline mint &operator+=(const T &other) {
        *this += mint(other);
        return *this;
    }
    inline mint &operator-=(const mint &other) { return *this += -mint(other); }
    template <typename T>
    inline mint &operator-=(const T &other) {
        *this -= mint(other);
        return *this;
    }
    inline mint &operator*=(const mint &other) {
        (x *= other.x) %= mod;
        return *this;
    }
    template <typename T>
    inline mint &operator*=(const T &other) {
        *this *= mint(other);
        return *this;
    }
    template <typename T>
    inline mint operator+(const T &other) {
        return mint(*this) += mint(other);
    }
    template <typename T>
    inline mint operator-(const T &other) {
        return mint(*this) -= mint(other);
    }
    template <typename T>
    inline mint operator*(const T &other) {
        return mint(*this) *= mint(other);
    }
    inline mint pow(ll n) {
        if (n == 0) return mint(1);
        mint res = pow(n / 2);
        res *= res;
        if (n % 2 == 1) res *= *this;
        return res;
    }
    inline mint inv() { return pow(mod - 2); }
    inline mint &operator/=(const mint &other) {
        return *this *= mint(other).inv();
    }
    inline mint operator/(const mint &other) { return mint(*this) /= other; }
    inline mint operator++() {
        *this += 1;
        return *this;
    }
    inline mint operator++(int) {
        const mint res = *this;
        ++(*this);
        return res;
    }
    inline mint operator--() {
        *this -= 1;
        return *this;
    }
    inline mint operator--(int) {
        const mint res = *this;
        --(*this);
        return res;
    }
    inline bool operator==(const mint &other) { return x == other.x; }
    inline bool operator!=(const mint &other) { return !(*this == other); }
    inline bool operator<(const mint &other) { return *this < other; }
};
inline istream &operator>>(istream &is, mint &x) {
    is >> x.x;
    x.x = (x.x % mod + mod) % mod;
    return is;
}
inline ostream &operator<<(ostream &os, const mint &x) { return os << x.x; }

inline mint modPow(ll x, ll n) { return mint(x).pow(n); }

template <typename T>
inline mint modFact(T n) {
    mint res(1);
    for (T i = n; n > 0; i--) res *= mint(i);
    return res;
}

template <typename T>
mint modComb(T n, T r) {
    mint res(1);
    for (T i = 0; i < r; i++) {
        res *= mint(n - i);
    }
    for (T i = 1; i <= r; i++) {
        res /= mint(i + 1);
    }
    return res;
}
///////////////////////////////////////////////////////////////////////ここから
inline void solve() {
    IN(mint, a);
    IN(string, s);
    REV(s);
    mint ans = 0;
    ll l = s.size();
    for (mint i = 0; i.x < l - 1; i++) {
        ans += i * (a - 1) * modPow(a.x, i.x);
    }

    for (mint i = 0; i.x < s.size(); i++) {
        ans += mint(l - 1) * mint(s[i.x] - '0') * modPow(a.x, i.x);
    }
    ans -= mint(l - 1) * (modPow(a.x, l - 1) - 1);
    COUT(ans)
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}
0