結果

問題 No.1097 Remainder Operation
ユーザー miscalcmiscalc
提出日時 2023-11-20 20:28:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 3,512 bytes
コンパイル時間 4,374 ms
コンパイル使用メモリ 265,176 KB
実行使用メモリ 9,048 KB
最終ジャッジ日時 2023-11-20 20:28:26
合計ジャッジ時間 10,472 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 23 ms
6,676 KB
testcase_08 AC 23 ms
6,676 KB
testcase_09 AC 23 ms
6,676 KB
testcase_10 AC 22 ms
6,676 KB
testcase_11 AC 23 ms
6,676 KB
testcase_12 AC 217 ms
6,676 KB
testcase_13 AC 217 ms
6,676 KB
testcase_14 AC 219 ms
6,676 KB
testcase_15 AC 218 ms
6,676 KB
testcase_16 AC 217 ms
6,676 KB
testcase_17 AC 228 ms
6,676 KB
testcase_18 AC 210 ms
6,744 KB
testcase_19 AC 228 ms
9,048 KB
testcase_20 AC 215 ms
9,048 KB
testcase_21 AC 208 ms
6,744 KB
testcase_22 AC 207 ms
6,744 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using tlll = tuple<ll, ll, ll>;
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll safemod(ll A, ll M) {ll res = A % M; if (res < 0) res += M; return res;}
ll divfloor(ll A, ll B) {if (B < 0) A = -A, B = -B; return (A - safemod(A, B)) / B;}
ll divceil(ll A, ll B) {if (B < 0) A = -A, B = -B; return divfloor(A + B - 1, B);}
template<class T> void unique(vector<T> &V) {V.erase(unique(V.begin(), V.end()), V.end());}
template<class T> void sortunique(vector<T> &V) {sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end());}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)
template<class T> void printvec(const vector<T> &V) {int _n = V.size(); for (int i = 0; i < _n; i++) cout << V[i] << (i == _n - 1 ? "" : " ");cout << '\n';}
template<class T> void printvect(const vector<T> &V) {for (auto v : V) cout << v << '\n';}
template<class T> void printvec2(const vector<vector<T>> &V) {for (auto &v : V) printvec(v);}
//*
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;
//*/

/*
x[0] = start, x[i+1] = next_index(x[i]) の漸化式で定まるインデックス列に対して
get(x[0]) op … op get(x[K-1]) を求める (K はクエリで渡される)
Index: x_i の型
Data: 求める値の型、モノイド
  op: 結合則を満たす演算
  e: 単位元
  power(b, t) = b^t = b op … op b (t 回)
計算量: 前計算 O(周期)、クエリ O(1)
*/
template <typename Index, typename Data, Index (*next_index)(Index), Data (*get)(Index), Data (*op)(Data, Data), Data (*e)(), Data (*power)(Data, ll)>
struct Period
{
private:
  vector<Data> dat, prod_head, prod_tail;
  int lambda, mu;
  Data head, tail;

public:
  Period(Index start)
  {
    Index a = start, b = start;
    do
    {
      dat.emplace_back(get(a));
      a = next_index(a);
      b = next_index(next_index(b));
    } while (a != b);
    mu = dat.size();
    Index c = start;
    while (a != c)
    {
      dat.emplace_back(get(a));
      a = next_index(a);
      c = next_index(c);
    }
    lambda = (int)dat.size() - mu;

    prod_head.resize((int)dat.size() + 1);
    prod_tail.resize((int)dat.size() + 1);
    prod_head[0] = e(), prod_tail[lambda] = e();
    for (int i = 1; i < (int)prod_head.size(); i++)
      prod_head[i] = op(prod_head[i - 1], dat[i - 1]);
    for (int i = lambda + 1; i < (int)prod_tail.size(); i++)
      prod_tail[i] = op(prod_tail[i - 1], dat[i - 1]);

    head = prod_head[lambda];
    tail = prod_tail[lambda + mu];
  }

  Data query(ll k)
  {
    if (k <= (int)dat.size())
      return prod_head[k];

    Data mid = prod_tail[lambda + (k - lambda) % mu];
    return op(op(head, power(tail, (k - lambda) / mu)), mid);
  }
};

ll N;
vector<ll> A;
ll next_index(ll i) { return (i + A.at(i)) % N; }
ll get(ll i) { return A.at(i); }
ll op(ll a, ll b) { return a + b; }
ll e() { return 0; }
ll power(ll a, ll t) { return t * a; }

int main()
{
  cin >> N;
  A.resize(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }

  Period<ll, ll, next_index, get, op, e, power> pe(0);
  ll Q;
  cin >> Q;
  while (Q--)
  {
    ll K;
    cin >> K;
    cout << pe.query(K) << endl;
  }
}
0