#include <bits/stdc++.h>
// solved by bekagg
#define ll long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int N = 1e5+5;
const int MOD = 1e9+7;
int n , d , c[5][5] , f[5];
ll ans;
map<string , int>mp;
void arkanefury228(){
cin >> n >> d;
if (d == 4){
ans = n * (n - 1) / 2;
for (int i = 1; i <= n; i++){
string s;
cin >> s;
for (int mask = 0; mask < 16; mask++){
string g = "";
int sum = 0 , cnt = 0;
for (int j = 0; j < 4; j++){
if (mask & (1 << j)) {
g += s[j];
cnt++;
}
else {
g += 'X';
}
}
if (d == 4){
if (cnt == 0) continue;
if (cnt % 2 == 1){
ans -= mp[g];
}
else {
ans += mp[g];
}
continue;
}
}
for (int mask = 0; mask < 16; mask++){
string g = "";
for (int j = 0; j < 4; j++){
if (mask & (1 << j)) g += s[j];
else g += 'X';
}
mp[g]++;
}
}
cout << ans;
return;
}
for (int i = 1; i <= n; i++){
string s;
cin >> s;
for (int mask = 0; mask < 16; mask++){
string g = "";
int sum = 0 , cnt = 0;
for (int j = 0; j < 4; j++){
if (mask & (1 << j)) g += s[j];
else {
g += 'X';
cnt++;
}
}
if (d == 4){
if (cnt == 3){
ans += mp[g];
}
else if (cnt == 2){
ans -= mp[g] * 2;
}
continue;
}
if (cnt == d){
ans += mp[g];
}
else if (cnt == d - 1){
ans -= mp[g] * c[4 - cnt][d];
}
}
for (int mask = 0; mask < 16; mask++){
string g = "";
for (int j = 0; j < 4; j++){
if (mask & (1 << j)) g += s[j];
else g += 'X';
}
mp[g]++;
}
}
cout << ans;
}
signed main(){
PRaim_bek_abi
f[0] = 1;
for (int i = 1; i <= 4; i++){
f[i] = f[i - 1] * i;
}
for (int i = 0; i <= 4; i++){
for (int j = 0; j <= i; j++){
c[i][j] = f[i] / (f[i - j] * f[j]);
}
}
int t=1;
//cin>>t;
for (int respagold = 1; respagold <= t; respagold++) arkanefury228();
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
