Problem: piepackages (2017 round3)

Wilson, everyone's favorite recurring programming contest character, has
finally decided that it's time to retire. Why? After several more job changes
and miraculous promotions, not only has he become incredibly wealthy, but he's
ended up stuck in a boring administrative role, which was the last thing he
wanted!

Wilson is currently employed as the head of accounting at a pie delivery
company, and has been given one last assignment to complete before his
retirement — computing delivery truck gas usage. He wishes he could just drive
one of the trucks instead...

The pie delivery company services a network of **N** \+ 1 towns, which rather
looks like a pie itself (or perhaps like an umbrella...). **N** of the towns
form a circle around the outside of the region, and are numbered from 1 to
**N** in clockwise order. They are connected to one another by **N** roads,
each of which can be driven along in either direction. The _i_th of these
roads requires **Oi** litres of gas to drive along, and runs between towns _i_
and _i_ \+ 1 (unless _i_ = **N**, in which case it instead runs between towns
**N** and 1).

The remaining town, numbered **N** \+ 1, lies in the center of the region.
There are **N** roads connecting it to the other towns, each of which can be
driven along in either direction. The _i_th of these roads requires **Ri**
litres of gas to drive along, and runs between towns **N** \+ 1 and _i_.

A total of **N** * (**N** \+ 1) / 2 pie deliveries are scheduled to be carried
out, one for each distinct pair of towns. In particular, for every town _i_,
_i_ \- 1 deliveries will originate from it, with the _j_th of them having town
_j_ as its destination. The truck drivers will have to pay the gas expenses
out of their own pockets, of course, so for each delivery, the truck driver
will choose a sequence of roads to follow from the initial town to the
destination such that the total amount of gas required for their trip is
minimized. Wilson's task is to tally up the total amount of gas which will be
used across all **N** * (**N** \+ 1) / 2 of the deliveries. He's been
instructed to only determine the value of this sum modulo 1,000,000,007.

You're given **O1**, and **O2..N** may then be calculated as follows using
given constants **Ao**, **Bo**, **Co**, and **Do**.

