当前位置:首页 > 数学 > 矩阵 > 正文
SSOJ2924佳佳的Fibonacci
1047+

题目大意:$f_n = f_{n-1} + f_{n-2}$,$T_n = F_1 + 2F_2 + … + nF_n$,输入n和m,求$T_n % m$。

题目描述

佳佳对数学,尤其对数列十分感兴趣。在研究完 Fibonacci 数列后,他创造出许多稀奇古怪的数列。例如用 S(n) 表示 Fibonacci 前 n 项和 modm 的值,即 S(n)=(F1+F2+...+Fn)modm,其中 F1=F2=1,Fi=Fi1+Fi2。可这对佳佳来说还是小菜一碟。

终于,她找到了一个自己解决不了的问题。用 T(n)=(F1+2F2+3F3+...+nFn)modm 表示 Fibonacci 数列前 n 项变形后的和 modm 的值。

现在佳佳告诉你了一个 nm,请求出 T(n) 的值。

输入

输入数据包括一行,两个用空格隔开的整数 n,m

输出

仅一行,T(n) 的值。

提示

样例输入

5 5

样例输出

1

样例解释

T(5)=(1+2×1+3×2+4×3+5×5)mod5=1

对于 30% 的数据,1n1000

对于 60% 的数据,1m1000

对于 100% 的数据,1n,m2311

解题思路

$T_n$是发散型序列,很难写出递推式,我们要想办法转成收敛的,或者想办法让两项之间的关系相差1。

如何让系数1、2、3、……、n,转换成n、n-1、……、1呢?让$S_n$乘以n,再减去$T_n$即可得到$(n-1)f_1 + (n-2)f_2 + … + f_{n-1}$,令$g_n = nS_n – T_n = (n-1)f_1 + (n-2)f_2 + … + f_{n-1} = S_1 + S_2 + … + S_{n-1} = g_{n-1} + S_{n-1}$ ,最后根据这些关系:

$f_n = f_{n-1} + f_{n-2}$

$S_n = F_1 + F_2 + … + F_n = S_{n-1} + f_{n-1} + f_{n-2}$

$g_n = g_{n-1} + S_{n-1}$

列出矩阵:

$g_n$

$S_n$

$f_n$

$f_{n-1}$

尝试推出:

$g_{n+1}$

$S_{n+1}$

$f_{n+1}$

$f_{n}$

可得方阵:

1 1 0 0 ($g_n = g_{n-1} + S_{n-1}$)

0 1 1 1 ($S_n = S_{n-1} + f_{n-1} + f_{n-2}$)

0 0 1 1 ($f_n = f_{n-1} + f_{n-2}$)

0 0 1 0

计算完成后,答案就是$nS_n – g_n$,$S_n = a[2][2] + a[2][3]$,$g_n = a[1][2] + a[1][3]$,因为初始时g1 = 0,S1 = f1 = 1,f0 = 0。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

SSOJ2924佳佳的Fibonacci:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!