1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const pii mod = {1e9 + 7, 1e9 + 9}, base = {131, 251}; const int N = 1e5 + 10;
pll operator*(const pll &p1, const pll &p2) { return {p1.first * p2.first % mod.first, p1.second * p2.second % mod.second}; }
pll operator+(const pll &p1, const pll &p2) { return {(p1.first + p2.first) % mod.first, (p1.second + p2.second) % mod.second}; }
pll operator-(const pll &p1, const pll &p2) { return {(p1.first - p2.first + mod.first) % mod.first, (p1.second - p2.second + mod.second) % mod.second}; }
int ok = 1; int ch[N][26]; string s[N];
void dfs(const vector<int>& v, vector<bool> rc){ if(!ok) return; vector<int> cnt(26); for(int i : v){ for(int j = 0; j < 26; j++){ if(rc[j]) continue; cnt[j] += ch[i][j]; } } int c = 0; vector<bool> rp(26); for(int i = 0; i < 26; i++){ rp[i] = rc[i]; if(cnt[i] == v.size()) c++, rp[i] = true; } if(!c){ ok = 0; return; } map<pll, vector<int>> mp; for(int i : v){ pll res = {0, 0}; for(char j : s[i]){ if(rp[j - 'a']) res = res * base + pll{j - 'a' + 1, j - 'a' + 1}; else res = res * base + pll{114514, 114514}; } mp[res].push_back(i); } for(const auto& i : mp){ if(i.second.size() > 1){ dfs(i.second, rp); } } }
void solve() { int m, n; cin >> m >> n; vector<int> vec(n); vector<bool> is(26); for(int i = 0; i < n; i++){ cin >> s[i]; vec[i] = i; for(char j : s[i]){ ch[i][j - 'a'] = 1; } } dfs(vec, is); if(ok) cout << "YES\n"; else cout << "NO\n"; }
int main() { int T = 1; ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); while (T--) solve(); return 0; }
|