Header Ad

HackerEarth Cost Recovery problem solution

In this HackerEarth Cost Recovery problem solution Alice is studying the cost of packing chocolates. She has already collected and analyzed some data. Chocolates are packed in boxes that have very weird pricing: it changes as you buy more boxes. The first box one buys always costs b1 burles, the second one costs b2 burles and so on. Some boxes can even have negative price: meaning Alice gets the box for free and additionally gets some burles. Alice has collected the values of b1,b2,...,bn and wrote them down.

Next, she has also computed the sum of all possible distribution and packaging of chocolates. Specifically, for each positive integer k not greater than n: Alice has considered all possible ways to partition k chocolates of different flavors into some boxes, computed the cost of buying those boxes, and added all these costs up to obtain the total cost ak. She has also written down the values of a1,a2,...,an. 

Getting a good night's sleep, she finds out to her horror in the morning that Wakandan spies stole her sheet containing values of b1,b2,...,bn. So she asks for your help in recovering the values. But she does not need all the costs to complete her research, only the values of bl,bl+1,...,br.


HackerEarth Cost Recovery problem solution


HackerEarth Cost Recovery problem solution.

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

const ld PI = acos(-1);
const int MAX = 1 << 18;
const int MOD = 1e9 + 7;

int bigMod (int a, int e) {
if (e == -1) e = MOD - 2;
int ret = 1;
while (e) {
if (e & 1) ret = ret * 1LL * a % MOD;
a = a * 1LL * a % MOD, e >>= 1;
} return ret;
}

int fac[MAX], inv[MAX];

namespace FFT {
struct cp {
ld x, y;

cp (ld x = 0, ld y = 0) : x(x), y(y) {}

cp operator + (const cp &rhs) const {return cp(x + rhs.x, y + rhs.y);}
cp operator - (const cp &rhs) const {return cp(x - rhs.x, y - rhs.y);}
cp operator * (const cp &rhs) const {return cp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);}
cp operator ! () const {return cp(x, -y);}
};

cp rts[MAX + 1];
int bitrev[MAX];
cp f_a[MAX], f_b[MAX];
cp f_c[MAX], f_d[MAX];

void fft_init() {
int k = 0; while (1 << k < MAX) ++k;
bitrev[0] = 0;
for (int i = 1; i < MAX; ++i) {
bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
}
rts[0] = rts[MAX] = cp(1, 0);
for (int i = 1; i + i <= MAX; ++i) {
rts[i] = cp(cos(i * 2 * PI / MAX), sin(i * 2 * PI / MAX));
}
for (int i = MAX / 2 + 1; i < MAX; ++i) {
rts[i] = !rts[MAX - i];
}
}

void dft (cp a[], int n, int sign) {
static int is_init;
if (!is_init) is_init = 1, fft_init();
int d = 0; while ((1 << d) * n != MAX) ++d;
for (int i = 0; i < n; ++i) {
if (i < bitrev[i] >> d) swap(a[i], a[bitrev[i] >> d]);
}
for (int len = 2; len <= n; len <<= 1) {
int delta = MAX / len * sign;
for (int i = 0; i < n; i += len) {
cp *x = a + i, *y = a + i + (len >> 1), *w = sign > 0 ? rts : rts + MAX;
for (int k = 0; k + k < len; ++k) {
cp z = *y * *w;
*y = *x - z, *x = *x + z;
++x, ++y, w += delta;
}
}
}
if (sign < 0) for (int i = 0; i < n; ++i) a[i].x /= n, a[i].y /= n;
}

void multiply (int a[], int b[], int n_a, int n_b, long long c[]) {
int n = n_a + n_b - 1; while (n != n & -n) n += n & -n;
for (int i = 0; i < n; ++i) f_a[i] = f_b[i] = cp();
for (int i = 0; i < n_a; ++i) f_a[i] = cp(a[i]);
for (int i = 0; i < n_b; ++i) f_b[i] = cp(b[i]);
dft(f_a, n, 1), dft(f_b, n, 1);
for (int i = 0; i < n; ++i) f_a[i] = f_a[i] * f_b[i];
dft(f_a, n, -1);
for (int i = 0; i < n; ++i) c[i] = (long long) floor(f_a[i].x + 0.5);
}

void multiply (int a[], int b[], int n_a, int n_b, int c[]) {
int n = n_a + n_b - 1;
while (n != (n & -n)) n += n & -n;
for (int i = 0; i < n; ++i) f_a[i] = f_b[i] = cp();
static const int MAGIC = 15;
for (int i = 0; i < n_a; ++i) f_a[i] = cp(a[i] >> MAGIC, a[i] & (1 << MAGIC) - 1);
for (int i = 0; i < n_b; ++i) f_b[i] = cp(b[i] >> MAGIC, b[i] & (1 << MAGIC) - 1);
dft(f_a, n, 1), dft(f_b, n, 1);
for (int i = 0; i < n; ++i) {
int j = (n - i) % n;
cp x = f_a[i] + !f_a[j];
cp y = f_b[i] + !f_b[j];
cp z = !f_a[j] - f_a[i];
cp t = !f_b[j] - f_b[i];
f_c[i] = (x * t + y * z) * cp(0, 0.25);
f_d[i] = x * y * cp(0, 0.25) + z * t * cp(-0.25, 0);
}
dft(f_c, n, -1), dft(f_d, n, -1);
for (int i = 0; i < n; ++i) {
long long u = ((long long) floor(f_c[i].x + 0.5)) % MOD;
long long v = ((long long) floor(f_d[i].x + 0.5)) % MOD;
long long w = ((long long) floor(f_d[i].y + 0.5)) % MOD;
c[i] = ((u << 15) + v + (w << 30)) % MOD;
}
}

