#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define gcd __gcd
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define pqueue priority_queue
#define si(a) scanf("%d", &a)
#define sll(a) scanf("%lld", &a)
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0)
#define EPS 1e-9
#define mod 1000000007
#define MOD 1000000007
#define N 50005
using namespace std;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxpq = priority_queue<T>;
//All indexing is 0-based
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar.
template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
//ordered_map<int, int> my_map;
//Returns no. of values x for which ceil(n / x) == y (y must be > 1).
inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }
//Returns no. of values x for which floor(n / x) == y
inline ll FF(ll n, ll y) { return n / y - n / (y+1); }
//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p; }
// #define int ll
#define trace(...) 42
int n, m;
vector<string> adj[N];
int mask(const string& s) {
int ans = 0;
repi(i, m-1, -1) {
char c = s[i];
ans <<= 1;
if(c != '?') ans |= 1;
}
return ans;
}
inline ll nC2(int n) {
return n * 1ll * (n-1) / 2;
}
main()
{
#ifdef CP
freopen("/home/tarun/Desktop/input.txt", "r", stdin);
// freopen("/home/tarun/Desktop/output.txt", "w", stdout);
#endif
sync;
clock_t clk = clock();
// cerr << "I will return...\n";
cin >> n >> m;
rep(i, 0, n) {
string s; cin >> s;
adj[mask(s)].pb(s);
}
ll ans = 0;
//Consider pairs of strings having same mask.
for(int i = 0; i < 1<<m; i++) {
sort(all(adj[i]));
int l, r;
l = r = 0;
while(l < adj[i].size()) {
while(r < adj[i].sz && adj[i][l] == adj[i][r]) r++;
ans += nC2(r - l);
l = r;
}
}
for(int i = 0; i < 1<<m; i++) {
if(adj[i].sz == 0) continue;
for(int j = i+1; j < 1<<m; j++) {
if(adj[j].sz == 0) continue;
int new_mask = i & j;
vi v;
for(int b = 0; b < m; b++) if(new_mask & (1 << b)) v.pb(b);
if(new_mask == 0) ans += adj[i].sz * adj[j].sz;
else {
map<string, int> mp;
for(auto s : adj[i]) {
string t; for(int j : v) t += s[j];
mp[t]++;
trace(1, t);
}
for(auto s : adj[j]) {
string t; for(int j : v) t += s[j];
ans += mp[t];
trace(2, t);
}
}
trace(i, j, ans);
}
}
cout << ans << '\n';
// cerr << "...don't you ever hang your head.\n";
// cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
}
//Compile using:
//g++ -o filename.exe --std=c++11 filename.cpp
//Use -D CP for defining a macro CP in the local environment
Compilation message
parametriziran.cpp:80:0: warning: "trace" redefined
#define trace(...) 42
parametriziran.cpp:39:0: note: this is the location of the previous definition
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
parametriziran.cpp:99:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
parametriziran.cpp: In function 'int main()':
parametriziran.cpp:121:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l < adj[i].size()) {
~~^~~~~~~~~~~~~~~
parametriziran.cpp:122:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(r < adj[i].sz && adj[i][l] == adj[i][r]) r++;
^
parametriziran.cpp:141:32: warning: statement has no effect [-Wunused-value]
trace(1, t);
^
parametriziran.cpp:146:32: warning: statement has no effect [-Wunused-value]
trace(2, t);
^
parametriziran.cpp:149:29: warning: statement has no effect [-Wunused-value]
trace(i, j, ans);
^
parametriziran.cpp:106:13: warning: unused variable 'clk' [-Wunused-variable]
clock_t clk = clock();
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
3696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2796 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
2916 KB |
Output is correct |
| 2 |
Correct |
20 ms |
4336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
2676 KB |
Output is correct |
| 2 |
Correct |
17 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
3388 KB |
Output is correct |
| 2 |
Correct |
31 ms |
2552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
29 ms |
3120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
25 ms |
2792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
5020 KB |
Output is correct |
| 2 |
Correct |
119 ms |
3792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
373 ms |
3808 KB |
Output is correct |
| 2 |
Correct |
35 ms |
2804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
597 ms |
4576 KB |
Output is correct |
| 2 |
Correct |
310 ms |
3828 KB |
Output is correct |
