20200914 T1 s 德 kr 摩

提供一种题解没有提到的做法。
感觉比题解的 dp 自然？
因为要求某两种n顔色出现偶数次，那我们直接枚举好了。

\(\sum\limits_{i=0}^n\sum\limits_{j=0}^{n-i}\binom{n}{i}\binom{n-i}{j}[2\mid i][2\mid j]2^{n-i-j}\)

很自然能够想到\[\sum\limits_{i=0}^{n}\binom{n}{i}[2\mid i]=\sum\limits_{i=0}^{n}\binom{n}{i}[2\nmid i]=2^{n-1}\]
理解方式是前面\(i-1\)个乱选，最后一个用来凑奇数或者偶数，所以只有最后一个是固定的。

但是这样好像并不太好做

于是如果能把奇偶的限制拿掉就好了。
构造一个式子\(\frac{(-1)^i+1^i}{2}\)。
可以发现在偶数时为\(1\)，奇数是为\(0\)。
于是把条件换成这个式子。

\(\sum\limits_{i=0}^n[2\mid i]\binom{n}{i}\sum\limits_{j=0}^{n-i}\binom{n-i}{j}\frac{(-1)^i+1^i}{2}2^{n-i-j}\)

我们先考虑\(j\)那部分怎么算，如果把刚刚那个式子\(2^{-1}\)提出去，\(-1\)和\(1\)分开算，用二项式定理。
式子变成\(\sum\limits_{i=0}^{n}[2\mid i]\binom{n}{i}\frac{3^{n-i}+1}{2}\)

和刚才差不多，把偶数的限制换一下，把括号打开用二项式定理。
最后答案是\(2^{n-1}+4^{n-1}\)