Codeforces #419 Div1 B. Karen and Test

実験でなんとか。
http://codeforces.com/contest/815/problem/B

問題

N要素の整数列Aがある。
隣接要素同士で先頭から和・差・和・差…と交互に取っていくと、(N-1)個の要素が得られる。
この要素からなる数列を考え、さらに作業を繰り返したとき(和と差どちらを取るかは、前の処理の最後の処理で決まる)、最終的に1要素残るときの値を求めよ。

解法

Nが小さいとき、元数列の各要素の何倍が最終的な要素に寄与するか実験してみよう。
Nが4の周期で似たような傾向を示しており、そのうち二項係数が並んでいるだけの箇所が見える。
具体的にはNが4の倍数の時、係数ベクトルをVとするととなっている。

Nが4の倍数以外の場合はここから数回処理を行いVを求め、元のAとの積和を答えればよい。

int N;
ll A[202020];
ll mo=1000000007;

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll hoge(vector<ll> a) {
	int v=1;
	int i;
	string s;
	while(a.size()>1) {
		vector<ll> b;
		FOR(i,a.size()-1) {
			b.push_back((mo+a[i]+v*a[i+1])%mo);;
			v=-v;
		}
		s+=" ";
		swap(a,b);
	}
	return a[0];
}

vector<ll> getP(int N) {
	vector<ll> P;
	int M=N/4*4;
	int i;
	FOR(i,M/2) {
		P.push_back(combi(M/2-1,i));
		P.push_back(mo-combi(M/2-1,i));
	}
	if(M<N) {
		vector<ll> Q;
		M++;
		P.push_back(0);
		Q.push_back(1);
		int v=1;
		FOR(i,M-1) {
			Q.push_back((mo+P[i+1]+v*P[i])%mo);
			v=-v;
		}
		swap(P,Q);
	}
	if(M<N) {
		vector<ll> Q;
		M++;
		P.push_back(0);
		Q.push_back(1);
		FOR(i,M-1) Q.push_back((P[i+1]+P[i])%mo);
		swap(P,Q);
	}
	if(M<N) {
		vector<ll> Q;
		M++;
		P.push_back(0);
		Q.push_back(1);
		int v=1;
		FOR(i,M-1) {
			Q.push_back((mo+P[i+1]+v*P[i])%mo);
			v=-v;
		}
		swap(P,Q);
	}
	return P;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	auto V=getP(N);
	ll ret=0;
	FOR(i,N) {
		ll v;
		cin>>v;
		ret += v*V[i];
		ret = (ret%mo+mo)%mo;
	}
	cout<<ret<<endl;
	
}

まとめ

コードはともかく、規則性に気づくまでしんどいから1250ptなのかな。