G - Yet Another RGB Sequence Editorial by en_translator
By replacing RG
with K
in a string satisfying the conditions, the problem is rephrased as:
Find the number of strings obtained by arranging \(K\) K
’s, \((R-K)\) R
’s, \((G-K)\) G
’s, and \(B\) B
’s, that does not contain a substring RG
.
We introduce two approaches to the rephrased problem.
[1] Inclusion-exclusion principle
It can be solved by applying inclusion-exclusion principle with respect to the number of RG
’s. The number of strings containing at least \(i\) RG
’s is obtained as a multinomial coefficient. The complexity is \(\mathrm{O}(R+G+B)\).
[2] Combinatorial interpretation
First, freely arrange K
,G
, and B
. Then we can insert R
to any position except for inserting in the left of G
. Both can be found easily as binomial and multinomial coefficients. The complexity is \(\mathrm{O}(R+G+B)\).
By the way, with a fast algorithm to find a factorial, we can solve it in a total of \(\mathrm{O}(\sqrt P\log P)\) time, where \(P=998244353\).
posted:
last update: