#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define len(s) (ll) s.size()
const ll I = 1e6 + 9;
const ll Z = 1e9 + 7;
using namespace std;
int st[15], tf = 0, n, m, a[15], b[14], rs = 0;
map<string, int> dem;
string conv()
{
string rs = "";
for (int i = 1; i <= m; i++)
if (b[i] == 0)
rs = rs + "?";
else if (b[i] == 27)
rs = rs + "1";
else
rs = rs + (char)(b[i] + 96);
return rs;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
string p = "";
tf = 0;
int omsk = (1 << m) - 1;
for (int j = 1; j <= m; j++)
{
char c;
cin >> c;
if (c == '?')
a[j] = 0;
else
a[j] = (int)c - 96;
if (a[j] != 0)
{
tf++;
st[tf] = j;
omsk ^= (1 << (j - 1));
}
}
for (int msk = 0; msk < (1 << tf); msk++)
{
for (int id = 1; id <= m; id++)
b[id] = a[id];
for (int id = 0; id < tf; id++)
{
if ((msk & (1 << id)) == 0)
continue;
b[st[id + 1]] = 0;
}
for (int bit = omsk;; bit = omsk & (bit - 1))
{
for (int tmp = bit; tmp > 0; tmp &= (tmp - 1))
{
int id = __builtin_ctz(tmp) + 1;
b[id] = 27;
}
rs += dem[conv()];
for (int tmp = bit; tmp > 0; tmp &= (tmp - 1))
{
int id = __builtin_ctz(tmp) + 1;
b[id] = a[id];
}
if (bit == 0)
break;
}
}
for (int msk = 0; msk < (1 << tf); msk++)
{
for (int id = 1; id <= m; id++)
b[id] = a[id];
for (int id = 0; id < tf; id++)
{
if ((msk & (1 << id)) == 0)
b[st[id + 1]] = 27;
}
dem[conv()]++;
}
}
cout << rs;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |