140 lines
3.7 KiB
Java
140 lines
3.7 KiB
Java
import java.util.*;
|
|
import java.io.*;
|
|
|
|
public class Main {
|
|
static int m;
|
|
|
|
public static void main(String[] args) throws IOException {
|
|
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
|
|
StringTokenizer st = new StringTokenizer(br.readLine());
|
|
int n = Integer.parseInt(st.nextToken());
|
|
m = Integer.parseInt(st.nextToken());
|
|
|
|
int totalMasks = 1 << m;
|
|
|
|
int[][] maskPatterns = new int[totalMasks][];
|
|
int[] maskSize = new int[totalMasks];
|
|
int[] maskCount = new int[totalMasks];
|
|
|
|
char[][] patterns = new char[n][m];
|
|
int[] masks = new int[n];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
String line = br.readLine().trim();
|
|
int mask = 0;
|
|
for (int j = 0; j < m; j++) {
|
|
patterns[i][j] = line.charAt(j);
|
|
if (patterns[i][j] != '?')
|
|
mask |= (1 << j);
|
|
}
|
|
masks[i] = mask;
|
|
maskCount[mask]++;
|
|
}
|
|
|
|
for (int mask = 0; mask < totalMasks; mask++) {
|
|
maskPatterns[mask] = new int[maskCount[mask]];
|
|
}
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
int mask = masks[i];
|
|
int code = encode(patterns[i], mask);
|
|
maskPatterns[mask][maskSize[mask]++] = code;
|
|
}
|
|
|
|
long answer = 0;
|
|
|
|
int[] projA = new int[n];
|
|
int[] projB = new int[n];
|
|
|
|
for (int a = 0; a < totalMasks; a++) {
|
|
if (maskPatterns[a].length == 0)
|
|
continue;
|
|
for (int b = a; b < totalMasks; b++) {
|
|
if (maskPatterns[b].length == 0)
|
|
continue;
|
|
|
|
int conflict = a & b;
|
|
|
|
if (a == b) {
|
|
int sz = maskPatterns[a].length;
|
|
for (int i = 0; i < sz; i++) {
|
|
projA[i] = reproject(maskPatterns[a][i], a, conflict);
|
|
}
|
|
Arrays.sort(projA, 0, sz);
|
|
int i = 0;
|
|
while (i < sz) {
|
|
int j = i + 1;
|
|
while (j < sz && projA[j] == projA[i])
|
|
j++;
|
|
long cnt = j - i;
|
|
answer += cnt * (cnt - 1) / 2;
|
|
i = j;
|
|
}
|
|
} else {
|
|
int sza = maskPatterns[a].length;
|
|
int szb = maskPatterns[b].length;
|
|
for (int i = 0; i < sza; i++)
|
|
projA[i] = reproject(maskPatterns[a][i], a, conflict);
|
|
for (int i = 0; i < szb; i++)
|
|
projB[i] = reproject(maskPatterns[b][i], b, conflict);
|
|
Arrays.sort(projA, 0, sza);
|
|
Arrays.sort(projB, 0, szb);
|
|
int i = 0, j = 0;
|
|
while (i < sza && j < szb) {
|
|
if (projA[i] == projB[j]) {
|
|
int cntA = 1, cntB = 1;
|
|
while (i + cntA < sza && projA[i + cntA] == projA[i])
|
|
cntA++;
|
|
while (j + cntB < szb && projB[j + cntB] == projB[j])
|
|
cntB++;
|
|
answer += (long) cntA * cntB;
|
|
i += cntA;
|
|
j += cntB;
|
|
} else if (projA[i] < projB[j])
|
|
i++;
|
|
else
|
|
j++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
System.out.println(answer);
|
|
}
|
|
|
|
static int encode(char[] pattern, int mask) {
|
|
int code = 0;
|
|
for (int i = 0; i < m; i++) {
|
|
if ((mask & (1 << i)) != 0) {
|
|
code = code * 27 + (pattern[i] - 'a' + 1);
|
|
}
|
|
}
|
|
return code;
|
|
}
|
|
|
|
static int reproject(int code, int srcMask, int targetMask) {
|
|
int[] vals = new int[6];
|
|
int idx = 0;
|
|
for (int i = 0; i < 6; i++) {
|
|
if ((srcMask & (1 << i)) != 0) {
|
|
vals[idx++] = code % 27;
|
|
code /= 27;
|
|
}
|
|
}
|
|
int result = 0, mul = 1;
|
|
int[] srcBits = new int[6];
|
|
int srcCount = 0;
|
|
for (int i = 0; i < 6; i++) {
|
|
if ((srcMask & (1 << i)) != 0)
|
|
srcBits[srcCount++] = i;
|
|
}
|
|
for (int k = 0; k < srcCount; k++) {
|
|
if ((targetMask & (1 << srcBits[k])) != 0) {
|
|
result += vals[srcCount - 1 - k] * mul;
|
|
mul *= 27;
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
}
|