vector <int> multiply (vector <int> a, vector <int> b) {
static int f_a[MAX], f_b[MAX], f_c[MAX];
int n_a = a.size(), n_b = b.size();
for (int i = 0; i < n_a; ++i) f_a[i] = a[i];
for (int i = 0; i < n_b; ++i) f_b[i] = b[i];
multiply(f_a, f_b, n_a, n_b, f_c);
int k = n_a + n_b - 1; vector <int> res(k);
for (int i = 0; i < k; ++i) res[i] = f_c[i];
return res;
}

vector <int> extend (vector <int> a, int c) {
a.insert(a.begin(), 0);
for (int i = 0; i < (int) a.size() - 1; ++i) {
int add = c * 1LL * a[i + 1] % MOD;
a[i] -= add; if (a[i] < 0) a[i] += MOD;
} return a;
}

vector <int> falling_factorial (int n) {
if (!n) return {1}; int m = n >> 1;
if (n & 1) return extend(falling_factorial(n - 1), n - 1);
vector <int> left = falling_factorial(m);
vector <int> one(m + 1), two(m + 1), right(m + 1);
for (int i = 0; i <= m; ++i) one[i] = bigMod(MOD - m, i) * 1LL * inv[i] % MOD;
for (int i = 0; i <= m; ++i) two[i] = left[m - i] * 1LL * fac[m - i] % MOD;
vector <int> three = multiply(one, two);
for (int i = 0; i <= m; ++i) right[i] = three[m - i] * 1LL * inv[i] % MOD;
return multiply(left, right);
}

int dot (vector <int> a, vector <int> b) {
int res = 0;
for (int i = 0; i < (int) min(a.size(), b.size()); ++i) {
int add = a[i] * 1LL * b[i] % MOD;
res += add; if (res >= MOD) res -= MOD;
} return res;
}
}

int main() {
fac[0] = 1;
for (int i = 1; i < MAX; ++i) fac[i] = i * 1LL * fac[i - 1] % MOD;
inv[MAX - 1] = bigMod(fac[MAX - 1], -1);
for (int i = MAX - 1; i; --i) inv[i - 1] = i * 1LL * inv[i] % MOD;
int n, l, r;
scanf("%d %d %d", &n, &l, &r);
vector <int> a(n + 1);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
vector <int> poly = FFT::falling_factorial(l - 1);
int last = FFT::dot(a, poly);
for (int it = l; it <= r; ++it) {
poly = FFT::extend(poly, it - 1);
int cur = FFT::dot(a, poly);
int ans = cur - last; if (ans < 0) ans += MOD;
if (it > l) printf(" ");
printf("%d", ans); last = cur;
}
puts("");
return 0;
}

Second solution

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() {return abs((int) mt());}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

