Yeah I think all of these things are things you can do through extension on SOS.
To handle wildcard, essentially we add a new "digit" to every position that depends on every other digit. This sort of transforms the original linear dependence in SOS dp to a tree
Normal: a -> b -> c
Now: a -> b and a -> c
Some very messy code that does this: (in base 3, 0 encodes wildcard, 1 is a '0', 2 is a '1'): ~~~~~ int div = 1; for(int i{}; i < n; ++i){ for(int m = amt-1; m >= 0; --m){ if((m/div)%3 == 0){ int lower = m — (m/div)*div; dp[m] += dp[(m/div + 1)*div + lower]; dp[m] += dp[(m/div + 2)*div + lower]; } } div *= 3; } ~~~~~
This idea that SOS dp works on trees of implications allows this to be used for the second example you also posed.
Theoretically, it could be used for dags?? but that would get very messy very quickly I think.
Yeah I think all of these things are things you can do through extension on SOS.
To handle wildcard, essentially we add a new "digit" to every position that depends on every other digit. This sort of transforms the original linear dependence in SOS dp to a tree
Normal: a -> b -> c
Now: a -> b and a -> c
Some very messy code that does this: (in base 3, 0 encodes wildcard, 1 is a '0', 2 is a '1'): ~~~~~ int div = 1; for(int i{}; i < n; ++i){ for(int m = amt-1; m >= 0; --m){ if((m/div)%3 == 0){ int lower = m — (m/div)*div; dp[m] += dp[(m/div + 1)*div + lower]; dp[m] += dp[(m/div + 2)*div + lower]; } } div *= 3; } ~~~~~
This idea that SOS dp works on trees of implications allows this to be used for the second example you also posed.
Theoretically, it could be used for dags?? but that would get very messy very quickly I think.