#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll B = 2305843009213693951;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);
int main() {
Algerian OI
ll n, m;
cin >> n >> m;
vector<string> s(n);
map<string, ll> freq;
auto fill = [&](string t, ll x, auto&& fill) -> void {
if (x == m) {
freq[t]++;
return;
}
fill(t, x + 1, fill);
t[x] = '!';
fill(t, x + 1, fill);
};
ll res = 0;
for (ll i = 0; i < n; i++) {
cin >> s[i];
// dbg("ye");
fill(s[i], 0, fill);
// dbg("yes");
}
for (ll i = 0; i < n; i++) {
// dbg(res);
// vector<char> cur;
// for (char c : s[i]) if (c != '?')
for (ll mask = 0; mask < (1 << m); mask++) {
string t = s[i];
bool ok = 1;
for (ll j = 0; j < m; j++) {
if (((mask >> j) & 1) && s[i][j] == '?') {
ok = 0;
break;
}
if (s[i][j] == '?') t[j] = '!';
else if (((mask >> j) & 1)) t[j] = '?';
}
if (ok) res += freq[t];
}
}
// dbg(res);
res -= n;
cout << res / 2 << "\n";
// for (ll i = 0; i < n; i++) {
// ll k = 0;
// for (ll j = 0; j < m; j++) k += (s[i][j] == '?');
// res -= (1 << k);
// }
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |