0

我有这样的复发f(n)=(2*f(n-1)+2*f(n-2))%10007;

现在对于一个特定的 ni 需要找到：

g(n)=(f(n)f(0)+f(n-1)f(1)+....+f(0)f(n))%10007.

例如，如果 n=3，

g(3)=(f(3)f(0)+f(2)f(1)+f(1)f(2)+f(0)f(3))%10007.

n可以大到 10^9。我可以找到f(n)使用矩阵指数的价值，log(n)但我不知道如何获得g(n)。

（我需要这个来解决来自amritapuri 2008 地区的问题

4

3 回答 3

1

暂时忘记 10007。

让F(x)=sum(f(n)*x^n). 然后F(x)=(f(0)+x*(f(1)-2f(0))/(1-2x-2x^2)。

让G(x)=sum(g(n)*x^n). 然后G(x)=F(x)^2。

因此，问题被简化为找到一个系列的系数（模 10007）。

于 2013-07-30T20:48:44.077 回答
0

背景

最初的问题是关于如何用 4 种类型的瓷砖平铺一个 2*n 的矩形。

不同寻常的是，瓷砖必须分成两部分。

提示 1

但是，您也可以将其视为一种将原始的 4 块红色瓷砖和另一组 4 块蓝色瓷砖拼贴的方法，这样最终的棋盘就有红色的一面和蓝色的一面。

提示 2

令 f(n) 为仅用红色瓷砖平铺 2*n 矩形的方式数，而 h(n) 是用 0 或更多列红色瓷砖后跟 1 平铺 2*n 矩形的方式数或更多列蓝色瓷砖。

提示 3

您现在可以找到一个简单的矩阵乘法，它根据之前的两个值给出 h 和 f 的下一个值，并使用标准矩阵幂幂求最终值。

示例代码

这是一个 Python 演示，该公式给出了与原始求和相同的答案。

def f(n):
    """Number of ways to tile 2*n board with red tiles"""
    if n<0: return 0
    if n==0: return 1
    return 2*f(n-1)+2*f(n-2)

def g_orig(n):
    """Number of ways to tile 2*n board in two halves"""
    return sum(f(k)*f(n-k) for k in range(n+1))

def h(n):
    """Number of ways to tile 2*n board with red tiles and at least one column of blue tiles"""
    if n<1: return 0
    # Consider placing one column of blue tiles (either 2*1 or 2 1*1)
    t=2*(f(n-1)+h(n-1))
    # Also consider placing two columns of blue tiles (either a 2*2 or L shaped and a 1*1)
    t+=2*(f(n-2)+h(n-2))
    return t

def g(n):
    return f(n)+h(n)

for n in range(10):
    print n,g_orig(n),g(n)
于 2013-07-30T20:47:48.467 回答
0

诀窍是该序列f(n) mod 10007的周期为 10007，即f(n) mod 10007 = f(n + 10007) mod 10007. 所以你需要做的只是（1）计算f(0 .. n - 1) mod 10007，（2）计算f(n - k)f(k) mod 10007，0 <= k < 10007然后（3）根据你的方程对它们求和。您甚至不需要幂指数法来计算f(n)。

于 2013-08-05T03:19:28.930 回答