LeetCode Weekly Contest 421 : 3337. Total Characters in String After Transformations II

これは★8も要らないな…。
https://leetcode.com/problems/total-characters-in-string-after-transformations-ii/description/

問題

文字列に対し1回変換処理を行うと、各文字がどのような文字列に置き換わるか、という情報が与えられる。
文字列Sに対しN回変換を行うと、最終的な文字列長は何通りか。

解法

変換処理により、どの文字がどの文字群何個に変換されるかを行列Aで持つとする。
A^Nを求めて、S中の各文字の登場回数からなるベクトルと掛け合わせれば、最終的にどの文字が何文字残るかわかる。

const ll mo=1000000007;

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

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;
}

class Solution {
public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
		Mat A;
		int x,y;
		FOR(x,26) {
			FOR(y,nums[x]) A.v[(x+1+y)%26][x]=1;
		}
		A=powmat(t,A);
		int C[26]={};
		FORR(c,s) C[c-'a']++;
		
		ll ret=0;
		FOR(y,26) FOR(x,26) ret+=C[y]*A.v[x][y];
		return ret%mo;
        
    }
};

まとめ

★7の方が変に迷う問題が多い気がする…。