AOJ2209 UTF-8

問題リンク UTF-8

• 解法

DPです。
dp[i][j]: iバイト目をjバイト文字の先頭と解釈したときのiバイト目以降の解釈の組み合わせ数
という表を後ろのバイトから埋めていけば解けます。
iバイト目をjバイト文字と解釈する方法を説明します。
まず、マスクが0や1のときに入力がその文字でなかったらjバイト文字を作れないので0となります。
変数xsを、マスクがxのときに入力もxだったときの個数。ysを、マスクがyのときに入力がxだったときの個数。y1をマスクがyだったときに入力が1だったときの個数とします。
解釈しようとする文字が1バイト文字だった場合はマスクにyが登場しないので、解釈の仕方は 2^xs 通りとなります。
2，3，4バイト文字だった場合で
y1が0のとき、マスクがyの部分は (2^ys)-1 通りの解釈ができます。-1してるのは、オール0の場合を抜かすためです。
y1が0でないとき、yの箇所に1が少なくとも1つ現れるという条件をすでにクリアしているので、マスクがyの部分は 2^ys 通りの解釈ができます。
それぞれに対して、マスクxの部分は 2^xs 通りの解釈ができるので、結局
(2^xs)*((2^ys)-1) 通り
(2^xs)*(2^ys) 通り
の解釈ができます。

• ソース

import java.util.Scanner;

//UTF-8
public class AOJ2209 {

	String[][] p = {{"0xxxxxxx"}, 
			{"110yyyyx", "10xxxxxx"},
			{"1110yyyy", "10yxxxxx", "10xxxxxx"},
			{"11110yyy", "10yyxxxx", "10xxxxxx", "10xxxxxx"}
	};

	void run(){
		Scanner sc = new Scanner(System.in);
		int MOD = 1000000;
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			char[][] s = new char[n][8];
			for(int i=0;i<n;i++)s[i]=sc.next().toCharArray();
			long[][] dp = new long[n+1][4];
			dp[n][0] = 1;
			for(int i=n-1;i>=0;i--)for(int L=0;L<4;L++){
				if(n<=i+L)continue;
				boolean ok = true;
				int ys = 0, xs = 0, y1 = 0;
				for(int j=0;j<=L;j++)for(int k=0;k<8;k++){
					char ch = p[L][j].charAt(k);
					if(ch=='0'){
						if(s[i+j][k]=='1')ok = false;
					}
					if(ch=='1'){
						if(s[i+j][k]=='0')ok = false;
					}
					if(ch=='x'){
						if(s[i+j][k]=='x')xs++;
					}
					if(ch=='y'){
						if(s[i+j][k]=='1')y1++;
						if(s[i+j][k]=='x')ys++;
					}
				}
				if(ok){
					long res = (1L<<xs)%MOD;
					if(0<L){
						if(y1==0){
							res = (res*((1<<ys)-1))%MOD;
						}
						else{
							res = (res*(1<<ys))%MOD;
						}
					}
					for(int j=0;j<4;j++){
						dp[i][L] = (dp[i][L]+res*dp[i+L+1][j])%MOD;
					}
				}
				else dp[i][L] = 0;
			}
			long res = 0;
			for(int j=0;j<4;j++)res+=dp[0][j];
			System.out.println(res%MOD);
		}
	}

	public static void main(String[] args) {
		new AOJ2209().run();
	}
}