**Oi** = ((**Ao** * **Oi-1** \+ **Bo**) %**Co** \+ **Do**

You're given **R1**, and **R2..N** may then be calculated as follows using
given constants **Ar**, **Br**, **Cr**, and **Dr**.

**Ri** = ((**Ar** * **Ri-1** \+ **Br**) %**Cr** \+ **Dr**

### Input

Input begins with an integer **T**, the number of different regions of towns.
For each region, there is first a line containing the integer **N**. Then
there is a line with five space-separated integers, **O1**, **Ao**, **Bo**,
**Co**, and **Do**. Then there is a line with five space-separated integers,
**R1**, **Ar**, **Br**, **Cr**, and **Dr**.

### Output

For the _i_th graph, print a line containing "Case #**i**: " followed by the
total amount of gas which will be used (in litres), modulo 1,000,000,007

### Constraints

1 ≤ **T** ≤ 40  
3 ≤ **N** ≤ 1,000,000  
1 ≤ **O1**, **Co**, **Do** ≤ 1,000,000  
0 ≤ **Ao**, **Bo** ≤ 1,000,000  
1 ≤ **R1**, **Cr**, **Dr** ≤ 1,000,000  
0 ≤ **Ar**, **Br** ≤ 1,000,000  

### Explanation of Sample

In the first case, the roads running around the outside require 1, 3, and 5
litres of gas to drive along, respectively. Meanwhile, the roads connected to
the central town require 1, 2, and 2 litres of gas to drive along,
respectively. The amounts of gas required for the 6 deliveries (in litres) are
[1, 1, 2, 2, 3, 3], for a total of 12.



Sample input:
5
3
1 1 1 100 1
1 0 1 100 1
3
1 1 1 100 1
50 1 0 100 1
5
2 3 4 13 3
4 3 2 13 3
10
23 42 32 98 29
19 43 36 67 21
1000
123 456 789 123456 789
789 456 123 654321 987


Sample output:
Case #1: 12
Case #2: 161
Case #3: 93
Case #4: 4288
Case #5: 292394669



Code: // Hacker Cup 2017
// Round 3
// Pie Packages
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 2000001
#define MOD 1000000007
#define DIV2 500000004

int Add(int a,int b)
{
	a+=b;
		if (a>=MOD)
			a-=MOD;
	return(a);
}

int Sub(int a,int b)
{
	a-=b;
		if (a<0)
			a+=MOD;
	return(a);
}

int Mult(int a,int b)
{
	return((LL)a*b%MOD);
}

int main()
{
	// vars
	int T,t;
	int N;
	int O,Ao,Bo,Co,Do;
	int C,Ac,Bc,Cc,Dc;
	int i,j,k,d,d2,ans;
	int r1,r2,m;
	LL a,b,c;
	static int E[LIM],dist[LIM],sum[LIM];
	static LL D1[LIM],D2[LIM],S1[LIM],S2[LIM];
	static vector<PR> con[LIM];
	priority_queue<PR> Q;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
				Fox(i,N+1)
					con[i].clear();
			Read(O),Read(Ao),Read(Bo),Read(Co),Read(Do);
				Fox(i,N)
				{
					E[i]=O;
					j=(i+1)%N;
					con[i].pb(mp(j,O));
					con[j].pb(mp(i,O));
					O=((LL)Ao*O+Bo)%Co+Do;
				}
			Read(C),Read(Ac),Read(Bc),Read(Cc),Read(Dc);
				Fox(i,N)
				{
					con[N].pb(mp(i,C));
					con[i].pb(mp(N,C));
					C=((LL)Ac*C+Bc)%Cc+Dc;
				}
			// precompute outer distances/sums
			D1[0]=D2[0]=S1[0]=S2[0]=0;
				Fox(i,N*2)
				{
					D1[i+1]=D1[i]+E[i%N];
					D2[i+1]=D2[i]+E[(N*2-i-1)%N];
					S1[i+1]=Add(S1[i],D1[i+1]%MOD);
					S2[i+1]=Add(S2[i],D2[i+1]%MOD);
				}
			// dijkstra's from center
			Fill(dist,60);
			Q.push(mp(0,N)),dist[N]=0;
				while (!Q.empty())
				{
					d=-Q.top().x;
					i=Q.top().y;
					Q.pop();
						if (d!=dist[i])
							continue;
						Fox(j,Sz(con[i]))
						{
							k=con[i][j].x;
							d2=d+con[i][j].y;
								if (d2<dist[k])
									Q.push(mp(-d2,k)),dist[k]=d2;
						}
				}
			// precompute center distance sums
			sum[0]=0;
				Fox(i,N*2)
					sum[i+1]=Add(sum[i],dist[i%N]);
			// process outer points
			j=ans=0;
				Fox(i,N)
				{
					// advance j to furthest node from i (along outside only)
						for(;;)
						{
							c=D1[j]-D1[i];
							a=min(c,D1[N]-c);
							c=D1[j+1]-D1[i];
							b=min(c,D1[N]-c);
								if (b<=a)
									break;
							j++;
						}
					// binary search for furthest node in i..j which is closer along the ouside
					r1=i,r2=j;
						while (r2>r1)
						{
							m=(r1+r2+1)>>1;
								if (D1[m]-D1[i]<dist[i]+dist[m%N])
									r1=m;
								else
									r2=m-1;
						}
					a=r1;
					// binary search for furthest node in j..(i+N) which is closer along the ouside
					r1=j,r2=i+N;
						while (r2>r1)
						{
							m=(r1+r2)>>1;
								if (D1[i+N]-D1[m]<dist[i]+dist[m%N])
									r2=m;
								else
									r1=m+1;
						}
					b=r1;
						if (a==b)
						{
							c=D1[a]-D1[i];
								if (c<D1[N]-c)
									b++;
								else
									a--;
						}
					// add outer distances i -> i..a
					ans=Add(ans,Sub(S1[a],S1[i]));
					ans=Sub(ans,Mult(D1[i]%MOD,a-i));
					// add outer distances i -> b..(i+N)
					ans=Add(ans,Sub(S2[N*2-b],S2[N*2-(i+N)]));
					ans=Sub(ans,Mult(D2[N*2-(i+N)]%MOD,i+N-b));
					// add distances through center i -> (a+1)..(b-1)
						if (a+1<=b-1)
						{
							ans=Add(ans,Mult(dist[i],b-a-1));
							ans=Add(ans,Sub(sum[b],sum[a+1]));
						}
				}
			// add center distances
			ans=Mult(ans,DIV2);
			ans=Add(ans,sum[N]);
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}