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
AC × 5
AC × 33
AC × 58
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