【题目大意】给定一个N个格子和4种颜色，分别是红蓝绿黄，问对于N个格子，存在多少种涂色方案，使得红格子和绿格子个数都是偶数。
【算法分析】我先写了个dfs找规律。。。发现f[i]=f(i-1)*4+2^(i-1)
于是利用我们高二刚学的等比数列求和化简，得到一个非常漂亮的式子f(n)=2^(2*n-2)+2^(n-1)。
不过比较遗憾的是偶还是不会推这个答案，于是只能找规律
【其它】1A
6412011 edward2 3734 Accepted 572K 0MS G++ 417B 2010-02-04 23:54:00
【CODE】
#include
母函数啊。。以前我怎么就没想到恩。。
回复ad饕饕不绝：师傅。。。什么是母函数？就是那个递推式？
回复edward_mj：yes..用母函数几分钟………………
母函数不太会化简..递推公式可以这么考虑合法的N位的=1、后N-1位合法 2*f(n-1) 2、后N-1位一奇一偶 g(n-1) 3、后N-1位都是奇数 不可能g(n-1)=1、对f(n-1)中一排列，把第一个红绿色变成其他色 2*f(n-1) 2、不存在红绿色 2^(n-1)直接求sigma(C(n,a+b)*2^(n-a-b)*sigma(C(a+b,a)))