TopCoder SRM 390 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8307&rd=11124
一組Pattern，每個位上是字母或者通配符“？”，求恰好符合K個Pattern的字符串數

這個題目麻煩在恰好（exactly）上
否則完全可以暴力處理
這里要恰好，即符合K個而不符合K＋1個
用DP逐個位置處理
計算出每個字母匹配的Pattern集合，再和前面的Pattern集合取交集計算這一行的結果
計算過程中取交集的“&”錯寫成了“|” 太生疏了

 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class SetOfPatterns
 8{
 9    public int howMany(String[] patterns, int k)
10    {
11        int[][] tab = new int[50][1<<15];
12        int L = patterns.length;
13        int T = 1 << L;
14
15        for(int[] i:tab)
16            Arrays.fill(i, 0);
17        int i,j;
18        char c;
19        for(i = 0 ; i < patterns[0].length(); ++ i){
20            
21            for(c = 'a'; c <= 'z'; ++ c){
22                int mask = 0 ;
23                for(j = 0 ; j < L ; ++ j){
24                    if(patterns[j].charAt(i) == c || patterns[j].charAt(i) =='?')
25                        mask |= 1 << j;
26                }
27                if(i == 0){
28                    tab[i][mask]++;
29                }
30                else{
31                    for(j = 0 ; j < (T); ++ j){
32                        int fin = j & mask;
33                        tab[i][fin] = (tab[i][fin] + tab[i-1][j])%1000003;
34                    }
35                }
36            }
37        }
38        int ans=0;
39        for(i = 0 ; i < T; ++ i){
40            int cnt = 0;
41            for(j = 0 ; j < L; ++ j){
42                int temp = i & (1 << j);
43                if(temp != 0)
44                    cnt ++;
45            }
46            if(cnt == k)
47                ans = (ans + tab[patterns[0].length()-1][i]) % 1000003;
48        }
49        return ans;
50    }
51}