P1 三角魔法

描述
小栖必须在一个三角形中才能施展魔法，现在他知道自己的坐标和三个点的坐标，他想知道他能否施展魔法

• 点在边上也属于三角形内
• − 1 0 9 < = x , y < = 1 0 9 -10^{9}<=x, y<=10^{9} −109<=x,y<=109

解：

• 判断是否共线
• 判断是否在三角形内

补充知识(好久之前学的，早忘了)：

1. 判断是否共线
   对于三个点 ( x 0 , y 0 ) (x0, y0) (x0,y0) ， ( x 1 , y 1 ) (x1, y1) (x1,y1) ， ( x 2 , y 2 ) (x2, y2) (x2,y2) ，如果满足 ( y 3 − y 1 ) ( x 2 − x 1 ) − ( y 2 − y 1 ) ( x 3 − x 1 ) = 0 (y 3-y 1)(x 2-x 1)-(y 2-y 1)(x 3-x 1)=0 (y3−y1)(x2−x1)−(y2−y1)(x3−x1)=0， 那么这三点共线。

2. 判断是否在三角形内：
   判断 P P P是否在 A ， B , C A，B, C A，B,C组成的三角形内。 如果在三角形内，则：
   A P = u × ( A B ) + v × A C A P=u \times(A B)+v\times A C AP=u×(AB)+v×AC
   满足 0 ≤ u , v ≤ 1 0 \leq u,v \leq 1 0≤u,v≤1， 且 u + v ≤ 1 u+v\leq 1 u+v≤1。

   v = x 2 y 0 − y 2 x 0 x 1 y 0 − y 1 x 0 v=\frac{x_{2} y_{0}-y_{2} x_{0}}{x_{1} y_{0}-y_{1} x_{0}} v=x1​y0​−y1​x0​x2​y0​−y2​x0​​
   u = x 2 y 1 − y 2 x 1 x 0 y 1 − y 0 x 1 u=\frac{x_{2} y_{1}-y_{2} x_{1}}{x_{0} y_{1}-y_{0} x_{1}} u=x0​y1​−y0​x1​x2​y1​−y2​x1​​
   其中, A P = ( x 2 , y 2 ) AP=(x2, y2) AP=(x2,y2), A B = ( x 0 , y 0 ) AB=(x0,y0) AB=(x0,y0), A C = ( x 1 , y 1 ) AC=(x1,y1) AC=(x1,y1)

class Solution:
    """ @param triangle: Coordinates of three points @param point: Xiaoqi's coordinates @return: Judge whether you can cast magic """
    def castMagic(self, triangle, point):
        # write your code here
        return "Yes" if self.solve(triangle, point) else "No"

    def solve(self, triangle, point):
        A, B, C = triangle
        P = point
        if self.isline(A, B, C): return False
        def vec(P, X):
            p0, p1 = P
            x0, x1 = X
            return [p0 - x0, p1 - x1]
        AP, AB, AC = vec(A, P), vec(A, B), vec(A, C)
        x0, y0 = AB
        x1, y1 = AC
        x2, y2 = AP
        div = x1 * y0 - y1 * x0
        u = (x2 * y0 - y2 * x0) / div
        v = -(x2 * y1 - y2 * x1) / div
        return 0 <= u <= 1 and 0 <= v <= 1 and u + v <= 1

    def isline(self, A, B, C):
        x1, y1 = A
        x2, y2 = B
        x3, y3 = C
        return (y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1)

P2 区间异或

描述
有一个数组num，现在定义区间对的和等于：左区间的最大值加右区间的最小值 由于小栖特别能突发奇想，他突然想知道多个区间对和的异或和是多少

4 < = len ⁡ ( 4<=\operatorname{len}( 4<=len(num ) < = 50000 )<=50000 )<=50000
0 < = num ⁡ [ i ] < = 10000000 0<=\operatorname{num}[i]<=10000000 0<=num[i]<=10000000
1 < = len ⁡ ( 1<=\operatorname{len}( 1<=len(ask ) < = 100000 )<=100000 )<=100000
len ⁡ ( a s k [ 0 ] ) = 4 , s \operatorname{len}(a s k[0])=4, s len(ask[0])=4,s,分别表示 l1,r1,l2,r2
num中视作下标从1开始，而不是0
左右区间可能重合

解：

1. ST表 贴一下 秒过舒服

