Submission #948092
Source Code Expand
#include <iostream> #include <vector> using namespace std; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n==0)?1:10*TEN(n-1); } template<uint MD> struct ModInt { uint v; ModInt() : v{0} {} ModInt(ll v) : v{normS(v%MD+MD)} {} static uint normS(const uint &x) {return (x<MD)?x:x-MD;}; static ModInt make(const uint &x) {ModInt m; m.v = x; return m;} const ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));} const ModInt operator-(const ModInt &r) const {return make(normS(v+normS(MD-r.v)));} const ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);} ModInt& operator+=(const ModInt &r) {return *this=*this+r;} ModInt& operator-=(const ModInt &r) {return *this=*this-r;} ModInt& operator*=(const ModInt &r) {return *this=*this*r;} static ModInt inv(const ModInt &x) { return pow(ModInt(x), MD-2); } }; using Mint = ModInt<TEN(9)+7>; /** * Fenwick Tree * * 0-indexed */ template<class T> struct Fenwick { int N; vector<T> seg; Fenwick(int N) : N(N) { seg.resize(N+1); fill_n(begin(seg), N+1, 0); } /// i番目の要素にxを追加する void add(int i, T x) { i++; while (i <= N) { seg[i] += x; i += i & -i; } } /// [0, i)のsum T sum(int i) { T s{0}; while (i > 0) { s += seg[i]; i -= i & -i; } return s; } /// [a, b)のsum T sum(int a, int b) { return sum(b) - sum(a); } }; const int MN = 500500; Mint fact[MN]; void first() { fact[0] = 1; for (int i = 1; i < MN; i++) { fact[i] = fact[i-1]*i; } } int main() { first(); int n, m = 0; cin >> n; int a[n]; Fenwick<int> unfw(n); for (int i = 0; i < n; i++) { unfw.add(i, 1); } for (int i = 0; i < n; i++) { cin >> a[i]; a[i]--; if (a[i] == -1) { m++; } else { unfw.add(a[i], -1); } } Mint ans = 0; int unfix = 0; Mint unfix_fix = 0; Fenwick<int> fw(n); for (int i = n-1; i >= 0; i--) { int d = a[i]; Mint res = 0; if (d == -1) { res += unfix_fix * fact[m-1]; if (unfix) { Mint mc2 = ull(m) * (m-1) / 2; res += Mint(unfix) * mc2 * fact[m-2]; } unfix++; } else { int co = fw.sum(d); res += fact[m] * co; res += Mint(unfix) * unfw.sum(d) * fact[m-1]; unfix_fix += unfw.sum(d, n); fw.add(d, 1); } ans += res * fact[n-1-i]; // cout << res.v << " " << ans.v << endl; } ans += fact[m]; cout << ans.v << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | yosupo |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 2960 Byte |
Status | AC |
Exec Time | 233 ms |
Memory | 8064 KB |
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 | 6 ms | 2176 KB |
0_001.txt | AC | 6 ms | 2176 KB |
0_002.txt | AC | 6 ms | 2176 KB |
0_003.txt | AC | 6 ms | 2176 KB |
0_004.txt | AC | 6 ms | 2176 KB |
1_005.txt | AC | 6 ms | 2176 KB |
1_006.txt | AC | 6 ms | 2176 KB |
1_007.txt | AC | 6 ms | 2176 KB |
1_008.txt | AC | 7 ms | 2176 KB |
1_009.txt | AC | 7 ms | 2176 KB |
1_010.txt | AC | 7 ms | 2176 KB |
1_011.txt | AC | 7 ms | 2176 KB |
1_012.txt | AC | 7 ms | 2176 KB |
1_013.txt | AC | 7 ms | 2176 KB |
1_014.txt | AC | 7 ms | 2176 KB |
1_015.txt | AC | 7 ms | 2176 KB |
1_016.txt | AC | 7 ms | 2176 KB |
1_017.txt | AC | 6 ms | 2176 KB |
1_018.txt | AC | 7 ms | 2176 KB |
1_019.txt | AC | 7 ms | 2176 KB |
1_020.txt | AC | 7 ms | 2176 KB |
1_021.txt | AC | 7 ms | 2176 KB |
1_022.txt | AC | 7 ms | 2176 KB |
1_023.txt | AC | 7 ms | 2176 KB |
1_024.txt | AC | 7 ms | 2176 KB |
1_025.txt | AC | 6 ms | 2176 KB |
1_026.txt | AC | 7 ms | 2176 KB |
1_027.txt | AC | 7 ms | 2176 KB |
1_028.txt | AC | 7 ms | 2176 KB |
1_029.txt | AC | 7 ms | 2176 KB |
1_030.txt | AC | 7 ms | 2176 KB |
1_031.txt | AC | 7 ms | 2176 KB |
1_032.txt | AC | 7 ms | 2176 KB |
2_033.txt | AC | 104 ms | 8064 KB |
2_034.txt | AC | 55 ms | 5120 KB |
2_035.txt | AC | 121 ms | 8064 KB |
2_036.txt | AC | 110 ms | 7552 KB |
2_037.txt | AC | 136 ms | 8064 KB |
2_038.txt | AC | 119 ms | 7296 KB |
2_039.txt | AC | 150 ms | 8064 KB |
2_040.txt | AC | 77 ms | 5120 KB |
2_041.txt | AC | 165 ms | 8064 KB |
2_042.txt | AC | 34 ms | 3328 KB |
2_043.txt | AC | 179 ms | 8064 KB |
2_044.txt | AC | 118 ms | 6016 KB |
2_045.txt | AC | 197 ms | 8064 KB |
2_046.txt | AC | 185 ms | 7808 KB |
2_047.txt | AC | 205 ms | 8064 KB |
2_048.txt | AC | 91 ms | 4736 KB |
2_049.txt | AC | 219 ms | 8064 KB |
2_050.txt | AC | 142 ms | 6016 KB |
2_051.txt | AC | 233 ms | 8064 KB |
2_052.txt | AC | 218 ms | 7424 KB |
2_053.txt | AC | 104 ms | 8064 KB |
2_054.txt | AC | 233 ms | 8064 KB |
2_055.txt | AC | 222 ms | 8064 KB |
2_056.txt | AC | 216 ms | 8064 KB |
2_057.txt | AC | 161 ms | 8064 KB |