Problem
acm.hdu.edu.cn/showproblem.php?pid=1438
Reference
blog.csdn.net/u010405898/article/details/9530769
blog.csdn.net/zoucharming/article/details/42918275
Meaning
一把钥匙 n 个槽,槽深可为 1、2、3、4,至少有 3 种槽深,至少有两个连续的槽满足深度差为 3。求合法钥匙数。
Analysis
a[i]:长度为 i 的合法钥匙数
b[i]:长度为 i 的、以 1 或 4 结尾的合法钥匙数
对任意一根长为 i 的合法钥匙,第 i+1 位加上任意深度的槽也合法;
对一根长为 i 的不合法钥匙,如果添加第 i+1 位就合法,有两种情况:
1. 前 i 位全是 1 和 4(但不能只有 1 或只有 4),满足了深度差为 3 的要求,但不满足至少 3 种槽深的要求。此时在 i+1 位补 2 或 3 即可。
2. 前 i 位满足了至少 3 种槽深的要求,但不满足深度差为 3 的要求。此时如果第 i 位是 1 或 4,那在第 i+1 位补 4 或 1 即可。
也就是:前 i-1 位随便放,第 i 位放 1 或 4,第 i+1 位放 4 或 1。(但前 i 位不能只有 1 和 4,或者合法)
(上面只考虑新加的一个槽补在最后,而不考虑插在中间的情况,因为插中间其实就是在合法序列后任意补的情况)
所以:a[i] = a[i-1] * 4 + [ 2^(n-1) - 2 ] * 2 + 2 * 4^(i-2) - 2^(i-1) - b[i-1]
b[i] = a[i-1] * 2 + 2 * 4^(i-2) - 2^(i-1) - b[i-1]
Source code
#include <stdio.h>
#define N 31
long long a[N+1] = {0, 0, 0, 8, 64, 360};
long long b[N+1] = {0, 0, 0, 4};
int main()
{
int i;
for(i=4; i<=N; ++i)
{
long long tmp;
// 合法序列末尾加任意槽深:a[i-1] * 4
a[i] = a[i-1] << 2;
// 末尾加2/3:[2^(n-1) - 2] * 2
a[i] += (1LL << i) - 4;
// 末尾加1/4:2*4^(i-2) - 2^(i-1) - b[i-1]
tmp = (1LL << 2*i-3) - (1LL << i-1) - b[i-1];
a[i] += tmp;
b[i] = (a[i-1] << 1) + tmp;
}
for(i=2; i<=N; ++i)
printf("N=%d: %I64d\n", i, a[i]);
return 0;
}