あれ?
http://s8pc-1.contest.atcoder.jp/tasks/s8pc_1_e
問題
1~N番のN個の町が並んでいる。
各町はパラメータA[i]を持つ。
町(i-1)とiの間の距離はA[i-1]^A[i]である。
町1から初めて、町C[i]に順に訪問し、最後また町1に戻りたい。
移動距離はいくらか。
解法
各町の町1からの距離を最初に累積和で求めておこう。
そうするとあとは町C[i]とC[i+1]の間の距離を足しこむだけ。
int N,Q; int A[151515]; ll S[151515]; ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) cin>>A[i]; S[1]=0; FOR(i,N-1) { (S[i+2]=S[i+1]+modpow(A[i],A[i+1]))%=mo; } ll ret=0; int cur=1; FOR(i,Q+1) { if(i==Q) j=1; else cin>>j; ret+=S[max(j,cur)]-S[min(j,cur)]+mo; cur=j; } cout<<ret%mo<<endl; }
まとめ
Eにしては簡単すぎる。
もっとややこしい想定解考えてたのかな?