题解：P9885 [ICPC2018 Qingdao R] Sequence and Sequence

· · 题解

模拟赛搬了这个题，写一发题解纪念我成功补掉依托shi。

以下 p_i=P(i),q_i=Q(i)。

首先根据递推式我们可得：

q_n=\sum_{i=1}^n{q_{p_i}}

当 i \in [1,n] 时 p_i \leq O(\sqrt{n})，所以我们希望凑出一些式子含有 p_{i}-p_{i-1} 的形式或 q_{p_i}-q_{p_{i-1}} 之类的形式。

接下来是一种叫“分部求和法”的神秘技巧：

令 f_0(x)=1，F_i(x)=\sum_{j=1}^xf_i(j)，f_{i+1}(x)=F_i(\frac{x(x+1)}{2}-1)，那么：

\begin{aligned} q_n &=\sum_{i=1}^n{q_{p_i}}\\ &=\sum_{i=1}^nf_0(i){q_{p_i}}\\ &=\sum_{i=1}^n(F_0(i)-F_0(i-1)){q_{p_i}}\\ &=F_0(n)q_{p_n}+\sum_{i=1}^{n-1} F_0(i)(q_{p_i}-q_{p_{i+1}})\\ &=F_0(n)q_{p_n}-\sum_{i=0}^{n-1} F_0(i)(q_{p_{i+1}}-q_{p_{i}})\\ &=F_0(n)q_{p_n}-\sum_{i=1}^{n} F_0(i-1)(q_{p_{i}}-q_{p_{i-1}})\\ \end{aligned}

出现了 q_{p_{i}}-q_{p_{i-1}} 的形式，这样我们枚举 p_{i}\neq p_{i-1} 的 i=\frac{j(j+1)}{2},j \in \N，且我们可以发现 j=p_i。

于是我们枚举 j：

\begin{aligned} q_n &=F_0(n)q_{p_n}-\sum_{i=1}^{n} F_0(i-1)(q_{p_{i}}-q_{p_{i-1}})\\ &=F_0(n)q_{p_n}-\sum_{j=1}^{p_{n}} F_0(\frac{j(j+1)}{2}-1)(q_{j}-q_{j-1})\\ &=F_0(n)q_{p_n}-\sum_{j=1}^{p_{n}} F_0(\frac{j(j+1)}{2}-1)q_{p_j}\\ &=F_0(n)q_{p_n}-\sum_{j=1}^{p_{n}} f_1(j)q_{p_j}\\ \end{aligned}

这时我们设 g(n,k)=\sum_{i=1}^nf_k(i)q_{p_i}，那么我们就可以知道：

\begin{aligned} q_n&=g(n,0)\\ g(n,k)&=F_k(n)q_{p_n}-\sum_{j=1}^{p_{n}} f_{k+1}(j)q_{p_j}\\ &=F_k(n)g(p_{n},0)-g(p_{n},k+1)\\ \end{aligned}

每次递归都可以把 n 的大小开根号。

用 p_n \leq \sqrt{2n} 估计递归四层以后 n 只有 605 的大小，可以直接预处理。

关于维护 f_k,F_k 的部分，可以维护一些连续点值，然后求值的时候直接拉插即可。

预处理时间复杂度很小，查询复杂度是 O(2^{\max k}q\max{\deg F_i})，其中 \max k=5,\max \deg F_i = 47。

python 代码：

python跑得比C++还快拿了最优解（那个匿名用户不算）

f = [None]*5
F = [None]*5

f[0] = [1]

fc = [1]*80

for i in range(1,80):
    fc[i] = fc[i-1]*i

def getf(f:list, x:int):
    n = len(f)
    if x < n and x>=0:
        return f[x]
    if n>=80:
        print(n)
    r = 0
    m = 1
    for i in range(n):
        m = m*(x-i)
    for i in range(n):
        t = m//(x-i)*f[i]*(-1 if (n-i-1)%2==1 else 1)
        r += t*(fc[n]//fc[i])*(fc[n]//fc[n-i-1])
    return r//(fc[n]*fc[n])

def work2(f):
    r = f.copy()
    n = len(f)
    r.append(getf(f,n))
    r[0] = 0
    for i in range(1,len(r)):
        r[i] += r[i-1]
    return r

def work1(f):
    r = [None]*len(f)*2
    for i in range(len(r)):
        r[i] = getf(f,i*(i+1)//2-1)
    return r

ans = [None]*5
B = 700
q = [None]*B
p = [None]*B

def init():
    q[0] = 0
    q[1] = 1
    q[2] = 2
    p[0] = 0
    p[1] = p[2] = 1
    idc = 2
    c = 0
    for i in range(3,B):
        q[i] = q[i-1] + q[idc]
        p[i] = idc
        c += 1
        if c == idc + 1:
            idc += 1
            c = 0
    for i in range(5):
        if i:
            f[i] = work1(F[i-1])
        F[i] = work2(f[i])
        ans[i] = [None]*B
        ans[i][0] = 0
        for j in range(1,B):
            ans[i][j] = ans[i][j-1] + getf(f[i],j)*q[p[j]]

def getp(n: int):
    l = 1
    r = n
    while r-l>1:
        mid = (l+r)>>1
        if mid*(mid+3)<2*n:
            l = mid
        else:
            r = mid
    return r

def g(d:int, n:int):
    if n<B:
        return ans[d][n]
    p = getp(n)
    return getf(F[d],n)*g(0,p)-g(d+1,p)

init()

t=int(input())
for tc in range(t):
    n=int(input())
    print(g(0,n))