In this HackerEarth Dexter and Points, problem solution Dexter has you on his kill table now. He gives you one last chance to survive. He gives you a problem to solve. If you solve the problem correctly, he will let you go, else he will kill you.

You are given N integers a1,a2,,...,aN. Consider an N-dimensional hyperspace. Let (x1,x2,...,xN) be a point in this hyperspace and all xi for i related [1,N] are integers. Now, Dexter gives you a set which contains all the points such that 0 <= xi <= ai for i related [1,N]. Find the number of ways to select two points A and B from this set, such that the midpoint of A and B also lies in this set.

As the required number can be really large, find the answer modulo 10^9 + 7.


HackerEarth Dexter and Points problem solution


HackerEarth Dexter and Points problem solution.

#include <bits/stdc++.h>
using namespace std;

#define TRACE
#ifdef TRACE
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define TR(...)
#endif

typedef long long LL;
typedef vector < int > VI;
typedef pair < int,int > II;
typedef vector < II > VII;

#define MOD 1000000007
#define EPS 1e-12
#define N 200100
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(v) v.begin(),v.end()
#define SZ(a) (int)a.size()
#define FILL(a,b) memset(a,b,sizeof(a))
#define SI(n) scanf("%d",&n)
#define SLL(n) scanf("%lld",&n)
#define PLLN(n) printf("%lld\n",n)
#define PIN(n) printf("%d\n",n)
#define REP(i,j,n) for(LL i=j;i<n;i++)
#define PER(i,j,n) for(LL i=n-1;i>=j;i--)
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define FILEIO(name) \
freopen(name".in", "r", stdin); \
freopen(name".out", "w", stdout);

inline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }
inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }
inline int sub(int a , int b) { return a - b < 0 ? MOD - b + a : a - b; }
LL powmod(LL a,LL b) { if(b==0)return 1; LL x=powmod(a,b/2); LL y=(x*x)%MOD; if(b%2) return (a*y)%MOD; return y%MOD; }

int a[N];
int inv;
inline int nP2(int x) {
return mult(x, x-1);
}
int main() {
inv = powmod(2,MOD-2);
int n; cin >> n;
assert(n >= 1 && n <= 100000);
for(int i = 0; i < n; i ++) {
cin >> a[i];
assert(a[i] >= 0 && a[i] <= 1000000000);
}
int ans = 1;
for(int i = 0; i < n; i ++) {
int tmp = a[i]+1;
if(a[i] & 1) {
int x = (a[i]+1)/2;
tmp = add(tmp, mult(2,nP2(x)));
}
else {
int x = a[i]/2;
tmp = add(tmp, nP2(x));
x ++;
tmp = add(tmp, nP2(x));
}
ans = mult(ans, tmp);
}
cout << ans << endl;
return 0;
}