The Wall is a massive wall over 700 feet high and is made of ice, stretching 300 miles across the northern border of the Seven Kingdoms, separating it from the wild lands beyond. Appearing as one of the nine
Wonders Made by Man in the book by Lomas Longstrider, the Wall is defended and held by the Sworn Brothers of the Night's Watch, who patrol and guard the castles from the Frostfangs mountain range in the west to the Bay of Seals in the east.
(c) A Wiki of Ice and Fire
Winter is coming. The army of White Walkers is heading to the south. The Wall is the only obstacle, that protects the people of the Seven Kingdoms from the danger.
In this problem we assume, that the Wall can be described as a rectangle R on the Cartesian plane. The corner points of R are (0, 0), (0, H), (W, H)
and (W, 0).
In order to reinforce the Wall, the brothers of the Night's Watch have placed a huge simple polygonal chain P made of the purest valyrian steel on the wall. P can be desribed
as following:
- P consists of N points, both coordinates of which are integers;
- The points are indexed with integers from 0 to N - 1;
- X-coordinate of i'th point of P equals to Xi;
- Y-coordinate of i'th point of P equals to:
- 0, if i is even;
- H, if i is odd.
Your task is pretty simple: calculate the area of R, which is lying under P.
Let's consider a small example for your better understanding:
Let's define H = 4, W = 6, N = 3, X0 = 0, X1 = 5, X2 = 6.
In this testcase we are interested in caculating the area of the green triangle.
N can be extremely huge in this problem, so it's impossible to give you array X itself. Instead of this, we will provide some additional variables and arrays, with a help of which you will be able
to generate arrayX inside your program.
We will use additional integer variables M, A, B and IND. Also, additional array D, which consists of Mintegers and is indexed
with integers from 0 to M - 1 will be used.
Here's a pseudocode, which generates array X:
X[0] = 0
for i from 1 to N - 1:
begin
X[i] = X[i - 1] + D[IND]
IND = (A * IND + B) % M
endInput
The first line of the input contains an integer T, denoting the number of testcases. The description of Ttestcases follows.
The first line of each testcase contains an integer H, denoting the height of R.
The second line contains two integer N and M, denoting the number of points in P and an additional variable.
The third line contains three integers A, B and IND, denoting additional variables.
The fourth line contains M integers, i'th one denotes Di - 1.
Note: W is not provided in the input, but according to the legend it equals to XN - 1.
Output
For each test case the only line of the output should contain the only float: the area of R, which is lying under P.
IMPORTANT: the result should be printed out with exactly one digit after the decimal point. Ignoring of that requirement may lead correct solutions to the WA verdict.
Also, do not add any newlines between different testcases.
Constraints
- 1 ≤ T ≤ 6, for each input file;
- 1 ≤ H ≤ 100000;
- 0 ≤ A, B, IND < M;
- 1 ≤ Di < 104;
- Subtask 1(34 points): 2 ≤ N ≤ 524288, 1 ≤ M ≤ 524288;
- Subtask 2(33 points): 2 ≤ N ≤ 1000000000, 1 ≤ M ≤ 256;
- Subtask 3(33 points): 2 ≤ N ≤ 1000000000, 1 ≤ M ≤ 524288.
Example
Input: 2 5 2 2 0 1 0 10 10 10 10 5 2 3 4 2 5 1 1 4 Output: 25.0 140.0
题解
这道题总的来说非常的奇怪！题目就这么长……
首先，求面积就是矩形面积的一半（傻子都知道），所以这道题要我们做的就只剩下找到x[n-1]。那段代码是无脑暴力的结果，要我们做的就是找循环节，然后注意运算时该要把“强转”的那些类似于（int）……，long long）……的加上，否则会有一些奇怪的错误，比如又WA又RE什么的
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int T,H,n,m,A,B,IND,d[530000];
ll v[530000];
int last[530000];
void init()
{
scanf("%d",&H);
scanf("%d%d",&n,&m);
scanf("%d%d%d",&A,&B,&IND);
int i;
for(i=0;i<m;i++) scanf("%d",&d[i]);
}
void work()
{
memset(last,-1,sizeof(last));
ll now=0; int i;
for(i=0;i<n-1;i++)
{if(last[IND]==-1)
{last[IND]=i; v[IND]=now;
now+=(ll)d[IND]; IND=(int)(((ll)A*(ll)IND+(ll)B)%m);
}
else
{int ju=i-last[IND],rest=n-1-i;
ll sum=now-v[IND];
now+=(ll)sum*(rest/ju);
rest%=ju;
while(rest--)
{now+=(ll)d[IND];
IND=(int)(((ll)A*(ll)IND+(ll)B)%m);
}
break;
}
}
now=(ll)now*H;
printf("%lld",now/2);
if(now&1) printf(".5\n");
else printf(".0\n");
}
int main()
{
scanf("%d",&T);
while(T--)
{init(); work();}
return 0;
}