i should probably actually start porting my gists
anyways, new problem, new sussy official code, you know the drill by now
it asks for a string of max len 1000 and max 10 char types how many subsequences of the string have all the same characters together
so right off the bat given that there's a really small bound we know that
this is bitwise dp
(aka we have to solve a problem on all subsets of something)
i know what you're thinking (probably, idk i'm not anya from spy x family [btw watch it it's a good anime that's still airing rn omg she's so cute])
sooo we just frickin define it as ``` dp[subset] = # of valid subsequences given that we only think abt the characters in the subset? ```
ok buddy, i'll take you up on that offer
but like if that's the case, why would they make the number of char types 10 instead of 20? and even more important is how the everloving heck are we going to transition?
(btw that was a rhetorical question i don't think there's a way)
usually when you have problems transitioning a way to remedy it is to add another dimension
to your dp array
so lemme just add something to your dp real quick ``` dp[subset][char_num] = # of valid subsequences given that: 1. we only use the characters in the subset 2. we only think about the first char_num characters ```
there! that should make it much, much easier to transition
so if you forgot, with bitwise dp we remove each element from the current subset & see how the previous subset without said element affects the current subset
so i hope it's evident enough that given this array, you know that to transition we do this:
armed with this general idea, we now arrive at our main challenge: we have an array like so: ``` prev[i] = # of valid subsequences of a prev subset given that only the first i chars are considered ``` and now we have to create a new array that we're going to add on to our current subset array that i'll define like so: ``` curr[i] = # of valid subsequences with that prev subset and our current character guaranteed to be at the end (or just not there at all, that's also an option) (also given that only the first i chars are considered) ```
gonna be honest, it's kinda (well it was really hard for me) to come up with an
actual relation between these two arrays without actually coding up some examples
so now would be a good time to just code it up yourself
or don't
if you're here you've probably given up entirely tbh
but anyways, the structure of our array relation
we iterate through all characters & there's 3 cases
(btw i defined the current index to be `at` in the editorial, diff from in the code)
so now we can just add `curr` onto our array and move on, right?
yeah... turns out by doing that we overcount and have to subtract `prev` from
the array as well
this is so that we count the ones that actually have the current character-
the others ones are handled by the other characters we've iterated or are going
to iterate through
phew, finally done! code here:
```cpp #include <iostream> #include <cassert> #include <vector> using std::cout; using std::endl; using std::vector; constexpr int TYPE_NUM = 10; constexpr int MOD = 998244353; int popcount(int x) { int res = 0; for (int i = 0; i < 31; i++) { // not sure if 31 or 32 lol res += (bool) (x & (1 << i)); } return res; } int main() { int contest_num; std::cin >> contest_num; vector<int> contests; for (int c = 0; c < contest_num; c++) { char contest; std::cin >> contest; assert('A' <= contest && contest < 'A' + TYPE_NUM); contests.push_back(contest - 'A'); } vector<vector<long long>> num_ways( 1 << TYPE_NUM, vector<long long>(contest_num + 1) ); for (int ss = 1; ss < (1 << TYPE_NUM); ss++) { vector<long long>& curr = num_ways[ss]; /* * base case is when there's only one character we care about, * i didn't talk about this in the explanation srry */ if (popcount(ss) == 1) { // get the first set bit int set = 0; for (; (ss & (1 << set)) == 0; set++); curr[0] = 1; for (int c = 1; c <= contest_num; c++) { if (contests[c - 1] == set) { curr[c] = curr[c - 1] * 2 % MOD; } else { curr[c] = curr[c - 1]; } } for (long long& c : curr) { // can't have an empty string so we sub 1 from all of them c--; } continue; } for (int to_add = 0; to_add < TYPE_NUM; to_add++) { if ((ss & (1 << to_add)) == 0) { continue; } // that state where we didn't have to_add in this crapshow const vector<long long>& prev = num_ways[ss & ~(1 << to_add)]; vector<long long> new_ways(contest_num + 1); new_ways[0] = 0; // just making it obvious for (int c = 1; c <= contest_num; c++) { // wth we don't care about this contest at all get outta here if ((ss & (1 << contests[c - 1])) == 0) { new_ways[c] = new_ways[c - 1]; continue; } // is this the one we can add on to the end? if (contests[c - 1] == to_add) { new_ways[c] = (2 * new_ways[c - 1] + 1) % MOD; } else { // oh i guess not, f new_ways[c] = ( new_ways[c - 1] + prev[c] - prev[c - 1] + 2 * MOD) % MOD; } } for (int c = 0; c <= contest_num; c++) { // we overcounted some though, be sure to account for that curr[c] = (curr[c] + new_ways[c] - prev[c] + MOD) % MOD; } } } cout << num_ways[(1 << TYPE_NUM) - 1][contest_num] << endl; } ```