数列 COGS1048：[Citric S2] 一道防AK好题

【题目描述】

Czy手上有一个长度为n的数列，第i个数为xi。

他现在想知道，对于给定的a,b,c，他要找到一个i，使得a*(i+1)*x_i²+(b+1)*i*x_i+(c+i)=0成立。

如果有多个i满足，Czy想要最小的那个i。

Czy有很多很多组询问需要你回答，多到他自己也不确定有多少组。所以在输入数据中a=b=c=0标志着Czy的提问的结束。

更加糟糕的是，Czy为了加大难度，决定对数据进行加密以防止离线算法的出现。

假设你在输入文件中读到的三个数为a0,b0,c0，那么Czy真正要询问的a=a0+LastAns,b=b0+LastAns,c=c0+LastAns.

LastAns的值是你对Czy的前一个询问的回答。如果这是第一个询问，那么LastAns=0。

所有的询问都将会按上述方式进行加密，包括标志着询问的结束的那个询问也是这样。

【输入】

输入文件为 seq.in

输入文件第一行包含一个整数n，表示数列的长度。

输入文件第二行包含n个整数，第i个数表示xi的值。

接下来若干行，每行三个数，表示加密后的a,b,c值（也就是上文所述的a0,b0,c0）

【输出】

输出文件为 seq.out

包含若干行，第i行的值是输入文件中第i个询问的答案。注意，你不需要对标志着询问结束的那个询问作答。

同时，标志着询问结束的询问一定是输入文件的最后一行。也就是，输入文件不会有多余的内容。

【输入输出样例】

 

seq.in	seq.out
5 -2 3 1 -5 2 -5 -4 145 -1 -6 -509 -9 -14 40 -3 -13 21 -3 -3 -3	5 4 3 3

【数据范围】

对于40%的数据，满足N<=1000，需要作出回答的询问个数不超过1000.

对于100%的数据，满足N<=50000，需要作出回答的询问个数不超过500000，xi的绝对值不超过30000，解密后的a的绝对值不超过50000，解密后的b的绝对值不超过10^8，解密后的c的绝对值不超过10^18.

【解题思路】

关于这个题目，我只想说一句出题人真心是够了！！！

如果按照丧病的出题人所谓防止出现离线算法在线处理的话复杂度大概是一个O(nq)的，然后能拿40

然而倒着去做这个题目就简单很多……很容易求得最后一个方程的解释-a[n+1],然后代入上一个方程就可以得到一个关于lastans的一次方程，解出这个值在代入……

program seq;
procedure open;
begin
    assign(input,'seq.in');
    assign(output,'seq.out');
    reset(input);
    rewrite(output);
end;

procedure closs;
begin
    close(input);
    close(output);
end;

var n,sum,x1,mid,now:int64;
    i:longint;
    a,b,x,lastans,c:array[0..500000] of int64;
begin
    open;
    read(n);
    for i:=1 to n do
    begin
        read(x[i]);
    end;
    while not eof do
    begin
        inc(sum);
        readln(a[sum],b[sum],c[sum]);
    end;
    //sort(1,n);
    lastans[sum]:=-a[sum];
    for i:=sum-1 downto 2 do
    begin
        now:=lastans[i+1];
        x1:=x[now];
        lastans[i]:=(-(a[i]*(now+1)*sqr(x1)+(b[i]+1)*now*x1+(c[i]+now)))
                    div ((now+1)*sqr(x1)+(now*x1)+1);

    end;
    for i:=2 to sum do writeln(lastans[i]);
    closs;
end.