题意

定义特殊的加法 $R(x_3,x_3)=P(x_1,x_2)+Q(x_1,x_2)R(x\_3,x\_3)\; =\; P(x\_1,x\_2)\; +\; Q(x\_1,x\_2)$R(x3​,x3​)=P(x1​,x2​)+Q(x1​,x2​)

$x_3=k^2-x_1-x_2\left(modp\right)x\_3\; =\; k^2-x\_1-x\_2(\backslash bmod\; p)$x3​=k2−x1​−x2​(modp)

$y_3=k(x_1-x_3)-y_1\left(modp\right)y\_3\; =\; k(x\_1-x\_3)\; -\; y\_1\; (\backslash bmod\; p)$y3​=k(x1​−x3​)−y1​(modp)

其中，若$P\ne QP\backslash neq\; Q$P​=Q 则 $k=\frac{y_2-y_1}{x_2-x_1}\left(modp\right)k\; =\; \backslash frac\{y\_2-y\_1\}\{x\_2-x\_1\}\; (\backslash bmod\; p)$k=x2​−x1​y2​−y1​​(modp)，否则$k=\frac{3x_1^2+1}{2y_1}\left(modp\right)k\; =\; \backslash frac\{3x\_1^2+1\}\{2y\_1\}(\backslash bmod\; p)$k=2y1​3x12​+1​(modp)

现在给$P_0(x,y)P\_0(x,y)$P0​(x,y)和$nn$n

求$nn$n个$P_{0}P\_0$P0​相加的和$P_0+P_0+...+P_{0}P\_0+P\_0+...+P\_0$P0​+P0​+...+P0​，其中相加的加法用上述定义的加法

方法

模拟/实现

因为这里是特殊的加法，所以乘法也就不再是数乘，$n{P}_0(x,y)\ne (nx,ny)nP\_0(x,y)\; \backslash neq\; (nx,ny)$nP0​(x,y)​=(nx,ny)

把题目给的递推式文字转换为代码, 我们可以通过for循环,相加点实现计算，

代码

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

class Solution {
public:
    const int mod = 1000000007;
    long long add(long long v1,long long v2){ // 带模运算的加法
        return ((v1+v2)%mod+mod)%mod; 
    }
    long long mypow(long long v,long long p){ // 带模运算的数值快速幂
        long long r = 1;
        while(p){
            if(p%2)(r*=v)%=mod;
            (v*=v)%=mod;
            p/=2;
        }
        return r;
    }
    Point add(Point P1,Point P2){ // 按照上面数学公式直接翻译的点加法
        long long k ;
        if(P1.x == P2.x && P1.y == P2.y){
            // 注意overflow
            k = add(P1.x*(long long)P1.x%mod*3,1)*mypow(2*P1.y%mod,mod-2)%mod; // $k = \frac{3x_1^2+1}{2y_1}
        }else{
            k = add(P2.y,-P1.y)*mypow(add(P2.x,- P1.x),mod-2)%mod; // 若$P\neq Q$ 则 $k = \frac{y_2-y_1}{x_2-x_1} (\bmod p)$
        }
        int x3 = add(k*k,-P1.x-P2.x); // $x_3 = k^2-x_1-x_2(\bmod p)$
        int y3 = add(k*add(P1.x,-x3),-P1.y); // $y_3 = k(x_1-x_3) - y_1 (\bmod p)$
        return Point{x3,y3};
    }
    /**
     * 
     * @param P Point类 
     * @param n int整型 
     * @return Point类
     */
    Point NTimesPoint(Point P, int n) {
        Point r = P;
        for(int i = 1;i<n;i++){ // n个点逐个相加
            r = add(r,P);
        }
        return r;
    }
};

复杂度分析

时间复杂度: 因为$nn$n的范围达到了$10^{9}10^9$109,并不能在时间复杂度内完成, $O\left(n\right)O(n)$O(n)

空间复杂度: 只用记录当前加和的值$O\left(1\right)O(1)$O(1)

快速幂

对于普通的加法，同一个数多次相加，我们可以用乘法一次完成计算

对于普通的乘法，同一个数多次相乘，我们可以用快速幂$O\left(log\right(n\left)\right)O(log(n))$O(log(n))次完成计算

因为这里是特殊的加法，我们不具备一个特殊的乘法来一次完成计算

