#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <unordered_map> #include <unordered_set> #include <queue> #include <deque> #include <tuple> #include <bitset> using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define x first #define y second typedef long long ll; typedef pair<ll, ll> pii; typedef pair<ll, ll> pll; typedef vector<ll> vi; typedef vector<ll> vll; string s; unordered_map<string, ll> map_word; void iterate_word(ll n){ for(ll i=0; i < 1 << n; i++){ string cur_s; for(ll j=0; j<n; j++){ int use = i & (1 << j); if(use){ cur_s += s[j]; } } map_word[cur_s]++; } } ll ans(ll n){ ll sum=0; map_word.clear(); iterate_word(n); for(const auto & [key, value]: map_word){ if(value>=2){ sum++; } } return sum; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; cin >> s; cout << ans(n) << "\n"; while(q--){ int p; char z; cin >> p >> z; s[p-1] = z; cout << ans(n) << "\n"; } 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 78 | #include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <unordered_map> #include <unordered_set> #include <queue> #include <deque> #include <tuple> #include <bitset> using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define x first #define y second typedef long long ll; typedef pair<ll, ll> pii; typedef pair<ll, ll> pll; typedef vector<ll> vi; typedef vector<ll> vll; string s; unordered_map<string, ll> map_word; void iterate_word(ll n){ for(ll i=0; i < 1 << n; i++){ string cur_s; for(ll j=0; j<n; j++){ int use = i & (1 << j); if(use){ cur_s += s[j]; } } map_word[cur_s]++; } } ll ans(ll n){ ll sum=0; map_word.clear(); iterate_word(n); for(const auto & [key, value]: map_word){ if(value>=2){ sum++; } } return sum; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; cin >> s; cout << ans(n) << "\n"; while(q--){ int p; char z; cin >> p >> z; s[p-1] = z; cout << ans(n) << "\n"; } return 0; } |