// Marcin Knapik #pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define FOR(i, b) for (int i = 0; i < b; ++i) #define sz(s) (int)s.size() #define all(s) s.begin(), s.end() #define mp make_pair #define pb push_back #define f first #define s second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define losuj(a, b) uniform_int_distribution<long long>(a, b)(rng) using ll = long long; ll ans(const string& s) { unordered_map<string, int> dp; for (int mask = 1; mask < (1 << sz(s)); ++mask) { string t; FOR (i, sz(s)) { if (mask & (1 << i)) { t += s[i]; } } dp[t]++; } int wyn = 0; for (auto & u : dp){ wyn += (u.s > 1); } return wyn; } void solve() { int n, m; cin >> n >> m; string s; cin >> s; cout << ans(s) << '\n'; FOR(i, m) { int pos; char c; cin >> pos >> c; pos--; s[pos] = c; cout << ans(s) << '\n'; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; FOR(test, t) { solve(); } return 0; }
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 | // Marcin Knapik #pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define FOR(i, b) for (int i = 0; i < b; ++i) #define sz(s) (int)s.size() #define all(s) s.begin(), s.end() #define mp make_pair #define pb push_back #define f first #define s second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define losuj(a, b) uniform_int_distribution<long long>(a, b)(rng) using ll = long long; ll ans(const string& s) { unordered_map<string, int> dp; for (int mask = 1; mask < (1 << sz(s)); ++mask) { string t; FOR (i, sz(s)) { if (mask & (1 << i)) { t += s[i]; } } dp[t]++; } int wyn = 0; for (auto & u : dp){ wyn += (u.s > 1); } return wyn; } void solve() { int n, m; cin >> n >> m; string s; cin >> s; cout << ans(s) << '\n'; FOR(i, m) { int pos; char c; cin >> pos >> c; pos--; s[pos] = c; cout << ans(s) << '\n'; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; FOR(test, t) { solve(); } return 0; } |