結果
| 問題 | No.1489 Repeat Cumulative Sum |
| ユーザー |
 suisen
|
| 提出日時 | 2021-04-23 22:11:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,459 bytes |
| コンパイル時間 | 2,535 ms |
| コンパイル使用メモリ | 198,416 KB |
| 最終ジャッジ日時 | 2025-01-20 23:58:20 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 1 WA * 26 |
ソースコード
#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, 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;}