제출 #1339445

#제출 시각아이디문제언어결과실행 시간메모리
1339445po_rag526Parametriziran (COCI19_parametriziran)C++17
0 / 110
14 ms3544 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e5;
const int MOD = 666013;

map< int , int >f[( 1 << 6 )];
string s1[MAXN + 1];
signed main() {
    int n , m , i , mask , j , x , p , ok;
    string s;
    cin >> n >> m;
    long long ans = 0;
    for( j = 1 ; j <= n ; j++ ) {
        cin >> s1[j];
    }
    sort(s1 + 1, s1+n+1, [&]( string a , string b ){
       int cnt = 0 , cnt1 = 0 , i;
       for( i = 0 ; i < m ; i++ ) {
            cnt += a[i] != '?';
            cnt1 += b[i] != '?';
       }
       return cnt < cnt1;
    });
    for( j= 1 ; j <= n ; j++ ) {
        string s = s1[j];
        x = 0;
        for( mask = 1 ; mask < ( 1 << m ) ; mask++ ) {
            x =0 , p = 1 , ok = 1;
            for( i = 0 ; i < m ; i++ ) {
                if( mask & ( 1 << i ) ) {
                    if( s[i] == '?' )
                        ok = 0;
                    x += p * ( s[i] - 'a' );
                }
                p *= 26;
            }
            if( ok == 1 ) {
                if( !f[mask].empty() ) {
                    ans += f[mask].size();
                    if( f[mask].find( x ) != f[mask].end() )
                        ans += f[mask][x];
                }
                //ans += fr[mask].size() - fr[mask][x];
            }
        }
        mask = 0;
        x = 0 , p = 1;
        for( i = 0 ; i < m ; i++ ) {
            if( s[i] != '?' ) {
                mask |= ( 1 << i );
                x += p * ( s[i] - 'a' );
            }
            p *= 26;
        }
        f[mask][x]++;
    }
    cout << ans << '\n';
    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...