AtCoder ARC #099 : F - Eating Symbols Hard

このテクは思いつかなかった。
https://arc099.contest.atcoder.jp/tasks/arc099_d

問題

無限の大きさの数列Aが与えられる。
Aの初期値は0であり、添え字は負の値も許容される。
初期状態で添え字p=0とする。

ここで""><+-"で構成された文字列を左から順に処理することを考える。
各文字に対し、以下のように数列や変数が変化する。

• "+""-"に対しA[p]がインクリメント・デクリメントされる。
• ">""<"に対しpがインクリメント・デクリメントされる。

文字列Sが与えられる。
Sの部分列の組で上記処理結果が等しくなるものは何通りか。

解法

数列Aを、Xの多項式の引数と見なそう。
すなわちf(X) = sum(A[p] * X^p)を考える。

上記文字列は、多項式に対する関数とみなすことができる。
文字列Sに対応する関数をt(S)とすると、

• t("+" + S) = t(S) + 1
• t("-" + S) = t(S) - 1
• t(">" + S) = t(S) * X^(-1)
• t("-" + S) = t(S) * X

t(S)は、あくまでXを引数とした関数ではない。
t(S)(p) = Ap+B (A,BはXの多項式)の形で表現できる。

そこでSの部分文字列S'に対し、t(S')における(A,B)が等しい対を数え上げればよいが、A,BはS'|次の式になりうるので、それをO(|S|)個覚えるとMLEする。
そこで、A,B多項式そのものを持つわけではなく、いくつかのXに対するA,Bの値だけを覚えるようにしよう。
そうすると多項式1個に対し覚えるべき情報が何通りかの値だけで済み、MLEしないようになる。

int N;
string S;
ll mo=1000000007;
vector<ll> C,R;
const int PAT=5;
vector<ll> A[PAT];
vector<ll> B[PAT];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	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>>S;
	srand(time(NULL));
	FOR(i,PAT) {
		C.push_back(rand()%10000000+10000000);
		R.push_back(modpow(C.back()));
		A[i].push_back(1);
		B[i].push_back(0);
	}
	reverse(ALL(S));
	FORR(c,S) {
		FOR(i,PAT) {
			if(c=='+') {
				A[i].push_back(A[i].back());
				B[i].push_back((B[i].back()+1)%mo);
			}
			if(c=='-') {
				A[i].push_back(A[i].back());
				B[i].push_back((B[i].back()+mo-1)%mo);
			}
			if(c=='>') {
				A[i].push_back(A[i].back()*C[i]%mo);
				B[i].push_back(B[i].back()*R[i]%mo);
			}
			if(c=='<') {
				A[i].push_back(A[i].back()*R[i]%mo);
				B[i].push_back(B[i].back()*C[i]%mo);
			}
		}
	}
	ll ret=0;
	map<vector<ll>,int> memo;
	memo[vector<ll>(PAT,0)]++;
	FOR(j,N) {
		vector<ll> BA(PAT),BAS(PAT);
		FOR(i,PAT) {
			BA[i]=B[i][j+1]*A[i][j+1]%mo;
			BAS[i]=(B[i][j+1]+mo-B[i].back())*A[i][j+1]%mo;
		}
		ret+=memo[BAS];
		memo[BA]++;
	}
	cout<<ret<<endl;
}

まとめ

これ定番テクなのかな…。