square869120Contest #1 : E - 散歩

あれ？
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にしては簡単すぎる。
もっとややこしい想定解考えてたのかな？