背景 Background
第二届『Citric 杯』NOIP 提高组模拟赛第一题
描述 Description
Lemon 认为在第一届『Citric』杯模拟赛中出的题目太简单了，于是他决定，这次要给参赛选手们一个下马威！ ^_^
Lemon 手上有一个长度为 n 的数列，第 i 个数为 xi。
他现在想知道，对于给定的 a,b,c，他要找到一个 i，使得 a(i+1)xi^2+(b+1)ixi+(c+i)=0 成立。
如果有多个 i 满足，Lemon 想要最小的那个 i。
Lemon 有很多很多组询问需要你回答，多到他自己也不确定有多少组。所以在输入数据中 a=b=c=0 标志着 Lemon 的提问的结束。
更加糟糕的是，Lemon 为了加大难度，决定对数据进行加密以防止离线算法的出现。
假设你在输入文件中读到的三个数为 a0,b0,c0，那么 Lemon 真正要询问的 a=a0+lastans,b=b0+lastans,c=c0+lastans.
lastans 的值是你对 Lemon 的前一个询问的回答。如果这是第一个询问，那么 lastans=0
所有的询问都将会按上述方式进行加密，包括标志着询问的结束的那个询问也是这样。
输入格式 InputFormat
输入文件第一行包含一个正整数 n，表示数列的长度。
输入文件第二行包含 n 个整数，第 i 个数表示 xi 的值。
接下来若干行，每行三个数，表示加密后的 a,b,c 值（也就是上文所述的 a0,b0,c0）。
输出格式 OutputFormat
包含若干行，第 i 行的值是输入文件中第 i 个询问的答案。注意，你不需要对标志着询问结束的那个询问作答。
同时，标志着询问结束的询问一定是输入文件的最后一行。也就是，输入文件不会有多余的内容。
样例输入 SampleInput
10
-25392 -22566 29038 -3448 -4253 -18611 3578 5277 15143 -17806
-8625 -793375 11101855351391
34164 43615871 -42948523613906
11782 -97161150 1148692953696
49152 -30145048 -163181863580725
15991 8258147 -1844885901924
20907 -44283578 -28093204667240
-5365 -36900929 17329329122399
16276 1843308 -37594426899934
-16601 -9312065 39316301737847
-9 -9 -9
样例输出 SampleOutput
1
1
8
3
7
1
9
9
9
代码 Code
我们考虑最后一行，因为其代表文件结束，所以解密后的 a=b=c=0。那么我们可以知道倒数第二行的答案（LastAns=-a=-b=-c）。那么原始式子即转换成一个简单的三元一次式子（只和 a,b,c 有关），然后这解密后的值又可以由上一行的答案和输入的 a0,b0,c0 得到，于是就变成了一个只和 LastAns 有关系的一元一次式子，所以又可以得到了上一行的答案。所以这样一直算回去就好了。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
ll i,j,t,n,m,l,r,k,z,y,x;
ll a[50005];
struct question
{
ll a,b,c;
};
vector <question> v;
vector <question>::iterator vi;
vector <ll> ans;
vector <ll>::iterator ai;
ll lastans;
int main()
{
scanf("%lld",&n);
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
while ((scanf("%lld%lld%lld",&x,&y,&z))!=EOF) v.push_back((question){x,y,z});
lastans=0;
for (vi=v.end()-1;vi>v.begin();vi--)
{
t=lastans;
lastans=-(vi->a*(t+1)*a[t]*a[t]+vi->b*t*a[t]+vi->c+a[t]*t+t)/((t+1)*a[t]*a[t]+t*a[t]+1);
ans.push_back(lastans);
}
for (ai=ans.end()-1;ai>=ans.begin();ai--) printf("%lld\n",*ai);
return 0;
}