#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end()
#define pb push_back
const int N=2e6+5;
const int mod=1e9+7;
const int inf=2e9;
int dp[37][37][37][37];
int pos[256];
void levi() {
int n,nd;
cin>>n>>nd;
int tim=0;
for (char c='0';c<='9';++c) {
pos[c]=tim++;
}
for (char c='a';c<='z';++c) {
pos[c]=tim++;
}
for (int i=1;i<=n;++i) {
string s;
cin>>s;
for (int j=0;j<16;++j) {
vector<int> id={36,36,36,36};
for (int l=0;l<4;++l) {
if (j&(1<<l)) id[l]=pos[s[l]];
//debug(pos[s[l]],'\n');
}
++dp[id[0]][id[1]][id[2]][id[3]];
}
}
nd=4-nd;
vector<int> su(5,0);
for (int i=0;i<16;++i) {
int res=0;
int d=__builtin_popcount(i);
vector<int> id;
for (int j=0;j<4;++j) {
if (i&(1<<j)) id.pb(j);
}
if (d==0) {
int cu=dp[36][36][36][36];
res+=(cu*(cu-1)/2);
break;
}
else if (d==1) {
for (int c=0;c<tim;++c) {
vector<int> pu={36,36,36,36};
pu[id[0]]=c;
int cu=dp[pu[0]][pu[1]][pu[2]][pu[3]];
res+=(cu*(cu-1)/2);
}
}
else if (d==2) {
for (int c=0;c<tim;++c) {
for (int c2=0;c2<tim;++c2) {
vector<int> pu={36,36,36,36};
pu[id[0]]=c;
pu[id[1]]=c2;
int cu=dp[pu[0]][pu[1]][pu[2]][pu[3]];
res+=(cu*(cu-1)/2);
}
}
}
else if (d==3) {
for (int c=0;c<tim;++c) {
for (int c2=0;c2<tim;++c2) {
for (int c3=0;c3<tim;++c3) {
vector<int> pu={36,36,36,36};
pu[id[0]]=c;
pu[id[1]]=c2;
pu[id[2]]=c3;
int cu=dp[pu[0]][pu[1]][pu[2]][pu[3]];
res+=(cu*(cu-1)/2);
}
}
}
}
else {
for (int c=0;c<tim;++c) {
for (int c2=0;c2<tim;++c2) {
for (int c3=0;c3<tim;++c3) {
for (int c4=0;c4<tim;++c4) {
vector<int> pu={36,36,36,36};
pu[id[0]]=c;
pu[id[1]]=c2;
pu[id[2]]=c3;
pu[id[3]]=c4;
int cu=dp[pu[0]][pu[1]][pu[2]][pu[3]];
res+=(cu*(cu-1)/2);
}
}
}
}
}
su[d]=res;
}
vector<int> res(5,0);
res[0]=su[0]-su[1]+su[2]-su[3]+su[4];
res[1]=su[1]-2*su[2]+3*su[3]-4*su[4];
res[2]=su[2]-3*su[3]+6*su[4];
res[3]=su[3]-4*su[4];
res[4]=su[4];
cout<<res[nd]<<'\n';
}
int32_t main() {
// freopen("sumdiv.in","r",stdin);
// freopen("sumdiv.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);int tt=1;//cin>>tt;
while(tt--)levi();
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
