Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

AOJ1082:11224111122411

方針

配る系のDP。
5種類音のある子音列はループするまでは

あ->ああ->あああ
     あい
 ->い ->いあ
    ->う

というように、最後にa音を1文字つけるor最後の文字を1つ進めるというように2倍になっていく。
ループするとそうもいかないが、例えば
1111111(7文字)のときは

11 + 11111(お)
111 + 1111(え) 
1111 + 111(う)
11111 + 11(い)
111111 + 1(あ)
1111111111(全部ループ)

とできる。
1 + 111111 は、後者の6個をループさせるにしろさせないにしろ
上記のいずれかに含まれていることが解る。
よって

dp[i] = 1 + dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4] + dp[i-5]

として
更新していけばいいことが解る。わ行、や行については3つ前まで考えればよい。

実際にはや行で5回押す場合まで書き出して解った。手作業は偉大である。

以下ソースコード

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

#define MOD 100000007

int main(void){
	int dp1[100001], dp2[100001];
	memset(dp1,0,sizeof(dp1));
	memset(dp2,0,sizeof(dp2));
	dp1[1] = 1; dp1[2] = 2; dp1[3] = 4; dp1[4] = 8; dp1[5] = 16;
	dp2[1] = 1; dp2[2] = 2; dp2[3] = 4;
	
	for(int i=4;i<100001;i++){
		if(i >= 6){
			dp1[i] = 1;
			for(int j=1;j<=5;j++){
				dp1[i] += dp1[i-j] % MOD;
				dp1[i] %= MOD;
			}
		}
		dp2[i] = 1;
		for(int j=1;j<=3;j++){
			dp2[i] += dp2[i-j] % MOD;
			dp2[i] %= MOD;
		}
	}
	
	string str;
	while(cin >> str){
		if(str == "#") break;
		
		char c;
		int num;
		long long ret=1;
		
		c = str[0];
		num = 1;
		if(str.size() == 1){
			cout << 1 << endl;
		}else{
			for(int i=1;i<str.size();i++){
				if(str[i] == c){
					num++;
				}else{
					if(c == '0' || c == '8'){
						ret = ((long long)ret * dp2[num]) % MOD;
					}else{
						ret = ((long long)ret * dp1[num]) % MOD;
					}
					c = str[i];
					num = 1;
				}
			}
			if(c == '0' || c == '8'){
				ret = ((long long)ret * dp2[num]) % MOD;
			}else{
				ret = ((long long)ret * dp1[num]) % MOD;
			}
			cout << ret << endl;
		}
	}
}