Submission #1315213

#TimeUsernameProblemLanguageResultExecution timeMemory
1315213haithamcoderParametriziran (COCI19_parametriziran)C++20
66 / 110
1562 ms100424 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...