上行路径

给定正整数n。在所有坐标为$(2^i \bmod n, 3^i \bmod n)$的位置安设站点，其中i是满足$0\le i\le 2n$的整数，同一位置只设一个站点。

本题的目的是希望找到一条从$(0, 0)$到$(n, n)$的路径，沿途x和y坐标都单调不减且穿过尽可能多的站点，记$S(n)$是这样一条路径最多能够穿过的站点数。

例如当$n=22$时一共有11个不同的站点，一条可行的路径最多能穿过5个站点，因此$S(22)=5$，以下是一条这样的路径：

可以验证$S(123)=14, S(10000)=48$。

求$\sum_{k=1}^{30}S(k^5)$。

本题难度:

解答

本题的策略非常直接，先生成所有的站点，再找出其中的最长不减序列的长度即可，前者利用周期性，后者则是标准算法。

最终结果是$9936352$。

注：本题数据量较大，故代码为Python 3（对pow内建函数和list都有一定优化），代码中还打印了进度信息。

s=0
for k in range(1,31):
    n=k**5
    stations=set()
    for i in range(0,2*n+1):
        if (p:=(pow(2,i,n),pow(3,i,n))) in stations:
            break
        else: 
            stations.add(p)
    y=[j for i,j in sorted(stations)]
    n=len(y)
    M=[0]*(n+1)
    L=0
    for i in range(n):
        a=1
        b=L
        while a<=b:
            c=(a+b)//2+(a+b)%2
            if y[M[c]]<=y[i]:
                a=c+1
            else:
                b=c-1
        M[a]=i
        L=max(L,a)
    s+=L
    print(k,"completed")
print(s)