AtCoder Beginner Contest 469 : G - K-nacci Operations

そういう行列累乗だったか…。
https://atcoder.jp/contests/abc469/tasks/abc469_g

問題

a,bで構成されるK個の文字列S[i]が与えられる。
また、S[K+1]以降は、直前のK個の文字列を連結したものとなる。

文字列Tに対し、ある文字列S[i]に応じた処理を行うと、以下が生じる。S[i]の先頭から１文字ずつ見て行ったとき、

• 'a'ならTを１文字左回転する
• 'b'ならTを反転する

Tに対しS[N]に応じた処理を行ったあとの文字列を答えよ。

解法

Tの状態としては、

• 何文字回転したか
• 反転の有無

の２つの状態で表せる。また、２つの文字列があったとき、それらを連結した文字列に応じた処理は、この２つの状態を合成して容易に求められる。
あとは、S[N]に対応する文字列をどう合成するかである。
ここで重要なのは反転の有無は周期が(K+1)となることである。
あとは回転数を求められれば良い。
S[(K+1)n+1]～S[(K+1)n+K+1]の回転数がわかっているとき、S[(K+1)(n+1)+1]～S[(K+1)(n+1)+K+1]の回転数は前述の回転数の加減算で計算できるので、行列累乗に持ち込もう。

int K;

ll N;
int L;
string T;
string S[101];
int A[102];
int B[302];

const int MAT=203;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};
ll mo;

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	FOR(i,K) cin>>S[i];
	cin>>N>>T;
	mo=L=T.size();
	FOR(i,K) {
		x=0;
		y=0;
		FORR(c,S[i]) {
			if(c=='a') {
				if(y==0) x++;
				else x--;
			}
			else {
				y=1-y;
			}
		}
		A[i]=(x%L+L)%L;
		B[i]=y;
	}
	for(i=K-1;i>=0;i--) {
		if(B[K]==0) {
			A[K]=(A[K]+A[i])%L;
			B[K]=B[i];
		}
		else {
			A[K]=(A[K]-A[i]+L)%L;
			B[K]=B[i]^1;
		}
	}
	
	Mat C;
	FOR(i,K+1) C.v[i][i]=1;
	
	for(y=K+1;y<=2*K+2;y++) {
		int turn=0;
		B[y]=B[y-(K+1)];
		for(i=1;i<=K;i++) {
			FOR(x,K+1) {
				if(turn==0) (C.v[y][x]+=C.v[y-i][x])%=mo;
				else (C.v[y][x]+=mo-C.v[y-i][x])%=mo;
			}
			turn^=B[y-i];
		}
	}
	FOR(y,K+1) FOR(x,K+1) C.v[y][x]=C.v[y+K+1][x];
	N--;
	C=powmat(N/(K+1),C,K+1);
	y=N%(K+1);
	ll ret=0;
	FOR(x,K+1) {
		(ret+=C.v[y][x]*A[x])%=mo;
	}
	rotate(T.begin(),T.begin()+(ret%mo),T.end());
	if(B[y]) reverse(ALL(T));
	cout<<T<<endl;
	
	
	
	
}

まとめ

行列累乗で１要素ずつ求めるのではなく、(K+1)要素ずつ求めるのは割と珍しいかも。