結果
問題 |
No.1097 Remainder Operation
|
ユーザー |
![]() |
提出日時 | 2022-11-12 15:51:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 247 ms / 2,000 ms |
コード長 | 1,695 bytes |
コンパイル時間 | 2,345 ms |
コンパイル使用メモリ | 201,044 KB |
最終ジャッジ日時 | 2025-02-08 19:49:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename Monoid,int LOG> class Doubling{ using X=typename Monoid::value_type; int n; bool is_prepared; using P=pair<int,X>; static constexpr P unit={-1,Monoid::unit()}; vector<vector<P>> DP; P k_move(const P&a,int k){ if(a.first==-1)return a; const auto [now,val]=a; const auto [nxt,cost]=DP[k][now]; return {nxt,Monoid::op(val,cost)}; } void build(){ is_prepared=true; for(int k=0;k<LOG-1;k++) for(int v=0;v<n;v++) DP[k+1][v]=k_move(DP[k][v],k); } public: Doubling(int n):n(n),is_prepared(false){ DP.assign(LOG, vector<P>(n,unit)); } void add(int from,int to,X x){ assert(!is_prepared); assert(-1<=to and to<n); DP[0][from]={to,x}; } // [終点,値] P calc(int s,long long step){ assert(step<=(1LL<<LOG)); if(!is_prepared)build(); P res{s,Monoid::unit()}; for(int k=0;step;k++,step>>=1) if(step&1)res=k_move(res,k); return res; } }; template<typename X> struct Group_Add { using value_type = X; static constexpr X op(const X &x, const X &y) noexcept { return x + y; } static constexpr X inverse(const X &x) noexcept { return -x; } static constexpr X power(const X &x, long long n) noexcept { return X(n) * x; } static constexpr X unit() { return X(0); } static constexpr bool commute = true; }; using GA=Group_Add<long long>; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n;cin>>n; Doubling<GA,40> db(n); for(int i=0;i<n;i++){ int a;cin>>a; db.add(i,(i+a)%n,a); } int q;cin>>q; while(q--){ long long k;cin>>k; cout<< db.calc(0,k).second <<"\n"; } }