結果

問題 No.1489 Repeat Cumulative Sum
ユーザー suisensuisen
提出日時 2021-04-23 22:21:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 6,473 bytes
コンパイル時間 2,083 ms
コンパイル使用メモリ 207,236 KB
実行使用メモリ 6,004 KB
最終ジャッジ日時 2024-07-04 08:15:20
合計ジャッジ時間 3,527 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 32 ms
5,428 KB
testcase_04 AC 29 ms
5,376 KB
testcase_05 AC 33 ms
5,376 KB
testcase_06 AC 26 ms
5,376 KB
testcase_07 AC 19 ms
5,376 KB
testcase_08 AC 12 ms
5,376 KB
testcase_09 AC 39 ms
5,680 KB
testcase_10 AC 31 ms
5,376 KB
testcase_11 AC 26 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 24 ms
5,376 KB
testcase_14 AC 41 ms
5,992 KB
testcase_15 AC 39 ms
5,808 KB
testcase_16 AC 21 ms
5,376 KB
testcase_17 AC 23 ms
5,376 KB
testcase_18 AC 18 ms
5,376 KB
testcase_19 AC 11 ms
5,376 KB
testcase_20 AC 16 ms
5,376 KB
testcase_21 AC 27 ms
5,376 KB
testcase_22 AC 4 ms
5,376 KB
testcase_23 AC 10 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 7 ms
5,376 KB
testcase_26 AC 43 ms
6,004 KB
testcase_27 AC 25 ms
5,376 KB
testcase_28 AC 4 ms
5,376 KB
testcase_29 AC 19 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <type_traits>
#include <cassert>
#include <bits/stdc++.h>

using namespace std;

using int128 = __int128_t;

#define rep(i, n)         for (int i = 0; i < n; ++i)
#define reps(i, n, s)     for (int i = 0; i < n; i += s)
#define repl(i, l, r)     for (int i = l; i < r; ++i)
#define repsl(i, l, r, s) for (int i = l; i < r; i += s)

#define all(iterable) (iterable).begin(), (iterable).end()

constexpr int dx4[4] = {1, 0, -1, 0};
constexpr int dy4[4] = {0, 1, 0, -1};

constexpr int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
constexpr int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

template <typename T>
void print(const vector<T>& vec, const string sep = " ", const string end = "\n") {
    int n = vec.size();
    rep(i, n) {
        cout << vec[i];
        if (i < n - 1) cout << sep;
        else cout << end;
    }
}

template <typename T>
void read(vector<T>& a, int begin_index, int length) {
    if (a.size() < begin_index + length) a.resize(begin_index + length);
    while (length --> 0) cin >> a[begin_index++];
}
template <typename T>
void read(vector<T>& a) { read(a, 0, a.size()); }


