专栏文章

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

nnot_clever_syl
P9885题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqo2re9
此快照首次捕获于
2025/12/04 07:57
3 个月前
此快照最后确认于
2025/12/04 07:57
3 个月前
查看原文
模拟赛搬了这个题，写一发题解纪念我成功补掉依托shi。
以下 pi=P(i),qi=Q(i)p_i=P(i),q_i=Q(i)。
首先根据递推式我们可得：
qn=∑i=1nqpiq_n=\sum_{i=1}^n{q_{p_i}}
当 i∈[1,n]i \in [1,n] 时 pi≤O(n)p_i \leq O(\sqrt{n})，所以我们希望凑出一些式子含有 pi−pi−1p_{i}-p_{i-1} 的形式或 qpi−qpi−1q_{p_i}-q_{p_{i-1}} 之类的形式。
接下来是一种叫“分部求和法”的神秘技巧：
令 f0(x)=1f_0(x)=1，Fi(x)=∑j=1xfi(j)F_i(x)=\sum_{j=1}^xf_i(j)，fi+1(x)=Fi(x(x+1)2−1)f_{i+1}(x)=F_i(\frac{x(x+1)}{2}-1)，那么：
qn=∑i=1nqpi=∑i=1nf0(i)qpi=∑i=1n(F0(i)−F0(i−1))qpi=F0(n)qpn+∑i=1n−1F0(i)(qpi−qpi+1)=F0(n)qpn−∑i=0n−1F0(i)(qpi+1−qpi)=F0(n)qpn−∑i=1nF0(i−1)(qpi−qpi−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}
出现了 qpi−qpi−1q_{p_{i}}-q_{p_{i-1}} 的形式，这样我们枚举 pi≠pi−1p_{i}\neq p_{i-1} 的 i=j(j+1)2,j∈Ni=\frac{j(j+1)}{2},j \in \N，且我们可以发现 j=pij=p_i。
于是我们枚举 jj：
qn=F0(n)qpn−∑i=1nF0(i−1)(qpi−qpi−1)=F0(n)qpn−∑j=1pnF0(j(j+1)2−1)(qj−qj−1)=F0(n)qpn−∑j=1pnF0(j(j+1)2−1)qpj=F0(n)qpn−∑j=1pnf1(j)qpj\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)=∑i=1nfk(i)qpig(n,k)=\sum_{i=1}^nf_k(i)q_{p_i}，那么我们就可以知道：
qn=g(n,0)g(n,k)=Fk(n)qpn−∑j=1pnfk+1(j)qpj=Fk(n)g(pn,0)−g(pn,k+1)\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}
每次递归都可以把 nn 的大小开根号。
用 pn≤2np_n \leq \sqrt{2n} 估计递归四层以后 nn 只有 605605 的大小，可以直接预处理。
关于维护 fk,Fkf_k,F_k 的部分，可以维护一些连续点值，然后求值的时候直接拉插即可。
预处理时间复杂度很小，查询复杂度是 O(2max⁡kqmax⁡deg⁡Fi)O(2^{\max k}q\max{\deg F_i})，其中 max⁡k=5,max⁡deg⁡Fi=47\max k=5,\max \deg F_i = 47。
python 代码：
python跑得比C++还快拿了最优解（那个匿名用户不算）
PYTHON
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))

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...