/*
"care a facut teste cu Lattice reduction attack e ciudat"
"linistiti va putin"
- 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#warning ai grija la ? ca l ai transformat in {
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
const int mod=1e9+9;
const int base=29;
string s[50001];
unordered_map<int,int> hashcount[(1<<6)];
int main()
{
ifstream fin(".in");
ofstream fout(".out");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int i,j,n,m,ans,mask,hashbuild,mask2;
bool ok;
cin >> n >> m;
for (j=1; j<=n; j++)
{
cin >> s[j];
for (i=0; i<s[j].size(); i++)
{
if (s[j][i]=='?')
s[j][i]='{';///urmatorul caracter dupa z
}
for (mask=1; mask<(1<<(m)); mask++)
{
hashbuild=0;
for (i=0; i<s[j].size(); i++)
{
if (mask&(1<<i))
hashbuild=((hashbuild*base)%mod+(s[j][i]-'a'+1))%mod;
}
hashcount[mask][hashbuild]++;
}
}
ans=0;
for (j=1; j<=n; j++)
{
mask=0;
for (i=0; i<s[j].size(); i++)
{
if (s[j][i]!='{')
{
mask=mask|(1<<i);
}
}
if (mask!=0)
{
for (mask2=0; mask2<=mask; mask2++)
{
ok=true;
for (i=0; i<s[j].size() && ok; i++)
{
if ((mask2&(1<<i)) && !(mask&(1<<i)))
ok=false;
}
if (ok)
{
hashbuild=0;
for (i=0; i<s[j].size(); i++)
{
if (mask&(1<<i))
{
if (mask2&(1<<i))
hashbuild=((hashbuild*base)%mod+('{'-'a'+1))%mod;
else
hashbuild=((hashbuild*base)%mod+(s[j][i]-'a'+1))%mod;
}
}
ans+=hashcount[mask][hashbuild];
}
}
}
else
{
ans+=n;
}
}
cout << (ans-n)/2;
return 0;
}
Compilation message
parametriziran.cpp:9:2: warning: #warning ai grija la ? ca l ai transformat in { [-Wcpp]
9 | #warning ai grija la ? ca l ai transformat in {
| ^~~~~~~
cc1plus: error: '::main' must return 'int'
parametriziran.cpp: In function 'int main()':
parametriziran.cpp:34:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (i=0; i<s[j].size(); i++)
| ~^~~~~~~~~~~~
parametriziran.cpp:42:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (i=0; i<s[j].size(); i++)
| ~^~~~~~~~~~~~
parametriziran.cpp:54:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (i=0; i<s[j].size(); i++)
| ~^~~~~~~~~~~~
parametriziran.cpp:66:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (i=0; i<s[j].size() && ok; i++)
| ~^~~~~~~~~~~~
parametriziran.cpp:74:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (i=0; i<s[j].size(); i++)
| ~^~~~~~~~~~~~
