觉得无事可做的可以像我一样推这个式子~

原题链接：37635.巨大的表格
userId_undefined

‮队团加不）童帅_者仇复

尊贵铂金

2025-02-08 11:09:20

发布于：广东

140阅读
0回复
0点赞

争取达到 O(Qlog⁡M)O(Q\log M)~

A1,i =S×A1,i−1+T×i =Si×A1,0+T×∑j=1ij×Si−j+1  =Si×A1,0+T×((S)+(S+S2)+(S+S2+S3)+(S+S2+S3+S4)+...+(S+...+Si))=Si×A1,0+T×∑j=1i∑k=1i−j+1Sk =Si×A1,0+T×∑j=1iSi−j+2−1S−1 =Si×A1,0+TS−1×∑j=1i(Si−j+2−1) =Si×A1,0+TS−1×((∑j=1iSi−j+2)−i) =Si×A1,0+TS−1×((Si+2−iS−1)−i) =Si×A1,0+T(S−1)2×((Si+2−i)−i×(S−1)) =Si×A1,0+T(S−1)2×(Si+2−i×S) A_{1,i}\\\space\\ =S\times A_{1,i-1}+T\times i\\\space\\ =S^i\times A_{1,0}+T\times \sum_{j=1}^{i} j\times S^{i-j+1}\\\space\\\space\\ =S^i\times A_{1,0}+T\times ((S)+(S+S^2)+(S+S^2+S^3)+(S+S^2+S^3+S^4)+...+(S+...+S^i))\\ =S^i\times A_{1,0}+T\times \sum_{j=1}^i\sum_{k=1}^{i-j + 1} S^k\\\space\\ =S^i\times A_{1,0}+T\times \sum_{j=1}^i \dfrac{S^{i-j+2}-1}{S-1}\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{S-1}\times \sum_{j=1}^i (S^{i-j+2}-1)\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{S-1}\times ((\sum_{j=1}^i S^{i-j+2})-i)\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{S-1}\times ((\dfrac{S^{i+2}-i}{S-1})-i)\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{(S-1)^2}\times ((S^{i+2}-i)-i\times(S-1))\\\space\\ =S^i\times A_{1,0}+\dfrac{T}{(S-1)^2}\times (S^{i+2}-i\times S)\\\space\\

userId_undefined
去预览
0/2000

