Submission #947207
Source Code Expand
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <vector> #include <random> #include <list> #include <numeric> using namespace std; typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<ll, int> ll_i; typedef pair<int, ll> i_ll; typedef pair<double, int> d_i; typedef pair<ll, ll> ll_ll; typedef pair<double, double> d_d; struct edge { int u, v; ll w; }; #define rep(i, N) for (int i = 0; i < (int)(N); i++) #define pb push_back int INF = INT_MAX / 10; ll MOD = 1000000007; ll _MOD = 1000000009; double EPS = 1e-10; int pow_mod(ll x, ll n, int M) { ll ans = 1; for (; n; n>>=1) { if (n & 1) ans = ans * x % M; x = x * x % M; } return ans; } ll inv_mod(int x, int p) { return pow_mod(x, p - 2, p); } struct bit { vector<ll> v; bit(int n) : v(n + 1) {} ll sum(int i) { ll res = 0; for (; i > 0; i -= i & -i) res += v[i]; return res; } void add(int i, ll x) { for (i++; i < v.size(); i += i & -i) v[i] += x; } }; int main() { int N; cin >> N; vector<int> a(N); rep(i, N) { scanf("%d", &a[i]); a[i]--; } reverse(a.begin(), a.end()); bit unko(N), unko2(N); rep(i, N) if (a[i] != -1) unko.add(a[i], 1); rep(i, N) if (unko.sum(i + 1) - unko.sum(i) == 0) unko2.add(i, 1); int kakutei = unko.sum(N), mikakutei = unko2.sum(N); int hatena = 0; ll hoge = 0, fact = 1, ans = 0; bit b(N); rep(i, N) { int x = a[i]; ll z = 0; if (x == -1) { z = (hatena * inv_mod(2, MOD) + hoge) % MOD; hatena++; } else { hoge = (hoge + (unko2.sum(N) - unko2.sum(x)) * inv_mod(mikakutei, MOD)) % MOD; z = (b.sum(x) + unko2.sum(x) * inv_mod(mikakutei, MOD) % MOD * hatena) % MOD; b.add(x, 1); } ans = (ans + z * fact) % MOD; fact = fact * (i + 1) % MOD; } ans = (ans + 1) % MOD; for (int i = 1; i <= mikakutei; i++) ans = ans * i % MOD; ans = (ans + MOD) % MOD; cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | sugim48 |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 2287 Byte |
Status | AC |
Exec Time | 701 ms |
Memory | 13952 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:73:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &a[i]); ^
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 | 3 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 | 5 ms | 384 KB |
1_009.txt | AC | 4 ms | 256 KB |
1_010.txt | AC | 5 ms | 384 KB |
1_011.txt | AC | 4 ms | 256 KB |
1_012.txt | AC | 5 ms | 384 KB |
1_013.txt | AC | 3 ms | 256 KB |
1_014.txt | AC | 5 ms | 384 KB |
1_015.txt | AC | 4 ms | 256 KB |
1_016.txt | AC | 5 ms | 384 KB |
1_017.txt | AC | 3 ms | 256 KB |
1_018.txt | AC | 6 ms | 384 KB |
1_019.txt | AC | 4 ms | 256 KB |
1_020.txt | AC | 6 ms | 384 KB |
1_021.txt | AC | 4 ms | 256 KB |
1_022.txt | AC | 6 ms | 384 KB |
1_023.txt | AC | 5 ms | 256 KB |
1_024.txt | AC | 6 ms | 384 KB |
1_025.txt | AC | 3 ms | 256 KB |
1_026.txt | AC | 6 ms | 384 KB |
1_027.txt | AC | 4 ms | 256 KB |
1_028.txt | AC | 5 ms | 384 KB |
1_029.txt | AC | 6 ms | 384 KB |
1_030.txt | AC | 6 ms | 384 KB |
1_031.txt | AC | 6 ms | 384 KB |
1_032.txt | AC | 5 ms | 384 KB |
2_033.txt | AC | 356 ms | 13952 KB |
2_034.txt | AC | 178 ms | 7040 KB |
2_035.txt | AC | 397 ms | 13952 KB |
2_036.txt | AC | 365 ms | 12800 KB |
2_037.txt | AC | 441 ms | 13952 KB |
2_038.txt | AC | 383 ms | 12288 KB |
2_039.txt | AC | 479 ms | 13952 KB |
2_040.txt | AC | 238 ms | 7040 KB |
2_041.txt | AC | 515 ms | 13952 KB |
2_042.txt | AC | 98 ms | 2816 KB |
2_043.txt | AC | 562 ms | 13952 KB |
2_044.txt | AC | 360 ms | 9216 KB |
2_045.txt | AC | 593 ms | 13952 KB |
2_046.txt | AC | 571 ms | 13312 KB |
2_047.txt | AC | 630 ms | 13952 KB |
2_048.txt | AC | 271 ms | 6272 KB |
2_049.txt | AC | 663 ms | 13952 KB |
2_050.txt | AC | 430 ms | 9216 KB |
2_051.txt | AC | 653 ms | 13952 KB |
2_052.txt | AC | 591 ms | 12544 KB |
2_053.txt | AC | 356 ms | 13952 KB |
2_054.txt | AC | 701 ms | 13952 KB |
2_055.txt | AC | 619 ms | 13952 KB |
2_056.txt | AC | 617 ms | 13952 KB |
2_057.txt | AC | 511 ms | 13952 KB |