题目描述
Czy手上有一个长度为n的数列，第i个数为xi。
他现在想知道，对于给定的a,b,c，他要找到一个i，使得a*(i+1)*xi2+(b+1)*i*xi+(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.
题解
我语文不好……人家说不用我就真没用。
话说根据a=a0+LastAns,b=b0+LastAns,c=c0+LastAns。可知最后一个询问的答案。然后把那个式子展开，就可以得出计算lastans的式子。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int n,x[50002],zz;
struct cans{ll a,b,c;} s[500002];
ll ans[500002];
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%d",&x[i]);
while(true)
{zz++;
scanf("%I64d%I64d%I64d",&s[zz].a,&s[zz].b,&s[zz].c);
if(s[zz].a==s[zz].b&&s[zz].a==s[zz].c) return;
}
}
ll calcu(int i)
{
ll A,B;
A=-s[i].a*(ans[i]+1)*x[ans[i]]*x[ans[i]]-(s[i].b+1)*ans[i]*x[ans[i]]-s[i].c-ans[i];
B=(ans[i]+1)*x[ans[i]]*x[ans[i]]+ans[i]*x[ans[i]]+1;
return A/B;
}
void work()
{
int i;
ans[zz-1]=0-s[zz].a;
for(i=zz-1;i>1;i--)
ans[i-1]=calcu(i);
for(i=1;i<zz;i++) printf("%I64d\n",ans[i]);
}
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
init(); work();
return 0;
}