Codeforces #542 Div1 C. Morse Code

Bで手間取りすぎて本番これ通せなかったのもったいない。
https://codeforces.com/contest/1129/problem/C

問題

0/1の2文字を1～4文字使うと30種類の表現ができる。
ここから4文字パターン4つを除くとアルファベットと同じ26種類の文字が表現できる。

01で構成される文字列Sが与えられる。
S[0..(n-1)]のn文字のprefixに対し、その部分文字列から変換できるアルファベット列は、何通りか、n=1～|S|についてそれぞれ求めよ。

解法

0/1のパターンが同じでも、分解の仕方によって生成できるアルファベット列は複数ある。
これは単純なDPで求められる。

よって、上記DPで同じ部分列に対するアルファベット列の組み合わせを列挙しつつ、元のSの部分列に対してローリングハッシュなどでnを増やしたときに新規パターンを見つけたら対応する組み合わせを解に加算しよう。

struct RollingHash {
	static const ll mo0=1000000021,mo1=1000000009;
	static ll mul0,mul1;
	static const ll add0=1000010007, add1=1003333331;
	static vector<ll> pmo[2];
	string s; int l; vector<ll> hash_[2];
	void init(string s) {
		this->s=s; l=s.size(); int i,j;
		hash_[0]=hash_[1]=vector<ll>(1,0);
		if(!mul0) mul0=10009+(((ll)&mul0)>>5)%259,mul1=10007+(((ll)&mul1)>>5)%257;
		if(pmo[0].empty()) pmo[0].push_back(1),pmo[1].push_back(1);
		FOR(i,l) hash_[0].push_back((hash_[0].back()*mul0+add0+s[i])%mo0);
		FOR(i,l) hash_[1].push_back((hash_[1].back()*mul1+add1+s[i])%mo1);
	}
	/*以下ll版*/
	ll hash(int l,int r) { // s[l..r]
		if(l>r) return 0;
		while(pmo[0].size()<r+2)
			pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1);
		return (((hash_[0][r+1]+(mo0-hash_[0][l]*pmo[0][r+1-l]%mo0))%mo0)<<32) | 
			             ((hash_[1][r+1]+(mo1-hash_[1][l]*pmo[1][r+1-l]%mo1))%mo1);
	}
};
vector<ll> RollingHash::pmo[2]; ll RollingHash::mul0,RollingHash::mul1;

ll mo=1000000007;
ll dp[3030];
int invalid[16];
ll ret[3030];
int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	string S;
	FOR(i,N) {
		cin>>x;
		S.push_back(x);
	}
	reverse(ALL(S));
	RollingHash rh;
	rh.init(S);
	
	invalid[3]=invalid[5]=invalid[14]=invalid[15]=1;
	unordered_set<ll> T[3030];
	ll ret=0;
	for(x=N-1;x>=0;x--) {
		ZERO(dp);
		dp[x]=1;
		for(y=x;y<=N;y++) {
			if(x!=y) {
				ll h=rh.hash(x,y-1);
				if(T[y-x].count(h)==0) {
					T[y-x].insert(h);
					(ret+=dp[y])%=mo;
				}
			}
			(dp[y+1]+=dp[y])%=mo;
			(dp[y+2]+=dp[y])%=mo;
			(dp[y+3]+=dp[y])%=mo;
			int mask=(S[y]<<0)|(S[y+1]<<1)|(S[y+2]<<2)|(S[y+3]<<3);
			if(invalid[mask]==0) (dp[y+4]+=dp[y])%=mo;
		}
		cout<<ret<<endl;
	}
}

まとめ

いやこれBの方が難しいでしょ…。