Codeforces ECR #107 : F. Chainword

言われてみるとそこまで複雑でもない。
https://codeforces.com/contest/1511/problem/F

問題

N個の文字列が与えられる。

以下の条件を満たすM文字の文字列および相当する２つのパターンの対は何通りか。
パターンは、M文字の文字列の分割を示す。
各分割は、N個の文字列のいずれかでなければならない。

解法

N個の文字列に関し、Aho-Chorasic法を適用するためのTrie木を作ろう。
Trie木上の位置2つの対を考え、１文字追加したときのそれぞれでの状態遷移を考える。
あとは行列累乗の要領でM文字追加したときの数え上げを行おう。

int N,M;
const ll mo= 998244353;
vector<string> S;
const int NUMC=26;
class Trie {
public:
	vector<vector<int> > V;
	int find(string s) {
		int cur=0;
		FORR(c,s) if((cur=V[cur][c+1])==0) return -1;
		return cur;
	}
	void create(vector<string> S) { // 0 is for backtrack
		V.clear();
		V.push_back(vector<int>(NUMC+1));
		sort(S.begin(),S.end());
		FORR(s,S) {
			int cur=0;
			FORR(c,s) {
				if(V[cur][c+1]==0) V.push_back(vector<int>(NUMC+1)),V[cur][c+1]=V.size()-1;
				cur=V[cur][c+1];
			}
		}
	}
};

class ACmatch_num {
public:
	Trie t;
	vector<int> acc;
	int ma;
	void create(vector<string> S) {
		int i;
		ma=S.size();
		t.create(S);
		acc.clear();
		acc.resize(t.V.size());
		FOR(i,S.size()) acc[t.find(S[i])]=1;
	}
	
	int nex(int cur,int c) {
		return t.V[cur][c+1];
	}
};
ACmatch_num ac;

const int MAT=250;
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;
}

int id;
int mp[2020][2020];
vector<int> E[2020];
Mat A;

int dfs(int a,int b) {
	if(mp[a][b]>=0) return mp[a][b];
	mp[a][b]=id++;
	int cur=mp[a][b];
	int i;
	FOR(i,26) {
		int x=ac.nex(a,i);
		int y=ac.nex(b,i);
		if(x==0||y==0) continue;
		A.v[dfs(x,y)][cur]++;
		if(ac.acc[x]) A.v[dfs(0,y)][cur]++;
		if(ac.acc[y]) A.v[dfs(x,0)][cur]++;
		if(ac.acc[x]&&ac.acc[y]) A.v[dfs(0,0)][cur]++;
	}
	
	return cur;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	S.resize(N);
	FOR(i,N) {
		cin>>S[i];
		FORR(c,S[i]) c-='a';
	}
	ac.create(S);
	MINUS(mp);
	
	dfs(0,0);
	A=powmat(M,A);
	
	cout<<A.v[0][0]<<endl;
}

まとめ

とはいえ本番に思いつくのはしんどいなぁ。