Lucky Coins Sequence 写不出来了

Question

Problem Description
As we all know,every coin has two sides,with one side facing up and another side facing down.Now,We consider two coins's state is same if they both facing up or down.If we have N coins and put them in a line,all of us know that it will be 2^N different ways.We call a "N coins sequence" as a Lucky Coins Sequence only if there exists more than two continuous coins's state are same.How many different Lucky Coins Sequences exist?

Input
There will be sevaral test cases.For each test case,the first line is only a positive integer n,which means n coins put in a line.Also,n not exceed 10^9.

Output
You should output the ways of lucky coins sequences exist with n coins ,but the answer will be very large,so you just output the answer module 10007.

Sample Input
3
4

Sample Output
2
6

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 二进制表示的n位数有2^n种不同的表示方式
# 判断两个连续的相同状态是否相邻有两种情况：
#   1. 相邻且左边为相同状态； 
#   2. 不相邻但右边为相同状态。
# 用一个变量dp记录第i个位置上是否存在相同的连续状态，初始值为false。
# dp[i] = dp[i-1] || (dp[i-2] && (dp[i-3] || (dp[i-4] && (dp[i-5] || ...))))。

# 从左到右遍历，每次更新dp[i]
# 当前元素为相同状态时，直接跳过，否则尝试将dp[i]设置为true，并更新dp[i+1], dp[i+2], dp[i+3].
# 注意：如果当前元素为相同状态，则无法判断是否相邻，因此在更新dp[i+1], dp[i+2], dp[i+3]时，需要判断dp[i-1]和dp[i-2]是否满足条件。

# 时间复杂度O(n)
# 空间复杂度O(1)

library(dplyr)

# 求解问题
lucky_coin_sequence <- function(n) {
  if (n == 1) return 1
  dp <- c(FALSE, FALSE)
  for (i in 2:n) {
    dp[i] <- dp[i-1] || (dp[i-2] && (dp[i-3] || (dp[i-4] && (dp[i-5] || ...))))
  }
  length(unique(dp))
}

# 测试数据
test_cases <- list(
  n = 3,
  n = 4
)
results <- lapply(test_cases, lucky_coin_sequence)
print(results)