template <int mod> class modint {
    public:
        modint(): _v(0) {}
        template <typename T> modint(T x) {
            T v = x % mod;
            if (v < 0) v += mod;
            _v = v;
        }

        unsigned int val() const { return _v; }

        modint& operator+=(const modint& x) { _v = add(_v, x._v); return *this; }
        modint& operator-=(const modint& x) { _v = sub(_v, x._v); return *this; }
        modint& operator*=(const modint& x) { _v = mul(_v, x._v); return *this; }
        modint& operator/=(const modint& x) { _v = mul(_v, inv(x._v)); return *this; }

        friend modint operator+(const modint& x, const modint& y) { return modint(x) += y; }
        friend modint operator-(const modint& x, const modint& y) { return modint(x) -= y; }
        friend modint operator*(const modint& x, const modint& y) { return modint(x) *= y; }
        friend modint operator/(const modint& x, const modint& y) { return modint(x) /= y; }

        modint& operator++() {
            ++_v;
            if (_v == mod) _v = 0;
            return *this;
        }
        modint& operator--() {
            if (_v == 0) _v = mod;
            --_v;
            return *this;
        }
        modint operator++(int) {
            modint res = modint(_v);
            ++*this;
            return res;
        }
        modint operator--(int) {
            modint res = modint(_v);
            --*this;
            return res;
        }
        modint operator+() const { return modint(_v); }
        modint operator-() const { return modint(mod - _v); }

        bool operator==(const modint& x) const { return _v == x._v; }
        bool operator!=(const modint& x) const { return _v != x._v; }
        bool operator!() const noexcept { return _v > 0; }

        modint inv() const { return inv(_v); }

        modint pow(long long x, bool accept_negative_power = false) const {
            bool negative_power = false;
            if (accept_negative_power) {
                if (x < 0) {
                    negative_power = true;
                    x = -x;
                }
            } else {
                assert(x >= 0);
            }
            modint res = 1, pw2 = _v;
            for (; x > 0; x >>= 1) {
                if (x & 1) res *= pw2;
                pw2 *= pw2;
            }
            return negative_power ? 1 / res : res;
        }

        static constexpr unsigned int safe_mod(const long long v) {
            long long z = v % (long long) mod;
            if (z < 0) z += mod;
            return (unsigned int) z;
        }
    private:
        unsigned int _v;
        static constexpr unsigned int add(const unsigned int x, const unsigned int y) {
            unsigned int z = x + y;
            if (z >= mod) z -= mod;
            return z;
        }
        static constexpr unsigned int sub(const unsigned int x, const unsigned int y) {
            return x < y ? x + mod - y : x - y;
        }
        static constexpr unsigned int mul(const unsigned int x, const unsigned int y) {
            return (unsigned int) ((unsigned long long) x * y % mod);
        }
        static constexpr unsigned int inv(const unsigned int x) {
            long long a = x, b = mod, u = 1, v = 0;
            long long tmp;
            while (b) {
                long long t = a / b;
                a -= t * b; tmp = a; a = b; b = tmp;
                u -= t * v; tmp = u; u = v; v = tmp;
            }
            return safe_mod(u);
        }
};
template <typename T, typename U = T> class factorial {
    public:
        factorial(size_t initial_max) : _sz(initial_max + 1) {
            _fac.resize(_sz);
            _fac_inv.resize(_sz);
            _fac[0] = _fac_inv[0] = 1;
            additional_calc(1, _sz);
        }
        const T& fac(const size_t i) { ensure_size(i + 1); return _fac[i]; }
        const U& fac_inv(const size_t i) { ensure_size(i + 1); return _fac_inv[i]; }
        U binom(const int n, const int r) {
            if (n < 0 or r < 0 or n < r) return 0;
            ensure_size(n + 1);
            return _fac[n] * _fac_inv[r] * _fac_inv[n - r];
        }
        U perm(const int n, const int r) {
            if (n < 0 or r < 0 or n < r) return 0;
            ensure_size(n + 1);
            return _fac[n] * _fac_inv[n - r];
        }
    private:
        size_t _sz;
        std::vector<T> _fac;
        std::vector<U> _fac_inv;
        void additional_calc(const size_t l, const size_t r) {
            assert(l > 0);
            for (size_t i = l; i < r; ++i) _fac[i] = _fac[i - 1] * i;
            _fac_inv[r - 1] = (U) 1 / _fac[r - 1];
            for (size_t i = r - 1; i > l; --i) _fac_inv[i - 1] = _fac_inv[i] * i;
        }
        void ensure_size(const size_t sz) {
            if (sz < _sz) return;
            size_t new_size = std::max(sz, _sz * 2);
            _fac.resize(new_size);
            _fac_inv.resize(new_size);
            additional_calc(_sz, new_size);
            _sz = new_size;
        }
};


using mint = modint<1000000007>;

int main() {
    int n;
    long long m;
    cin >> n >> m;
    --n, --m;
    vector<long long> a(n);
    read(a);
    factorial<mint> fac(n);
    mint num = m + 1;
    mint ans = 0;
    rep(k, n) {
        ans += a[n - k - 1] * num * fac.fac_inv(k + 1);
        num *= (m + k + 2);
    }
    cout << ans.val() << '\n';
    return 0;
}
0