所以套用普通乘法的思路，用快速幂的形式去计算,也就是如下表格的拆分，每个数表示成其二进制形式的整幂次和，然后依次计算$2^{0}P,2^{1}P,2^{2}P,2^{3}P,\cdots ,2^{i}P2^0P,2^1P,2^2P,2^3P,\backslash cdots,2^iP$20P,21P,22P,23P,⋯,2iP ，在对应位满足时，将当前计算的内容加进结果里，这样只需要$O\left(log\right(n\left)\right)O(log(n))$O(log(n))的时间复杂度即可计算出$nPnP$nP的值

图解:

假设我们要计算7P

代码

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

class Solution {
public:
    const int mod = 1000000007;
    long long add(long long v1,long long v2){ // 带模运算的加法
        // Non-negative add result
        return ((v1+v2)%mod+mod)%mod;
    }
    long long mypow(long long v,long long p){ // 带模运算的快速幂
        long long r = 1;
        while(p){ // 见上面图解的快速幂
            if(p%2)(r*=v)%=mod;
            (v*=v)%=mod;
            p/=2;
        }
        return r;
    }
    Point add(Point P1,Point P2){ // 按照上面数学公式直接翻译的点加法
        long long k ;
        if(P1.x == P2.x && P1.y == P2.y){
            // 注意overflow
            k = add(P1.x*(long long)P1.x%mod*3,1)*mypow(2*P1.y%mod,mod-2)%mod; // $k = \frac{3x_1^2+1}{2y_1}(\bmod p)$
        }else{
            k = add(P2.y,-P1.y)*mypow(add(P2.x,- P1.x),mod-2)%mod; // 若$P\neq Q$ 则 $k = \frac{y_2-y_1}{x_2-x_1} (\bmod p)$
        }
        int x3 = add(k*k,-P1.x-P2.x); // $x_3 = k^2-x_1-x_2(\bmod p)$
        int y3 = add(k*add(P1.x,-x3),-P1.y); // $y_3 = k(x_1-x_3) - y_1 (\bmod p)$
        return Point{x3,y3};
    }
    /**
     * 
     * @param P Point类 
     * @param n int整型 
     * @return Point类
     */
    Point NTimesPoint(Point P, int n) {
        Point r = P;
        n-=1;
        while(n){ // 见上面图解的快速幂
            if(n%2)r=add(r,P);
            P=add(P,P);
            n/=2;
        }
        return r;
    }
};

需要注意的点

1. $PointPoint$Point的$x,yx,y$x,y字段是int类型，做乘法可能溢出，所以需要转换成$longlonglong\; long$longlong参与计算，计算过程中注意保持加法结果的点是取模后的非负值

2. 因为是特殊的加法，初始结果不能取$(0,0)(0,0)$(0,0) 因为$(0,0)+P\ne P(0,0)\; +\; P\; \backslash neq\; P$(0,0)+P​=P, 所以这里采取$nP=P+(n-1)PnP=P+(n-1)P$nP=P+(n−1)P初始结果是$PP$P，剩余$n-1n-1$n−1个$PP$P来计算

复杂度分析

时间复杂度: 上面分析了，我们对幂次的值按二进制分解，分解的个数就是需要计算的轮次数，$O\left(log\right(n\left)\right)O(log(n))$O(log(n))

空间复杂度: 因为空间上只需要记录当前的计算结果 和 $2^{i}2^i$2i个$PP$P的和，所以是常数级别的空间复杂度$O\left(1\right)O(1)$O(1)

知识点

乘法模逆元

题目中要求分数的模其意义是,如果

$a\cdot b=1\left(modp\right)a\; \backslash cdot\; b\; =\; 1\; (\backslash bmod\; p)$a⋅b=1(modp)

那么$bb$b和$aa$a互为模逆元

有费马小定理$a^{p-1}=1\left(modp\right)a^\{p-1\}=1(\backslash bmod\; p)$ap−1=1(modp)

所以 $a\cdot a^{p-2}=1\left(modp\right)a\backslash cdot\; a^\{p-2\}\; =\; 1\; (\backslash bmod\; p)$a⋅ap−2=1(modp)

所以我们可以通过$a^{p-2}\left(modp\right)a^\{p-2\}\; (\backslash bmod\; p)$ap−2(modp) 来计算$aa$a的模逆元

快速幂

不论是处理特殊加法还是这里计算模逆元，都会用到快速幂,快速幂的核心代码

        while(power){
            if(power%2) result = mul(result,base);
            base = mul(base,base);
            power/=2;
        }