Submission #945030
Source Code Expand
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author RiaD
*/
#include <iostream>
#include <fstream>
#include <iostream>
#include <vector>
#include <cstddef>
#include <type_traits>
template <typename T, typename = std::true_type>
struct IdentityHelper;
template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
static T identity() {
return 1;
}
};
template <typename T>
T identity() {
return IdentityHelper<T>::identity();
}
template <bool b, typename T = void>
using enable_if_t = typename std::enable_if<b, T>::type;
#include <iterator>
#include <string>
#include <stdexcept>
#ifndef SPCPPL_ASSERT
#ifdef SPCPPL_DEBUG
#define SPCPPL_ASSERT(condition) \
if(!(condition)) { \
throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
}
#else
#define SPCPPL_ASSERT(condition)
#endif
#endif
/**
* Support decrementing and multi-passing, but not declared bidirectional(or even forward) because
* it's reference type is not a reference.
*
* It doesn't return reference because
* 1. Anyway it'll not satisfy requirement [forward.iterators]/6
* If a and b are both dereferenceable, then a == b if and only if *a and
* b are bound to the same object.
* 2. It'll not work with reverse_iterator that returns operator * of temporary which is temporary for this iterator
*
* Note, reverse_iterator is not guaranteed to work now too since it works only with bidirectional iterators,
* but it's seems to work at least on my implementation.
*
* It's not really useful anywhere except iterating anyway.
*/
template <typename T>
class IntegerIterator: public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
public:
explicit IntegerIterator(T value): value(value) {
}
IntegerIterator& operator++() {
++value;
return *this;
}
IntegerIterator operator++(int) {
IntegerIterator copy = *this;
++value;
return copy;
}
IntegerIterator& operator--() {
--value;
return *this;
}
IntegerIterator operator--(int) {
IntegerIterator copy = *this;
--value;
return copy;
}
T operator*() const {
return value;
}
bool operator==(IntegerIterator rhs) const {
return value == rhs.value;
}
bool operator!=(IntegerIterator rhs) const {
return !(*this == rhs);
}
private:
T value;
};
template <typename T>
class IntegerRange {
public:
IntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin <= end);
}
IntegerIterator<T> begin() const {
return IntegerIterator<T>(begin_);
}
IntegerIterator<T> end() const {
return IntegerIterator<T>(end_);
}
private:
T begin_;
T end_;
};
template <typename T>
class ReversedIntegerRange {
typedef std::reverse_iterator<IntegerIterator<T>> IteratorType;
public:
ReversedIntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin >= end);
}
IteratorType begin() const {
return IteratorType(IntegerIterator<T>(begin_));
}
IteratorType end() const {
return IteratorType(IntegerIterator<T>(end_));
}
private:
T begin_;
T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
return ReversedIntegerRange<T>(from + 1, to);
}
template <typename T>
std::vector<T> factorials(std::size_t maxN) {
std::vector<T> res(maxN + 1);
res[0] = identity<T>();
for (std::size_t i = 1; i <= maxN; ++i) {
res[i] = res[i - 1] * static_cast<long long>(i);
}
return res;
}
template <typename T>
std::vector<std::vector<T>> binomials(std::size_t maxN) {
std::vector<std::vector<T>> res(maxN + 1, std::vector<T>(maxN + 1));
for (std::size_t n = 0; n <= maxN; ++n) {
res[n][0] = identity<T>();
res[n][n] = identity<T>();
for (std::size_t k = 1; k < n; ++k) {
res[n][k] = res[n - 1][k - 1] + res[n - 1][k];
}
}
return res;
}
template <typename T, typename U, typename = enable_if_t<std::is_integral<U>::value>>
T binomial(U n, U k) {
if (k > n || k < 0) {
return T();
}
T res = identity<T>();
for (U i: inclusiveRange(1, k)) {
res *= n - i + 1;
res /= i;
}
return res;
};
template <typename T, typename U, typename = enable_if_t<std::is_integral<U>::value>>
T starsAndBars(U stars, U groups) {
if (groups == 0) {
if (stars == 0) {
return identity<T>();
} else {
return T();
}
}
return binomial<T>(stars + groups - 1, groups - 1);
};
#include <functional>
#include <utility>
template <typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
return true;
}
template <typename T>
constexpr bool hasBegin(...) {
return false;
}
template <typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;
template <typename T, typename Merge>
class SegmentTreeBase {
protected:
SegmentTreeBase(std::size_t n, const T& defaultValue = T(), const Merge& merge = Merge()):
n(n),
defaultValue(defaultValue),
shift(calculateShift(n)),
values(shift << 1, defaultValue),
merge(merge) {
}
template <typename R, typename = enable_if_t<IsContainer<R>::value>>
SegmentTreeBase(const R& range, const T& defaultValue = T(), const Merge& merge = Merge()) :
SegmentTreeBase(
static_cast<std::size_t>(std::distance(std::begin(range), std::end(range))),
defaultValue,
merge
) {
std::copy(std::begin(range), std::end(range), values.begin() + shift);
for (std::size_t index: downrange(shift, static_cast<std::size_t>(1))) {
recalculate(index);
}
}
static std::size_t calculateShift(std::size_t n) {
std::size_t result = 1;
while (result < n) {
result <<= 1;
}
return result;
}
void recalculate(std::size_t index) {
values[index] = merge(values[2 * index], values[2 * index + 1]);
}
std::size_t n;
T defaultValue;
std::size_t shift;
std::vector<T> values;
Merge merge;
};
template <typename T, typename Merge>
class BottomUpSegmentTree: protected SegmentTreeBase<T, Merge> {
public:
template <typename R>
BottomUpSegmentTree(const R& range, const T& defaultValue = T(), const Merge& merge = Merge()):
SegmentTreeBase<T, Merge>(range, defaultValue, merge) {
}
const T& getElement(std::size_t index) {
SPCPPL_ASSERT(index < n);
return values[index + shift];
}
T getResult(std::size_t l, std::size_t r) const {
SPCPPL_ASSERT(l <= r && r <= n);
return internalGetResult(l + shift, r + shift);
}
template <typename Updater>
void update(std::size_t index, const Updater& updater) {
SPCPPL_ASSERT(index < n);
index += shift;
updater(values[index]);
for (std::size_t parent = index / 2; parent > 0; parent /= 2) {
this->recalculate(parent);
}
}
void set(std::size_t index, const T& value) {
return update(index, [&value](T& element) {
element = value;
});
}
protected:
typedef SegmentTreeBase<T, Merge> Base;
using Base::n;
using Base::defaultValue;
using Base::shift;
using Base::values;
using Base::merge;
private:
T internalGetResult(std::size_t l, std::size_t r) const {
if (l == r) {
return defaultValue;
}
if (l & 1) {
return merge(values[l], internalGetResult(l + 1, r));
}
if (r & 1) {
return merge(internalGetResult(l, r - 1), values[r - 1]);
}
return internalGetResult(l / 2, r / 2);
}
};
template <typename T>
class BottomUpSumSegmentTree: public BottomUpSegmentTree<T, std::plus<T>> {
public:
template <typename R>
BottomUpSumSegmentTree(
const R& range,
const T& zero = T()
): BottomUpSegmentTree<T, std::plus<T>>(range, zero) {
}
};
#include <assert.h>
/**
* ax + by = result
*/
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
T d = extendedGcd(b % a, a, y, x);
x -= (b / a) * y;
return d;
}
template <typename T>
class Zn {
public:
Zn(): value(0) {
}
/**
* Instead of ctor, to allow not to normalize in ctor
*/
static Zn valueOf(int value) {
int x = value % mod();
if (x < 0) {
x += mod();
}
return Zn(x);
}
static Zn valueOf(long long value) {
int x = static_cast<int>(value % mod());
if (x < 0) {
x += mod();
}
return Zn(x);
}
static Zn rawValueOf(int value) {
SPCPPL_ASSERT(value >= 0 && value < mod());
return Zn(value);
}
Zn& operator=(int rhs) {
return *this = Zn::valueOf(rhs);
}
Zn& operator=(long long rhs) {
return *this = Zn::valueOf(rhs);
}
Zn& operator+=(const Zn& rhs) {
value += rhs.value;
if (value >= mod()) {
value -= mod();
}
return *this;
}
Zn& operator+=(int rhs) {
return *this += Zn::valueOf(rhs);
}
Zn& operator+=(long long rhs) {
return *this += Zn::valueOf(rhs);
}
Zn& operator-=(const Zn& rhs) {
value -= rhs.value;
if (value < 0) {
value += mod();
}
return *this;
}
Zn& operator-=(int rhs) {
return *this -= Zn::valueOf(rhs);
}
Zn& operator-=(long long rhs) {
return *this -= Zn::valueOf(rhs);
}
Zn& operator*=(const Zn& rhs) {
long long result = static_cast<long long>(value) * static_cast<long long>(rhs.value);
value = static_cast<int>(result % mod());
return *this;
}
Zn& operator*=(int rhs) {
return *this *= Zn::valueOf(rhs);
}
Zn& operator*=(long long rhs) {
return *this *= Zn::valueOf(rhs);
}
Zn operator-() const {
if (value == 0) {
return *this;
}
else {
return Zn(mod() - value);
}
}
Zn& operator/=(const Zn& rhs) {
return *this *= rhs.inversed();
}
Zn& operator/=(int rhs) {
return *this /= Zn::valueOf(rhs);
}
Zn& operator/=(long long rhs) {
return *this /= Zn::valueOf(rhs);
}
bool operator==(const Zn& rhs) const {
return value == rhs.value;
}
Zn inversed() const {
SPCPPL_ASSERT(value != 0);
int x, y;
int gcd = extendedGcd(value, mod(), x, y);
(void) gcd;
SPCPPL_ASSERT(gcd == 1);
if (x < 0) {
x += mod();
}
return Zn(x);
}
template <typename U>
friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);
template <typename U>
friend std::istream& operator>>(std::istream&, Zn<U>& zn);
int intValue() const {
return value;
}
private:
/**
* No normalization performed
*/
explicit Zn(int value): value(value) {
}
int value;
constexpr static int mod() {
return T::value;
}
template <int N = T::value>
static constexpr bool positive_or_runtime(int) {
return N > 0;
}
static constexpr bool positive_or_runtime(...) {
return true;
}
static_assert(
std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
"T::value must be int"
);
static_assert(positive_or_runtime(0), "Mod has to be positive integer");
};
template <typename T>
bool operator==(const Zn<T>& lhs, int rhs) {
return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(int lhs, const Zn<T>& rhs) {
return rhs == lhs;
}
template <typename T>
bool operator==(const Zn<T>& lhs, long long rhs) {
return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(long long lhs, Zn<T>& rhs) {
return rhs == lhs;
}
template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, int rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(int lhs, const Zn<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, long long rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(long long rhs, const Zn<T>& lhs) {
return !(lhs == rhs);
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy += rhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy += rhs;
}
template <typename T>
Zn<T> operator+(int lhs, const Zn<T>& rhs) {
return rhs + lhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy += rhs;
}
template <typename T>
Zn<T> operator+(long long lhs, const Zn<T>& rhs) {
return rhs + lhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy -= rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy -= rhs;
}
template <typename T>
Zn<T> operator-(int lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy -= rhs;
}
template <typename T>
Zn<T> operator-(long lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy *= rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy *= rhs;
}
template <typename T>
Zn<T> operator*(int lhs, const Zn<T>& rhs) {
return rhs * lhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy *= rhs;
}
template <typename T>
Zn<T> operator*(long long lhs, const Zn<T>& rhs) {
return rhs * lhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy /= rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy /= rhs;
}
template <typename T>
Zn<T> operator/(int lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy /= rhs;
}
template <typename T>
Zn<T> operator/(long long lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
return stream << zn.value;
}
template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
long long value;
stream >> value;
zn.value = static_cast<int>(value % T::value);
return stream;
}
template <typename T>
struct IdentityHelper<Zn<T>> {
static Zn<T> identity() {
return Zn<T>::valueOf(1);
}
};
template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;
using namespace std;
class TaskE {
public:
void solve(std::istream& in, std::ostream& out) {
int n;
in >> n;
vector<int> v(n);
vector<int> used(n);
for (int i: range(n)) {
in >> v[i];
--v[i];
if (v[i] != -1) {
++used[v[i]];
}
}
vector<int> unused;
unused.reserve(n);
int allEmptys = 0;
for (int i: range(n)) {
if (!used[i]) {
unused.push_back(i);
++allEmptys;
}
}
using Z = ZnConst<1000000007>;
Z ans;
vector<Z> fact = factorials<Z>(n);
BottomUpSumSegmentTree<int> usedNumbers(n);
int emptys = 0;
Z sumHren;
for (int i: downrange(n)) {
Z curAdd;
if (v[i] != -1) {
int numbersLess = usedNumbers.getResult(0, v[i]);
curAdd += numbersLess;
int emptyLess = (int) (lower_bound(unused.begin(), unused.end(), v[i]) - unused.begin());
if (allEmptys) {
curAdd += Z::valueOf(emptyLess) * emptys / allEmptys;
}
sumHren += (allEmptys - emptyLess);
usedNumbers.set(v[i], 1);
}
else {
curAdd += emptys * Z::rawValueOf(1) / 2;
curAdd += sumHren / Z::valueOf(allEmptys);
++emptys;
}
//cerr << i << ' ' << curAdd << ' ' << curAdd * fact[n - 1 - i] << endl;
ans += curAdd * fact[n - 1 - i];
}
//cerr << ans << endl;
out << (ans + 1) * fact[unused.size()];
}
};
int main() {
std::ios_base::sync_with_stdio(false);
TaskE solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
in.tie(0);
out << std::fixed;
out.precision(20);
return 0;
}
Submission Info
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
700 / 700 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt |
Subtask |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt, 2_051.txt, 2_052.txt, 2_053.txt, 2_054.txt, 2_055.txt, 2_056.txt, 2_057.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
3 ms |
256 KB |
0_001.txt |
AC |
3 ms |
256 KB |
0_002.txt |
AC |
2 ms |
256 KB |
0_003.txt |
AC |
2 ms |
256 KB |
0_004.txt |
AC |
3 ms |
256 KB |
1_005.txt |
AC |
3 ms |
256 KB |
1_006.txt |
AC |
3 ms |
256 KB |
1_007.txt |
AC |
3 ms |
256 KB |
1_008.txt |
AC |
3 ms |
384 KB |
1_009.txt |
AC |
3 ms |
256 KB |
1_010.txt |
AC |
3 ms |
384 KB |
1_011.txt |
AC |
3 ms |
384 KB |
1_012.txt |
AC |
3 ms |
384 KB |
1_013.txt |
AC |
3 ms |
256 KB |
1_014.txt |
AC |
3 ms |
384 KB |
1_015.txt |
AC |
3 ms |
256 KB |
1_016.txt |
AC |
3 ms |
384 KB |
1_017.txt |
AC |
3 ms |
256 KB |
1_018.txt |
AC |
3 ms |
384 KB |
1_019.txt |
AC |
3 ms |
256 KB |
1_020.txt |
AC |
3 ms |
384 KB |
1_021.txt |
AC |
3 ms |
256 KB |
1_022.txt |
AC |
3 ms |
384 KB |
1_023.txt |
AC |
3 ms |
256 KB |
1_024.txt |
AC |
3 ms |
384 KB |
1_025.txt |
AC |
3 ms |
256 KB |
1_026.txt |
AC |
3 ms |
384 KB |
1_027.txt |
AC |
3 ms |
256 KB |
1_028.txt |
AC |
3 ms |
384 KB |
1_029.txt |
AC |
3 ms |
384 KB |
1_030.txt |
AC |
3 ms |
384 KB |
1_031.txt |
AC |
3 ms |
384 KB |
1_032.txt |
AC |
3 ms |
384 KB |
2_033.txt |
AC |
97 ms |
12160 KB |
2_034.txt |
AC |
50 ms |
6272 KB |
2_035.txt |
AC |
139 ms |
11904 KB |
2_036.txt |
AC |
145 ms |
11392 KB |
2_037.txt |
AC |
166 ms |
11776 KB |
2_038.txt |
AC |
141 ms |
10880 KB |
2_039.txt |
AC |
199 ms |
11520 KB |
2_040.txt |
AC |
87 ms |
5888 KB |
2_041.txt |
AC |
179 ms |
11264 KB |
2_042.txt |
AC |
37 ms |
2560 KB |
2_043.txt |
AC |
206 ms |
11136 KB |
2_044.txt |
AC |
136 ms |
8832 KB |
2_045.txt |
AC |
208 ms |
10880 KB |
2_046.txt |
AC |
214 ms |
10624 KB |
2_047.txt |
AC |
237 ms |
10624 KB |
2_048.txt |
AC |
92 ms |
5120 KB |
2_049.txt |
AC |
224 ms |
10496 KB |
2_050.txt |
AC |
140 ms |
8320 KB |
2_051.txt |
AC |
136 ms |
10240 KB |
2_052.txt |
AC |
123 ms |
9600 KB |
2_053.txt |
AC |
101 ms |
12160 KB |
2_054.txt |
AC |
149 ms |
10240 KB |
2_055.txt |
AC |
117 ms |
10240 KB |
2_056.txt |
AC |
118 ms |
10240 KB |
2_057.txt |
AC |
124 ms |
11264 KB |