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; } } }