全部评论 9

  • userId_undefined

    咕咕咕

    荣耀黄金

    A2,i=SiA2,0+T(∑j=1iSj∗A1,i−j)A1,i−j=(Si−jA1,0+T(S−1)2∗(Si−j+2−(i−j)∗S))A_{2,i}=S^{i}A_{2,0}+T(\sum_{j=1}^{i}{S^{j}*A_{1,i-j}})\\ A_{1,i-j}=(S^{i-j}A_{1,0}+\frac{T}{(S-1)^{2}}*(S^{i-j+2}-(i-j)*S))\\

    所以

    A2,i=SiA2,0+T(∑j=1iSj∗(Si−jA1,0+T(S−1)2∗(Si−j+2−(i−j)∗S)))=SiA2,0+T(∑j=1iSiA1,0+T(S−1)2∗(Si+2−(i−j)Sj+1))=SiA2,0+T(iSiA1,0+∑j=1iT(S−1)2∗(Si+2−(i−j)Sj+1))=Si(A2,0+TiA1,0)+(TS−1)2∗∑j=1iSi+2+(i−j)Sj+1=Si(A2,0+TiA1,0+i(STS−1)2)+(TS−1)2∗∑j=1i(i−j)Sj+1A_{2,i}=S^{i}A_{2,0}+T(\sum_{j=1}^{i}{S^{j}*(S^{i-j}A_{1,0}+\frac{T}{(S-1)^{2}}*(S^{i-j+2}-(i-j)*S))})\\ =S^{i}A_{2,0}+T(\sum_{j=1}^{i}{S^{i}A_{1,0}+\frac{T}{(S-1)^{2}}*(S^{i+2}-(i-j)S^{j+1})})\\ =S^{i}A_{2,0}+T(iS^{i}A_{1,0}+\sum_{j=1}^{i}{\frac{T}{(S-1)^{2}}*(S^{i+2}-(i-j)S^{j+1})})\\ =S^{i}(A_{2,0}+TiA_{1,0})+(\frac{T}{S-1})^{2}*\sum_{j=1}^{i}{S^{i+2}+(i-j)S^{j+1}}\\ =S^{i}(A_{2,0}+TiA_{1,0}+i(\frac{ST}{S-1})^{2})+(\frac{T}{S-1})^{2}*\sum_{j=1}^{i}{(i-j)S^{j+1}}

    所以

    ∑j=1i(i−j)Sj+1=(i−1)S2−S3(Si−1−1S−1)=(i−1)S2+S31−Si−1S−1\sum_{j=1}^{i}{(i-j)S^{j+1}}=(i-1)S^{2}-S^{3}(\frac{S^{i-1}-1}{S-1})\\ =(i-1)S^{2}+S^{3}\frac{1-S^{i-1}}{S-1}\\

    所以

    A2,i=Si(A2,0+TiA1,0+i(STS−1)2)+(STS−1)2(i−1+S1−Si−1S−1)A_{2,i}=S^{i}(A_{2,0}+TiA_{1,0}+i(\frac{ST}{S-1})^{2})+(\frac{ST}{S-1})^{2}(i-1+S\frac{1-S^{i-1}}{S-1})

    尽力了,我小学生md太难推了(

    2025-03-09 来自 江西

    1
  • userId_undefined

    咕咕咕

    荣耀黄金
    A_{3,i}=S^iA_{3,0}+T\sum_{j=1}^i[S^j\times A_{2,i-j}]\\
A_{2,i-j}=S^{i-j}(A_{2,0}+T(i-j)A_{1,0}+(i-j)(\frac{ST}{S-1})^2)+(\frac{ST}{S-1})^2(i-j-1+S\frac{1-S^{i-j-1}}{S-1})\\

    1周前 来自 江西

    0
  • userId_undefined

    ZDZL_天之神_复仇者_

    倔强青铜

    DeepSeek-R1满血版
    思考完成
    Okay, let me try to figure out how to approach this problem. So, the task is to compute A₁,i given the recurrence relation A₁,i = S × A₁,i−1 + T × i. The user has already derived a formula, but maybe they want to verify it or find a more efficient way to compute it, especially when dealing with large values of i. They mentioned O(Q log M) time, which suggests that there might be multiple queries (Q) and we need an efficient way to compute each query, possibly using exponentiation by squaring or similar techniques.

    First, let me recap the recurrence relation. Starting with A₁,0, each subsequent term is S times the previous term plus T multiplied by the current index. This looks like a linear recurrence relation with a non-homogeneous term (the T × i part). The user's derived formula seems to express A₁,i in terms of S, T, and i, which is necessary for efficiency since directly computing each term up to i would take O(i) time per query, which isn't feasible for large i.

    Looking at the user's steps, they expanded the recurrence and recognized the geometric series that arises. Let me verify each step carefully.

    Starting with the recurrence:

    A₁,i = S × A₁,i−1 + T × i

    Unfolding this recursively:

    A₁,i = S^i × A₁,0 + T × [S^{i-1} × 1 + S^{i-2} × 2 + ... + S^0 × i]

    Wait, actually, when you expand the recurrence, each term T × j (where j ranges from 1 to i) gets multiplied by S^{i-j}. Let's see:

    For example, for i=1:

    A₁,1 = SA₁,0 + T1

    For i=2:

    A₁,2 = S*(SA₁,0 + T1) + T2 = S^2A₁,0 + TS1 + T*2

    For i=3:

    A₁,3 = S*(S^2A₁,0 + TS1 + T2) + T3 = S^3A₁,0 + TS^21 + TS2 + T*3

    So, in general:

    A₁,i = S^i * A₁,0 + T * Σ_{j=1}^i [j * S^{i-j}]

    Yes, that's correct. Now, the user rewrote the sum Σ_{j=1}^i [j * S^{i-j}] as a double summation involving geometric series. Let me check that step.

    The user expressed the sum as Σ_{j=1}^i Σ_{k=1}^{i-j+1} S^k. Wait, that seems a bit confusing. Let me think. Maybe they are trying to express j * S^{i-j} in terms of an

    2025-03-15 来自 广东

    0
  • userId_undefined

    杨曙宁

    秩序白银

    d

    2025-03-10 来自 浙江

    0
  • userId_undefined

    TN Hacker

    荣耀黄金

    看不懂

    思密达

    2025-02-10 来自 北京

    0
  • userId_undefined

    pipilong

    荣耀黄金

    %%%

    2025-02-07 来自 浙江

    0
  • userId_undefined

    ‮队团加不）童帅_者仇复

    尊贵铂金

    把 S2,iS_{2,i} 到 S30,iS_{30,i} 的都推了

    2025-02-07 来自 广东

    0
  • userId_undefined

    ‮队团加不）童帅_者仇复

    尊贵铂金

    顶

    2025-02-07 来自 广东

    0
  • userId_undefined

    ‮队团加不）童帅_者仇复

    尊贵铂金

    顶

    2025-02-07 来自 广东

    0

热门讨论