AOJ : 2209 - UTF-8 - Respect2Dの日記

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2209
日本語なので, 説明省略.

アルゴリズム

dp[0] = 1
dp[i] =
- dp[i-1] * i-1バイト目から1バイト列のパターン数 +
- dp[i-2] * i-2バイト目から2バイト列のパターン数 +
- dp[i-3] * i-3バイト目から3バイト列のパターン数 +
- dp[i-4] * i-4バイト目から4バイト列のパターン数

プログラム

#define MOD 1000000LL
typedef unsigned long long ll;

int n;
ll dp[1002];
string s[1002];
string utf[4][4] = {
  {"0xxxxxxx","","",""},
  {"110yyyyx","10xxxxxx","",""},
  {"1110yyyy","10yxxxxx","10xxxxxx",""},
  {"11110yyy","10yyxxxx","10xxxxxx","10xxxxxx"}
};

ll check(int idx,int len){
  ll res = 1;
  int xcnt = 0; //ビットパターンでyの位置で, 入力列がxになっている数
  int onecnt = 0; //ビットパターンでyの位置で, 入力列が1になっている数

  for(int i=0;i<len;i++){
    for(int j=0;j<8;j++){
      char cu = utf[len-1][i][j];
      char cs = s[idx+i][j];

      if(cu == '0' || cu == '1'){
        if(cs != 'x' && cu != cs) return 0;
      }
      else if(cu == 'x'){
        if(cs == 'x') res = (res * 2) % MOD;
      }
      else{
        if(cs == 'x') xcnt++;
        else if(cs == '1') onecnt++;
      }
    }
  }

  if(len == 1) return res;
  if(onecnt==0 && xcnt==0) return 0;

  if(onecnt == 0) res = (res * ((1<<xcnt) - 1)) % MOD;
  else res = (res * (1<<xcnt)) % MOD;

  return res;
}

int main(void){
  while(cin>>n,n){
    for(int i=0;i<n;i++) cin>>s[i];

    memset(dp,0,sizeof(dp));
    dp[0] = 1;

    for(int i=0;i<n;i++){
      for(int j=1;j<=4;j++){
        if(i+j > n) break;
        ll pat = check(i,j);
        if(pat == 0) continue;
        dp[i+j] = (dp[i+j] + dp[i] * pat) % MOD;
      }
    }

    cout<<dp[n]<<endl;
  }

  return 0;
}