AOJ 1082 - 11224111122411

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082

解法

文字種が5の場合，n 文字連続して入力したときの文字列の数を dp1[n] とすると，

dp1[n] = 1 + dp1[n-1] + dp1[n-2] + dp1[n-3] + dp1[n-4] + dp1[n-5]

で計算できる．

文字種が3の数字の場合も同様．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   static const int N = 100000;
 7   static const int M = 100000007;
 8   static int dp1[N+1], dp2[N+1];
 9   dp1[1] = 1;
10   dp1[2] = 2;
11   dp1[3] = 4;
12   dp1[4] = 8;
13   dp1[5] = 16;
14   for (int i = 6; i <= N; i++) {
15     dp1[i] = 1;
16     for (int j = 1; j <= 5; j++) {
17       dp1[i] = (dp1[i] + dp1[i-j]) % M;
18     }
19   }
20   dp2[1] = 1;
21   dp2[2] = 2;
22   dp2[3] = 4;
23   for (int i = 4; i <= N; i++) {
24     dp2[i] = 1;
25     for (int j = 1; j <= 3; j++) {
26       dp2[i] = (dp2[i] + dp2[i-j]) % M;
27     }
28   }
29   string s;
30   while (cin >> s && s != "#") {
31     const int l = s.size();
32     long long ans = 1LL;
33     for (int i = 0; i < l; i++) {
34       int k = i;
35       while (k < l && s[k] == s[i]) {
36         ++k;
37       }
38       if (s[i] == '8' || s[i] == '0') {
39         ans = (ans * dp2[k - i]) % M;
40       } else {
41         ans = (ans * dp1[k - i]) % M;
42       }
43       --k;
44       i = k;
45     }
46     cout << ans << endl;
47   }
48   return 0;
49 }