Created
February 4, 2019 09:25
-
-
Save Noobgam/f157a663522f7cba856becbb58b6ecde to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <stdio.h> | |
#include <vector> | |
#include <functional> | |
#include <unordered_set> | |
#include <algorithm> | |
#include <set> | |
#include <map> | |
#include <cmath> | |
#include <string> | |
#include <cstring> | |
#include <ctime> | |
#include <cassert> | |
#include <queue> | |
#include <stack> | |
#include <bitset> | |
using namespace std; | |
long long gcd(long long a, long long b) | |
{ | |
if (a < 0) | |
a = -a; | |
if (b < 0) | |
b = -b; | |
while (a && b) | |
{ | |
if (a > b) | |
a %= b; | |
else | |
b %= a; | |
} | |
return a ? a : b; | |
} | |
const int MOD = 998244353; | |
long long mult(long long a, long long b) { | |
return (a * b) % MOD; | |
} | |
void Mult(long long& a, long long b) { | |
a *= b; | |
a %= MOD; | |
} | |
int add(int a, int b) { | |
a += b; | |
if (a >= MOD) | |
return a - MOD; | |
return a; | |
} | |
int sub(int a, int b) { | |
a -= b; | |
if (a < 0) | |
return a + MOD; | |
return a; | |
} | |
long long binpow(long long a, long long b) { | |
long long res = 1; | |
while (b) { | |
if (b & 1) { | |
Mult(res, a); | |
} | |
Mult(a, a); | |
b >>= 1; | |
} | |
return res; | |
} | |
inline long long inverse(long long x) { | |
return binpow(x, MOD - 2); | |
} | |
struct fraction | |
{ | |
long long a; | |
fraction() | |
{ | |
a = 0; | |
} | |
fraction(long long _a) { | |
if (_a < 0) | |
_a += MOD; | |
a = _a; | |
} | |
fraction(long long _a, long long _b) | |
{ | |
if (_a < 0) | |
_a += MOD; | |
a = mult(_a, inverse(_b)); | |
} | |
void relax() | |
{ | |
} | |
}; | |
fraction operator +(const fraction a, const fraction b) | |
{ | |
fraction c(add(a.a, b.a)); | |
c.relax(); | |
return c; | |
} | |
fraction operator -(const fraction a, const fraction b) | |
{ | |
fraction c(sub(a.a, b.a)); | |
c.relax(); | |
return c; | |
} | |
fraction operator *(const fraction a, const fraction b) | |
{ | |
fraction c(mult(a.a, b.a)); | |
c.relax(); | |
return c; | |
} | |
struct polynomial | |
{ | |
vector <fraction> a; | |
polynomial() | |
{ | |
a = vector <fraction>(0); | |
} | |
polynomial(vector<fraction> &c) | |
{ | |
a = c; | |
} | |
fraction eval(fraction x) | |
{ | |
fraction temp(1, 1); | |
fraction ans; | |
for (int i = 0; i < a.size(); ++i, temp = temp * x) | |
ans = ans + temp * a[i]; | |
return ans; | |
} | |
}; | |
vector <int> antiderivative(const vector <int> &a) | |
{ | |
vector <int> b; | |
b.push_back(0); | |
for (int i = 0; i < a.size(); ++i) | |
b.push_back(mult(a[i], inverse(i + 1))); | |
return b; | |
} | |
vector <int> derivative(const vector <int> &a) | |
{ | |
vector <int> b; | |
for (int i = 1; i < a.size(); ++i) | |
b.push_back(mult(a[i], i)); | |
return b; | |
} | |
int generator(int p = MOD) { | |
vector<int> fact; | |
int phi = p - 1, n = phi; | |
for (int i = 2; i*i <= n; ++i) | |
if (n % i == 0) { | |
fact.push_back(i); | |
while (n % i == 0) | |
n /= i; | |
} | |
if (n > 1) | |
fact.push_back(n); | |
for (int res = 2; res <= p; ++res) { | |
bool ok = true; | |
for (size_t i = 0; i < fact.size() && ok; ++i) | |
ok &= binpow(res, phi / fact[i]) != 1; | |
if (ok) return res; | |
} | |
return -1; | |
} | |
const int G_ROOT = generator(); | |
void fft(vector<int> & a, bool invert) { | |
int n = (int)a.size(); | |
int DEG = (MOD - 1) / n; | |
const int root = binpow(G_ROOT, DEG); | |
const int root_1 = inverse(root); | |
const int root_pw = n; | |
for (int i = 1, j = 0; i < n; ++i) { | |
int bit = n >> 1; | |
for (; j >= bit; bit >>= 1) | |
j -= bit; | |
j += bit; | |
if (i < j) | |
swap(a[i], a[j]); | |
} | |
for (int len = 2; len <= n; len <<= 1) { | |
int wlen = invert ? root_1 : root; | |
for (int i = len; i < root_pw; i <<= 1) | |
wlen = int(wlen * 1ll * wlen % MOD); | |
for (int i = 0; i < n; i += len) { | |
int w = 1; | |
for (int j = 0; j < len / 2; ++j) { | |
int u = a[i + j]; | |
int v = mult(a[i + j + len / 2], w); | |
a[i + j] = add(u, v); | |
a[i + j + len / 2] = sub(u, v); | |
w = mult(w, wlen); | |
} | |
} | |
} | |
if (invert) { | |
int nrev = inverse(n); | |
for (int i = 0; i < n; ++i) | |
a[i] = mult(a[i], nrev); | |
} | |
} | |
vector <int> product(vector <int> a, vector <int> b) { | |
int n = 1; | |
while (n <= (a.size() + b.size())) { | |
n <<= 1; | |
} | |
a.resize(n); | |
b.resize(n); | |
vector <int> c(n); | |
fft(a, false); | |
fft(b, false); | |
for (int i = 0; i < n; ++i) { | |
c[i] = mult(a[i], b[i]); | |
} | |
fft(c, true); | |
while (c.back() == 0) { | |
c.pop_back(); | |
} | |
return c; | |
} | |
int eval(const vector <int>& a, int x) | |
{ | |
int temp = 1; | |
int ans = 0; | |
for (int i = 0; i < a.size(); ++i, temp = mult(temp, x)) | |
ans = add(ans, mult(temp, a[i])); | |
return ans; | |
} | |
int solver(int n, vector <int> t) | |
{ | |
sort(t.begin(), t.end()); | |
vector <int> v = { 1 }; | |
vector <vector <int>> prod; | |
for (int j = 0; j < n; ++j) //only these things can happen on this interval, interval is [t[i - 1]..t[i]) | |
{ | |
prod.push_back({ 1, sub(0, inverse(t[j])) }); | |
} | |
std::function<vector<int>(int, int)> multiply, multiply2; | |
multiply = [&](int l, int r) { | |
if (l == r - 1) { | |
return prod[l]; | |
} | |
int mid = (l + r) / 2; | |
return product(multiply(l, mid), multiply(mid, r)); | |
}; | |
multiply2 = [&](int l, int r) { | |
vector <int> vv = { 1 }; | |
for (int i = l; i < r; ++i) { | |
vv = product(vv, prod[i]); | |
} | |
return vv; | |
}; | |
v = multiply(0, n); | |
//auto vv2 = multiply2(0, n); | |
//assert(v == multiply2(0, n)); | |
for (auto& x : v) { | |
x = sub(0, x); | |
} | |
v[0] = add(v[0], 1); | |
v = derivative(v); | |
vector <int> here; | |
here = { 0 }; | |
for (auto x : v) { | |
here.push_back(x); | |
} | |
v = here; | |
v = antiderivative(v); | |
int answer = eval(v, t[0]); | |
return answer; | |
} | |
const int iterations = 1e7; | |
int main() | |
{ | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
cout.tie(0); | |
int n; | |
cin >> n; | |
vector <int> t(n); | |
for (int i = 0; i < n; ++i) | |
cin >> t[i]; | |
int ans = solver(n, t); | |
cout << ans << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment