# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
104550 | Hassoony | Parametriziran (COCI19_parametriziran) | C++17 | 2444 ms | 51580 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=(1e9+7);
const ll inf=(1ll<<61);
const int MX=50009;
int n,m,vis1[MX];
map<string,int>vis[(1<<7)];
string s;
char oo[8];
ll ans=0;
void add(string s){
for(int j=1;j<(1<<m);j++){
int ret=0;
string tmp="";
bool ok=1;
for(int i=0;i<s.size();i++){
if((j&(1<<i)) && s[i]=='?')ok=0;
if((j&(1<<i)))ret+=(1<<i),tmp+=s[i];
else tmp+='?';
}
if(!ok)continue;
vis[ret][tmp]++;
}
int ret=0;
for(int i=0;i<s.size();i++){
if(s[i]!='?')ret+=(1<<i);
}
vis1[ret]++;
}
ll get(string s){
ll ret=0;
for(int i=0;i<(1<<m);i++){
bool ok=1,ok1=1;
int sum=0;
for(int j=0;j<m;j++){
bool b=(bool)((i&(1<<j)));
if(b&&s[j]=='?')ok=0;
sum^=b;
}
if(!ok)continue;
string tmp="";
for(int j=0;j<m;j++){
bool b=(bool)((i&(1<<j)));
if(b)tmp+=s[j];
else tmp+='?';
}
if(sum)ret+=vis[i].count(tmp);
else ret-=vis[i].count(tmp);
}
for(int i=0;i<(1<<m);i++){
bool ok=1;
for(int j=0;j<m;j++){
bool b=(bool)((i&(1<<j)));
if(b&&s[j]!='?')ok=0;
}
if(ok)ret+=vis1[i];
}
return ret;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
scanf("%s",&oo);s=oo;
ans+=get(s);
add(s);
}
cout<<ans<<endl;
}
/*
3 3
??b
c??
c?c
4 6
ab??c?
??kll?
a?k??c
?bcd??
5 2
??
b?
c?
?g
cg
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |