結果
問題 | No.1172 Add Recursive Sequence |
ユーザー |
![]() |
提出日時 | 2020-08-28 14:21:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 324 ms / 4,000 ms |
コード長 | 1,812 bytes |
コンパイル時間 | 3,483 ms |
コンパイル使用メモリ | 197,848 KB |
最終ジャッジ日時 | 2025-01-13 16:05:18 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep2(i, m, n) for(int i=int(m); i<int(n); ++i) #define rep(i, n) rep2(i, 0, n) struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; const int MOD = int(1e9) + 7; template<int MOD> struct ModInt { int x; ModInt(int _x = 0) : x( (0 <= _x && _x < MOD) ? _x : (_x%MOD+MOD)%MOD ) {} constexpr ModInt operator-() const noexcept { return ModInt(MOD-x); } constexpr ModInt operator+(const ModInt y) const noexcept { return ModInt(*this) += y; } constexpr ModInt operator-(const ModInt y) const noexcept { return ModInt(*this) -= y; } constexpr ModInt operator*(const ModInt y) const noexcept { return ModInt(*this) *= y; } constexpr ModInt &operator+=(const ModInt y) noexcept { x += y.x; if (x >= MOD) x -= MOD; return *this; } constexpr ModInt &operator-=(const ModInt y) noexcept { x -= y.x; if (x < 0) x += MOD; return *this; } constexpr ModInt &operator*=(const ModInt y) noexcept { x = ll(x) * y.x % MOD; return *this; } }; using mint = ModInt<MOD>; istream &operator>>(istream &is, mint &a) { return is >> a.x; } ostream &operator<<(ostream &os, const mint &a) { return os << a.x; } int main() { int k, n, m; cin >> k >> n >> m; vector<mint> a(n), c(k+1); c[0] = -1; rep(i, k) cin >> a[i]; rep(i, k) cin >> c[i+1]; rep2(i, k, n) rep2(j, 1, k+1) a[i] += c[j]*a[i-j]; vector<array<int, 2>> Qs(m); rep(i, m) cin >> Qs[i][0] >> Qs[i][1]; vector<mint> b(n+1), p(n+k+1); rep(i, k) { rep(j, n) b[j] = b[j+1] + c[i]*a[j]; for (auto &[l, r] : Qs) { p[l+i] += b[0]; p[r+i] -= b[r-l]; } } rep(i, n) { rep2(j, 1, min(k, i)+1) p[i] -= c[j]*p[i-j]; p[i] = -p[i]; cout << p[i] << '\n'; } }