Codeforces #265 Div1 C. Substitutes in Number

なんとか本番に解けて良かった。
http://codeforces.com/contest/464/problem/C

問題

数だけで構成された文字列Sが与えられる。

ここにN種類のクエリを順に適用する。
各クエリは1つの数字d[i]と数だけで構成された文字列t[i]からなり、クエリに対してはS中における数字d[i]を、全て文字列t[i]に置換しなければならない。

全クエリを適用後の文字列を10進数表記の数字と考えたとき、1000000007で割った余りを求めよ。

解法

後ろのクエリから順にDPなりメモ化再帰し、「この数字は以降のクエリを適用するとどんな値になって、かつ何桁になるか」を計算していけばよい。
ただし、桁数は64bitを超える場合があるのでそのまま持つのではなく、代わりに10^桁数%1000000007を持っておけばよい。

なお、一番最初に「0->S」のクエリがあると仮定しておくと、Sの値を求めるのもDPの一環で処理できて楽である。

本番はメモ化再帰で通したけど、以下はDPで書き直したもの。

string S;
ll mo=1000000007;

int N;
string qs[100005];
ll memo[20][100005];
ll dig[20][100005];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>qs[0];
	cin>>N;
	N++;
	qs[0]="0->"+qs[0];
	for(i=1;i<N;i++) cin>>qs[i];
	FOR(i,10) memo[i][N]=i,dig[i][N]=10;
	
	for(i=N-1;i>=0;i--) {
		FOR(j,10) memo[j][i]=memo[j][i+1],dig[j][i]=dig[j][i+1];
		int from=qs[i][0]-'0';
		
		memo[from][i]=0;
		dig[from][i]=1;
		for(j=qs[i].size()-1;j>=3;j--) {
			int nn=qs[i][j]-'0';
			memo[from][i]=(memo[from][i]+memo[nn][i+1]*dig[from][i])%mo;
			dig[from][i]=(dig[from][i]*dig[nn][i+1])%mo;
		}
		
	}
	
	cout << memo[0][0] << endl;
	
}

まとめ

Bよりずっと実装は簡単。