JOI春合宿 2011-day3 deciphering

問題文 : 解読

解法 :
dp[i][j], i番目の文字まで, jで終わる暗号の総数, とすると

dp[i][i番目の文字] = Σ[j = 'A'...'Z' + ' ', j + i番目の文字は禁止されていない] dp[i - 1][j]

となります. 答えは Σ[i = 'A'...'Z'] dp[L][i] です.
dp[0][' '] = 1としておけば, あとはテーブル使い回しのDPで解けます.

計算量は O(L * 26) = O(L)です. (定数大きめ)

(ところで, 最近問題を解くときにどうでもいい弊害(bccのscanfで文字列を取るときに32767文字しか読み取らないとか)で時間を吸われていて残念です.)

コード :

#include <cstdio>
#include <cstring>

#define MOD (10000000)

using namespace std;

int w, m;
int dp[300010][27];
bool ng[27][27];
char str[300010];

int main()
{
	
	scanf("%d", &w);
	scanf("%s", &str[1]);
	scanf("%d", &m);
	
	for (int i = 0; i < m; i++){
		char s[8], t[8];
		scanf("%s %s", s, t);
		s[0] -= 'A'; t[0] -= 'A';
		ng[s[0]][t[0]] = true;
	}
	
	for (int i = 1; i <= w; i++) str[i] -= 'A';
	
	memset(dp, 0, sizeof(dp));
	
	dp[0][26] = 1;
	for (int i = 1; i <= w; i++){
		memcpy(dp[i], dp[i - 1], sizeof(dp[i - 1]));
		int next = 0;
		for (int j = 0; j <= 26; j++){
			if (!ng[j][str[i]]){
				next += dp[i - 1][j];
				next %= MOD;
			}
		}
		dp[i][str[i]] = next;
	}
	
	int ans = 0;
	for (int i = 0; i < 26; i++) ans = (ans + dp[w][i]) % MOD;
	
	printf("%d\n", ans);
	
	return (0);
}