fair cut

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:

click this for the idea, i'll let you think a little

iterate through all current elements in the subset
see how many ways there are if we tack on the removed element to the end of all subsequences of the previous subset

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)

isn't even in the subset we're processing, bruh
in that case we just set `curr[at] = curr[at - 1]` and move on with our day
is the character that we plan to tack on to the end!
this is a completely new character that `prev` has no goddamn clue about
for this case, we do `curr[at] = 2 * curr[at - 1] + 1`- we either tack it onto the end or we don't, and there's another choice where we start a completely new subsequence with that current character
or it's just part of the previous subset we're processing
in that case it's this thing:
`curr[at] = curr[at - 1] + prev[at] - prev[at - 1]`
tbh forgot why it is this way lmao, i think i figured this out just by looking at some examples
a plausible explanation is we add the previous ones and the ones the previous subset has got figured out
but we overcounted the ones the `prev` AND `curr` have figured out, so we subtract `prev[at - 1]`

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; } ```

atcoder chain contestant