from math import log
class ST:
    def __init__(self, arr):
        n = len(arr)
        K = int(log(n, 2))
        self.Ma = [[0]*(K+1) for _ in range(n)]
        self.Mi = [[0]*(K+1) for _ in range(n)]
        for k in range(K+1):
            for i in range(n):
                if k == 0:
                    self.Ma[i][k] = arr[i]
                    self.Mi[i][k] = arr[i]
                else:
                    if i + (1 << (k - 1)) >= n:
                        continue
                    self.Ma[i][k] = max(self.Ma[i][k-1], self.Ma[i+(1 << (k-1))][k-1])
                    self.Mi[i][k] = min(self.Mi[i][k-1], self.Mi[i+(1 << (k-1))][k-1])

    def query_max(self, L, R):
        k = int(log(R - L + 1, 2))
        return max(self.Ma[L][k], self.Ma[R - (1 << k) + 1][k])

    def query_min(self, L, R):
        k = int(log(R - L + 1, 2))
        return min(self.Mi[L][k], self.Mi[R - (1 << k) + 1][k])

class Solution:
    """ @param num: array of num @param ask: Interval pairs @return: return the sum of xor """
    def Intervalxor(self, num, ask):
        # write your code here
        ret = 0
        st = ST(num)
        for L0, R0, L1, R1 in ask:
            ret ^= st.query_min(L1 - 1, R1 - 1) + st.query_max(L0 - 1, R0 - 1)
        return ret

P3 五字回文

描述
小栖最近很喜欢回文串，由于小栖的幸运数字是5，他想知道形似“abcba"的回文串在他给定的字符串中的数量

s. length < = 1 0 6 <=10^{6} <=106
字符串s只包含小写字母

解：

1. 打卡

class Solution:
    """ @param s: The given string @return: return the number of Five-character palindrome """
    def Fivecharacterpalindrome(self, s):
        # write your code here
        n = len(s)
        def f(i):
            if i + 4 >= n: return 0
            if s[i] == s[i+4] and s[i+1] == s[i+3] and len(set(s[i:i+5])) == 3:
                return 1
            return 0
        return 0 if not s else sum(f(i) for i in range(n))

P4 小栖的金字塔

描述
小栖有一个金字塔，每一层都有编号.

小栖可以在不同点间移动，假设小栖现在在 ( x 1 , y 1 ) (x_1, y_1) (x1​,y1​),他能够移动到的下一个点满足x2>=x1&&y2>=y1现在小栖呆在 ( k , k ) (k,k) (k,k)处，由于我们不能确定小栖现在在哪儿，所以你需要求出所有点 ( k , k ) (k,k) (k,k)到达 ( n , n ) (n,n) (n,n)的方案数的和。

1 < = k < = n < = 1 0 7 1<=k<=n<=10^{7} 1<=k<=n<=107
由于方案数很大，请对方案数取模1e9+7

解：

1. 用dp算一下值， 写完就知道超时了。 看到 1 , 2 , 6 , 22 , 90 , 394 , 1806 , 8558 , 41586 1, 2, 6, 22, 90, 394, 1806, 8558, 41586 1,2,6,22,90,394,1806,8558,41586，网上找了下才知道是施罗德数。
2. 那我们就站在巨人的肩膀上把:)

下图为 n=1,2,3n=1,2,3 时的施罗德路径

施罗德数公式为:
S i = S i − 1 + ∑ j = 0 i − 1 S j S n − j − 1 S_{i}=S_{i-1}+\sum_{j=0}^{i-1} S_{j} S_{n-j-1} Si​=Si−1​+j=0∑i−1​Sj​Sn−j−1​

这个公式n比较小大概5次幂还行。题目是要7次幂， 有另外一个公式：
( i + 1 ) F i = ( 6 n − 3 ) F i − 1 − ( i − 2 ) F i − 2 (i+1) F_{i}=(6 n-3) F_{i-1}-(i-2) F_{i-2} (i+1)Fi​=(6n−3)Fi−1​−(i−2)Fi−2​
其中， F i F_i Fi​ 满足 2 F i = S i , i ⩾ 1 2 F_{i}=S_{i}, \quad i \geqslant 1 2Fi​=Si​,i⩾1。
到这里，还不能做出来， 还要取模， 好像用刀了Lucas公式什么的，没咋看，代码抄过来就好了。 反正， 以后它就是我的模板了。

class Solution:
    """ @param n: The number of pyramid levels n @param k: Possible coordinates k @return: Find the sum of the number of plans """
    def pyramid(self, n, k):
        #
        k = [n - x for x in k]
        n = max(k)
        A = [1, 1] + [0] * (n - 1)
        mod = 10 ** 9 + 7
        def qmi (a, k):
            ret = 1
            while k:
                if k & 1: ret = (ret * a) % mod
                k >>= 1
                a = (a * a) % mod
            return ret

        for i in range(2, n+1):
            A[i] = (((6 * i - 3) * A[i - 1] - (i - 2) * A[i - 2]) % mod) * (qmi(i + 1, mod - 2) % mod)
            A[i] = A[i] % mod
        ret = 0
        for x in k:
            if x == 0:
                ret = (ret + A[0]) % mod
            else:
                ret = (ret + 2*A[x]) % mod
        return ret % mod