#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ft first
#define sd second
#define sz(x) ((int)x.size())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 50100;
const ll Z = 28;
unordered_map<int, int> mem;
string s[N];
int n, m;
ll ans = 0;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> s[i];
for (int msk = 0; msk < (1 << m); msk++){
bool bad = 0;
int t = 0;
for (int j = 0; j < m && !bad; j++)
if (msk & (1 << j)) {
if (s[i][j] == '?')
bad = 1;
else t = t * Z + 26;
} else {
if (s[i][j] == '?')
t = t * Z + 27;
else t = t * Z + (s[i][j] - 'a');
}
if (!bad)
mem[t]++;
}
}
for (int i = 0; i < n; i++){
for (int msk = 0; msk < (1 << m); msk++){
int t = 0;
for (int j = 0; j < m; j++)
if (msk & (1 << j)) {
if (s[i][j] == '?')
t = t * Z + 26;
else t = t * Z + 27;
} else {
if (s[i][j] == '?')
t = t * Z + 27;
else t = t * Z + (s[i][j] - 'a');
}
if (mem.find(t) != mem.end())
ans += mem[t];
}
}
cout << (ans - n) / 2;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
1996 KB |
Output is correct |
2 |
Correct |
11 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
1920 KB |
Output is correct |
2 |
Correct |
15 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
2688 KB |
Output is correct |
2 |
Correct |
18 ms |
2176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
2304 KB |
Output is correct |
2 |
Correct |
45 ms |
2816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
6060 KB |
Output is correct |
2 |
Correct |
34 ms |
2048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
255 ms |
9784 KB |
Output is correct |
2 |
Correct |
51 ms |
2048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
392 ms |
17068 KB |
Output is correct |
2 |
Correct |
222 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
762 ms |
27372 KB |
Output is correct |
2 |
Correct |
127 ms |
2048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1233 ms |
37096 KB |
Output is correct |
2 |
Correct |
754 ms |
19332 KB |
Output is correct |