[POJ 3734]找规律、等比数列求和公式

【题目大意】给定一个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

加入对话

4条评论

  1. 母函数不太会化简..递推公式可以这么考虑合法的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)))

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注