UAPC 2011 I 11224111122411

問題

携帯電話のひらがな入力のような装置がある。
ただし、同じキーを続けて押した時に、どこで切れ目があると解釈されるかはわからない。
また、同じキーを何回も押すと、あ→い→う→え→お→あ　のように文字がループする。

キーの入力が与えられたとき、出力される文字列として考えられるのは何通りか。

方針

まずは文字をループさせない（余計な入力がない）場合の文字列を数える。
これは、今までにキーを何回押したか、最後の切れ目にキーがいくつあるかを数えるDPで求まる。
dp[i+1][j+1] += dp[i][j]
dp[i+1][1] += dp[i][j]
みたいな漸化式。

そして、余計な文字を入れることを考える。
6回少なくキーを押した文字列というのは作れる。12回少ないのも……と作れるので、
それらを全部足せばいいことがわかる。
連続する文字の場合の数がわかったら、あとは掛け算すればいい。

ソースコード

const int mod=100000007;
int dp[100001][6],dp2[100001][4];
int sum[100001],sum2[100001];
string in;

int main(){
  dp[0][0]=dp2[0][0]=1;
  
  rep(i,100000)rep(j,6){
    if(j<5)(dp[i+1][j+1]+=dp[i][j])%=mod;
    (dp[i+1][1]+=dp[i][j])%=mod;
  }
  rep(i,100000)rep(j,4){
    if(j<3)(dp2[i+1][j+1]+=dp2[i][j])%=mod;
    (dp2[i+1][1]+=dp2[i][j])%=mod;
  }
  rep(i,100001){
    rep(j,6)(sum[i]+=dp[i][j])%=mod;
    rep(j,4)(sum2[i]+=dp2[i][j])%=mod;
  }
  rep(i,100001){
    if(i>5)(sum[i]+=sum[i-6])%=mod;
    if(i>3)(sum2[i]+=sum2[i-4])%=mod;
  }
  
  while(getline(cin,in),in!="#"){
    int cnt=0;
    vi v,type;
    rep(i,in.size()){
      if(i&&in[i]!=in[i-1]){
        v.pb(cnt); cnt=1;
        type.pb(in[i-1]=='0'||in[i-1]=='8');
      }
      else cnt++;
    }
    type.pb(in[in.size()-1]=='0'||in[in.size()-1]=='8');
    v.pb(cnt);

    ll ans=1;
    rep(i,v.size()){
        if(!type[i])(ans*=sum[v[i]-1])%=mod;
        else (ans*=sum2[v[i]-1])%=mod;
    }
    cout<<ans<<endl;
  }
  return 0;
}