AGC031B

https://gyazo.com/1b9bf271902f33d4edff465f40136e47

Thoughts.

I misunderstood the problem condition (I thought it was two colors, black and white), so I had to start over (moved to the end of the page).

On the operation of overlapping sections

If the colors are different, it is impossible because the previous operation would make it inoperable.

The same color is the same as the manipulation of the combined section.

Therefore, the section of the operation can be assumed to be non-overlapping

For a continuous section of the same color.

No matter which endpoint is chosen, the result is the same.

First, prepare a row C' by collapsing consecutive same-colored squares into one square.

generally

$ f(i) = \sum f(j + 1) [j \in X(C'_i)][i < j]

The object of addition at each step is O(1) if and only if?

Looks bad when the colors alternate.

You can have a cumulative sum for each color.

Since it seems bad to pay O(N) for the calculation of X, if it is calculated collectively at the time of making C', O(N) can be calculated in total.

-----

What I thought (misunderstanding the problem conditions)

Think black and white, block by block.

PS: You misunderstood the problem condition here.

If both ends are the same block, it will not change.

Where you take the edge in the block has no bearing on the outcome.

The number of stones in the block has no bearing on the outcome.

It doesn't matter what color the first block is or what color the result is.

Therefore, the result is determined from the number of blocks alone.

1 street when 1 or 2

2 ways when 3 pieces

When there are four, there are two options, both of which come down to when there are two.

DP-ish

f(4)=2f(2)+1

When 5

3 ways to pinch 1 piece, 1 way to pinch 3 pieces

The two ways of sandwiching one will merge later, so the DP's gradual equation is suspect.

10101 becomes 11101 and 10111, both of which can then become 11111

I'd rather use "When you decide to align to 1, there are 2 blocks of 0's that are not edges, so 2^2".

I'll do this on the side of aligning this to zero.

One street that does not change is common, so subtract one.

summary

Let N be the number of blocks.

2^floor(N/2)+2^ceil(N/2)-1

Official Explanation

DP with foolish O(N^2) and O(N) with ingenuity.

It's a little hard to understand what you mean.

Implement and test

Oh, I thought it was two colors, not black and white! problem condition misunderstanding

Official explanations are difficult to understand.

I agree with the explanation that there are only two ways to do it: either you don't pinch it, or you pinch it with the right end.

---