結果
| 問題 |
No.1489 Repeat Cumulative Sum
|
| コンテスト | |
| ユーザー |
 suisen
|
| 提出日時 | 2021-04-23 22:21:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 52 ms / 2,000 ms |
| コード長 | 6,473 bytes |
| コンパイル時間 | 2,485 ms |
| コンパイル使用メモリ | 198,636 KB |
| 最終ジャッジ日時 | 2025-01-21 00:04:59 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
#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;
}