0422 双曲线上点列
* * * *
拉格朗日计划
* * * *
双曲线上点列

给定双曲线$H: 12x^2+7xy-12y^2=625$及其上一点X(7, 1),按如下方式定义一点列: $$P_1=(13, \frac{61}{4}), \quad P2 = (-\frac{43}{6}, -4), \quad \ldots$$ 之后$P_i$是H上异于$P_{i-1}$且满足直线$P_iP_{i-1}$平行于直线$P_{i-2}X$的点。



可以验证$P_i$总是存在且必为有理点且 $$P_3=(-\frac{19}{2}, -\frac{229}{24}), \quad P_4=(\frac{1267}{144}, -\frac{37}{12}), \quad \ldots, \quad P_7=(\frac{17194218091}{143327232}, \frac{274748766781}{1719926784}).$$ 设$P_{11^{14}}=(a/b,c/d)$,其中$a/b,c/d$均为最简分数形式,且$b,d>0$,求$a+b+c+d$模$10^9+7$的余数。

(把$P_7$的坐标按上述方式计算求得的结果应为806236837)

本题难度:



解答

考虑双曲线$xy=1$上的点$(a,1/a)$,将其映射为 $$(a+\frac{12}{a}, \frac{4a}{3}-\frac{9}{a}),$$ 即得题中双曲线。拟用这一仿射变换,可把$P_i$在$xy=1$上映射为横坐标为$a_i$的点,且$a_i$满足 $$a_{i}=\frac{a_{i-2}}{a_{i-1}}a_0,$$ 其中$a_0=3, a_1=12$,由此初值可以看出这一数列的分子分母分别是2和3的幂,且各自的指数都具有斐波那契数列的形式,从而用矩阵快速幂即可算出指数,并进一步得结果$92060460$。

N=11**14
mod=1000000007

mul=lambda A,B,m:(((A[0][0]*B[0][0]+A[0][1]*B[1][0])%m, (A[0][0]*B[0][1]+A[0][1]*B[1][1])%m),((A[1][0]*B[0][0]+A[1][1]*B[1][0])%m, (A[1][0]*B[0][1]+A[1][1]*B[1][1])%m))

def matPow(A,k,m):
    if k==1:
        return A
    X=matPow(A,k//2,m)
    X=mul(X,X,m)
    if k%2:
        X=mul(X,A,m)
    return X

x=matPow(((0,1),(1,1)),N-1,mod-1)[0][1]
y=matPow(((0,1),(1,1)),N-2,mod-1)[0][1]

a= pow(2, 4*y+2*x-2, mod)-pow(-3, 2*x-1, mod)
b=-pow(-3, x-1, mod)*pow(2, 2*y+x-2, mod)
c=pow(2, 4*y+2*x+2, mod)+pow(-3, 2*x+1, mod)
d=pow(-3, x, mod)*pow(2, 2*y+x, mod)

print (a+b+c+d)%mod