Problem 2209 : UTF-8

Problem F: UTF-8
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2209

• 問題概要

与えられた条件で何通りの解釈ができるでしょうか？的な
説明うまくできない。

• 解法

ｙのとこがポイント。
ｙのとこに、１がはいっていたら気にせず、２のx,またはyのところの数乗。
yのとこに１が入ってなかったら、上記から１をひく。
yのとこがすべて0になる場合を除くため。

うまくソースかけなかった。どうやったらこの問題綺麗にかけるんだろうか？？

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

int p1(string s1){
  if(s1[0] == '1')return 0;
  int cnt = 0;
  string x = s1.substr(1, 7);
  cnt += count(ALL(x), 'x');
  return (int)pow(2, cnt)%1000000;
}

int p2(string s1, string s2){
  if(s1[0] == '0' || s1[1] == '0' || s1[2] == '1' || s2[0] == '0' || s2[1] == '1')return 0;
  
  string y = s1.substr(3, 4), x = s1[7] + s2.substr(2, 6);
  if(y == "0000")return 0;  
  
  int one = 1, cnt = 0;
  if(count(ALL(y), '1') != 0) one = 0;
  cnt = (((int)pow(2,count(ALL(y), 'x')) - one)%1000000) * (((int)pow(2, count(ALL(x), 'x')))%1000000);
  return cnt%1000000;
}
int p3(string s1, string s2, string s3){
  if(s1[0] == '0' || s1[1] == '0' || s1[2] == '0' || s1[3] == '1' || s2[0] == '0' || s2[1] == '1'
     || s3[0] == '0' || s3[1] == '1')return 0;
  
  string y = s1.substr(4, 4) + s2[2], x = s2.substr(3, 5) + s3.substr(2, 6);
  if(y == "00000")return 0;
  
  int one = 1, cnt = 0;
  if(count(ALL(y), '1') != 0) one = 0;
  cnt = (((int)pow(2,count(ALL(y), 'x')) - one)%1000000) * (((int)pow(2, count(ALL(x), 'x')))%1000000);
  return cnt%1000000;
}
int p4(string s1, string s2, string s3, string s4){
  if(s1[0] == '0' || s1[1] == '0' || s1[2] == '0' || s1[3] == '0' || s1[4] == '1'  || s2[0] == '0' || s2[1] == '1'
     || s3[0] == '0' || s3[1] == '1' || s4[0] == '0' || s4[1] == '1')return 0;
  
  string y = s1.substr(5, 3) + s2.substr(2, 2), x = s2.substr(4, 4) + s3.substr(2, 6) + s4.substr(2, 6);
  if(y == "00000")return 0;
  
  int one = 1, cnt = 0;
  if(count(ALL(y), '1') != 0) one = 0;
  cnt = (((int)pow(2,count(ALL(y), 'x')) - one)%1000000) * (((int)pow(2, count(ALL(x), 'x')))%1000000);
  return cnt%1000000;
}

main(){

  int n;
  while(cin >> n){
    if(n == 0)break;
    string s[n];
    rep(i, n){
      cin >> s[i];
    }
    lli sum[n+1];
    sum[0] = 1;
    rep(i, n){
      lli cnt = 0;
      cnt += (sum[i] * p1(s[i]));
      if(i > 0)cnt += (sum[i-1] * (lli)p2(s[i-1], s[i]));
      cnt %= 1000000;
      if(i > 1)cnt += (sum[i-2] * (lli)p3(s[i-2], s[i-1], s[i]));   
      cnt %= 1000000;
      if(i > 2)cnt += (sum[i-3] * (lli)p4(s[i-3], s[i-2], s[i-1], s[i]));  
      cnt %= 1000000;
      sum[i+1] = cnt;
    }
    cout << sum[n] << endl;
  }
}