template<const int mod, const int maxf>
struct NTT {
int rts[maxf + 1];
int bitrev[maxf];
int iv[maxf + 1];

int fpow(int a, int k) {
if (!k) return 1;
int res = a, tmp = a;
k--;
while (k) {
if (k & 1) {
res = (long long) res * tmp % mod;
}
tmp = (long long) tmp * tmp % mod;
k >>= 1;
}
return res;
}
int prt() {
vector<int> dvs;
for (int i = 2; i * i < mod; i++) {
if ((mod - 1) % i) continue;
dvs.push_back(i);
if (i * i != mod - 1) dvs.push_back((mod - 1) / i);
}
for (int i = 2; i < mod; i++) {
int flag = 1;
for (int j = 0; j < dvs.size(); j++) {
if (fpow(i, dvs[j]) == 1) {
flag = 0;
break;
}
}
if (flag) return i;
}
assert(0);
return -1;
}
NTT() {
int k = 0; while ((1 << k) < maxf) k++;
bitrev[0] = 0;
for (int i = 1; i < maxf; i++) {
bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
}
int pw = fpow(prt(), (mod - 1) / maxf);
rts[0] = 1;
for (int i = 1; i <= maxf; i++) {
rts[i] = (long long) rts[i - 1] * pw % mod;
}
for (int i = 1; i <= maxf; i <<= 1) {
iv[i] = fpow(i, mod - 2);
}
}
void dft(int a[], int n, int sign) {
int d = 0; while ((1 << d) * n != maxf) d++;
for (int i = 0; i < n; i++) {
if (i < (bitrev[i] >> d)) {
swap(a[i], a[bitrev[i] >> d]);
}
}
for (int len = 2; len <= n; len <<= 1) {
int delta = maxf / len * sign;
for (int i = 0; i < n; i += len) {
int *w = sign > 0 ? rts : rts + maxf;
for (int k = 0; k + k < len; k++) {
int &a1 = a[i + k + (len >> 1)], &a2 = a[i + k];
int t = (long long) *w * a1 % mod;
a1 = a2 - t;
a2 = a2 + t;
a1 += a1 < 0 ? mod : 0;
a2 -= a2 >= mod ? mod : 0;
w += delta;
}
}
}
if (sign < 0) {
int in = iv[n];
for (int i = 0; i < n; i++) {
a[i] = (long long) a[i] * in % mod;
}
}
}
void multiply(int a[], int b[], int na, int nb, int c[]) {
static int fa[maxf], fb[maxf];
int n = na + nb - 1; while (n != (n & -n)) n += n & -n;
for (int i = 0; i < n; i++) fa[i] = fb[i] = 0;
for (int i = 0; i < na; i++) fa[i] = a[i];
for (int i = 0; i < nb; i++) fb[i] = b[i];
dft(fa, n, 1), dft(fb, n, 1);
for (int i = 0; i < n; i++) fa[i] = (long long) fa[i] * fb[i] % mod;
dft(fa, n, -1);
for (int i = 0; i < n; i++) c[i] = fa[i];
}
vector<int> multiply(vector<int> a, vector<int> b) {
static int fa[maxf], fb[maxf], fc[maxf];
int na = a.size(), nb = b.size();
for (int i = 0; i < na; i++) fa[i] = a[i];
for (int i = 0; i < nb; i++) fb[i] = b[i];
multiply(fa, fb, na, nb, fc);
int k = na + nb - 1;
vector<int> res(k);
for (int i = 0; i < k; i++) res[i] = fc[i];
return res;
}
};
const int pr0 = 1004535809; //2^20 * 958 + 1
const int pr1 = 1007681537; //2^20 * 961 + 1
const int pr2 = 1012924417; //2^20 * 966 + 1
int i0, i1, i2;
NTT<pr0, 1 << 18> ntt0;
NTT<pr1, 1 << 18> ntt1;
NTT<pr2, 1 << 18> ntt2;

template<typename num_t>
pair<num_t, num_t> euclid(num_t a, num_t b) {
if (!b) return make_pair(1, 0);
pair<num_t, num_t> r = euclid(b, a % b);
return make_pair(r.second, r.first - a / b * r.second);
}
long long invert(long long a, long long p) {
return (euclid(a, p).fi % p + p) % p;
}

vi multiply(vi a, vi b) {
vi r0 = ntt0.multiply(a, b);
vi r1 = ntt1.multiply(a, b);
vi r2 = ntt2.multiply(a, b);
vi c(sz(a) + sz(b) - 1);
FOR(i, 0, sz(c)) {
__int128 t = 0;
t += (__int128) r0[i] * i0 % pr0 * pr1 * pr2;
t += (__int128) r1[i] * i1 % pr1 * pr2 * pr0;
t += (__int128) r2[i] * i2 % pr2 * pr0 * pr1;
c[i] = t % ((__int128) pr0 * pr1 * pr2) % MOD;
}
return c;
}

void eof() {
string s; assert(!(cin >> s));
}

vi divide(int l, int r) {
if (l == r) {
vi res(2);
res[0] = (MOD - l) % MOD;
res[1] = 1;
return res;
}
return multiply(divide(l, l + r >> 1), divide((l + r >> 1) + 1, r));
}

void chemthan() {
i0 = invert((long long) pr1 * pr2, pr0);
i1 = invert((long long) pr2 * pr0, pr1);
i2 = invert((long long) pr0 * pr1, pr2);
int n, l, r; assert(cin >> n >> l >> r);
assert(1 <= n && n <= 1e5);
assert(1 <= l && l <= r && r <= n);
assert(r - l < 100);
vi a(n + 1);
FOR(i, 1, n + 1) {
assert(cin >> a[i]);
assert(0 <= a[i] && a[i] < 1e9 + 7);
}
eof();
vi c = 2 <= l ? divide(0, l - 2) : vi(1, 1);
int pv = 0;
FOR(i, 1, l) addmod(pv, mult(c[i], a[i]));
FOR(i, l, r + 1) {
vi nc(i + 1);
int d = (MOD - (i - 1)) % MOD;
FOR(j, 0, sz(c)) {
addmod(nc[j + 1], c[j]);
addmod(nc[j], mult(c[j], d));
}
c = nc;
int res = 0;
FOR(j, 1, i + 1) {
addmod(res, mult(c[j], a[j]));
}
cout << (res - pv + MOD) % MOD << " \n"[i == r];
pv = res;
}
}

int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
chemthan();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}

Post a Comment

0 Comments