QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188100#7237. Sort it!ucup-team004AC ✓73ms18916kbC++207.1kb2023-09-25 14:54:522023-09-25 14:54:52

Judging History

你现在查看的是最新测评结果

  • [2023-09-25 14:54:52]
  • 评测
  • 测评结果：AC
  • 用时：73ms
  • 内存：18916kb
查看
  • [2023-09-25 14:54:52]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template<i64 P>
struct MLong {
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(i64 x) : x{norm(x % getMod())} {}
    
    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    explicit constexpr operator i64() const {
        return x;
    }
    constexpr MLong operator-() const {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MLong &operator*=(MLong rhs) & {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n = 0) {
        init(n);
    }
    
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }
    
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<int> p(n);
    for (int i = 0; i < n; i++) {
        std::cin >> p[i];
        p[i]--;
    }
    
    Z ans = 0;
    std::vector S(n + 1, std::vector<Z>(n + 1));
    for (int i = 0; i <= n; i++) {
        S[i][0] = (i == 0);
        for (int j = 1; j <= i; j++) {
            S[i][j] = S[i - 1][j - 1] + S[i - 1][j] * j;
        }
    }
    
    std::vector<Z> dp(n);
    Z fac = 1;
    for (int k = 1; k <= n; k++) {
        fac *= k;
        Fenwick<Z> fen(n);
        if (k == 1) {
            std::fill(dp.begin(), dp.end(), 1);
        } else {
            for (int i = 0; i < n; i++) {
                fen.add(p[i], dp[i]);
                dp[i] = fen.sum(p[i]);
            }
        }
        Z res = std::accumulate(dp.begin(), dp.end(), Z(0));
        ans += res * S[n][k] * fac;
    }
    std::cout << ans << "\n";
    
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3456kb

input:

2
2 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

3
2 1 3

output:

15

result:

ok 1 number(s): "15"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

2
1 2

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

3
1 2 3

output:

27

result:

ok 1 number(s): "27"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

3
1 3 2

output:

15

result:

ok 1 number(s): "15"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

3
2 3 1

output:

9

result:

ok 1 number(s): "9"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

3
3 1 2

output:

9

result:

ok 1 number(s): "9"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

3
3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

8
3 1 2 7 6 8 5 4

output:

149984

result:

ok 1 number(s): "149984"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

15
15 5 4 9 7 10 3 13 14 1 8 11 2 6 12

output:

600062423

result:

ok 1 number(s): "600062423"

Test #12:

score: 0
Accepted
time: 13ms
memory: 6164kb

input:

894
670 618 579 212 780 557 380 412 672 8 777 117 684 768 99 404 140 122 139 329 623 17 645 18 880 790 625 505 307 747 801 754 783 146 757 263 285 228 719 640 199 193 105 234 847 842 348 159 823 577 466 133 850 851 643 802 819 317 826 55 617 690 604 229 570 254 759 575 498 240 397 736 864 415 751 49...

output:

333399230

result:

ok 1 number(s): "333399230"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

271
267 262 148 36 96 73 257 70 18 200 103 201 77 88 54 126 178 172 56 171 105 10 125 102 79 255 218 260 64 249 107 16 83 121 222 205 217 184 244 120 190 2 63 183 196 215 149 37 179 127 168 247 233 41 23 67 110 71 14 81 57 157 241 162 143 85 122 195 98 101 151 221 243 39 91 203 3 154 62 137 251 6 15...

output:

385331618

result:

ok 1 number(s): "385331618"

Test #14:

score: 0
Accepted
time: 72ms
memory: 18908kb

input:

2000
381 165 79 257 1037 1970 548 536 1312 1164 460 1189 380 950 1666 1491 1300 49 1414 786 1201 1364 1236 1519 182 1662 1578 1228 298 427 1511 1409 518 595 378 1737 183 929 899 1674 262 992 1246 563 1138 544 541 1527 1634 1963 166 1337 1656 1405 1693 1969 68 528 229 310 322 1922 1000 371 623 1830 7...

output:

916831570

result:

ok 1 number(s): "916831570"

Test #15:

score: 0
Accepted
time: 72ms
memory: 18844kb

input:

2000
433 1306 1470 1177 891 333 237 26 1070 637 487 725 1222 133 826 1797 1213 351 1888 1272 1628 52 1691 1830 776 352 198 1788 1444 1187 1741 1709 1352 1388 1492 86 120 332 1844 113 1652 523 962 1858 1126 1765 1302 285 85 960 1529 1457 1344 1916 773 769 1729 387 129 649 1182 569 1209 51 1308 104 63...

output:

709731050

result:

ok 1 number(s): "709731050"

Test #16:

score: 0
Accepted
time: 73ms
memory: 18856kb

input:

2000
338 1210 597 105 357 82 928 1879 1760 341 1961 1445 1169 1832 1460 1791 1597 1315 1270 744 1344 1511 599 90 349 811 125 840 1935 1711 995 1002 159 1769 859 1754 889 751 1186 1336 1496 1092 413 405 1077 586 705 150 567 426 1357 180 1404 138 668 825 36 276 133 333 1590 1265 830 873 1453 1949 1520...

output:

499882073

result:

ok 1 number(s): "499882073"

Test #17:

score: 0
Accepted
time: 61ms
memory: 18856kb

input:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

596636543

result:

ok 1 number(s): "596636543"

Test #18:

score: 0
Accepted
time: 62ms
memory: 18820kb

input:

2000
1 2 1192 4 5 6 7 8 9 10 11 12 13 14 15 16 336 18 19 20 341 22 23 24 25 1396 1558 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 187 55 56 57 58 975 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 1551 80 81 82 83 124 85 86 1412 88 89 90 1966 92 93 94 95 9...

output:

336718679

result:

ok 1 number(s): "336718679"

Test #19:

score: 0
Accepted
time: 61ms
memory: 18844kb

input:

2000
1 2 3 4 5 6 7 1330 9 10 11 12 13 14 15 16 374 1423 19 20 498 22 515 44 390 26 726 28 944 30 31 32 33 186 35 36 37 38 988 40 41 42 43 24 45 46 47 48 49 888 51 52 53 344 55 56 57 1944 59 60 61 62 63 1914 677 317 804 68 69 70 1939 1022 1550 74 75 76 77 78 79 80 81 67 691 84 1655 86 87 88 89 90 91 ...

output:

31673026

result:

ok 1 number(s): "31673026"

Test #20:

score: 0
Accepted
time: 61ms
memory: 18832kb

input:

2000
2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942 ...

output:

2000

result:

ok 1 number(s): "2000"

Test #21:

score: 0
Accepted
time: 55ms
memory: 18916kb

input:

2000
2000 1999 809 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1665 1983 1982 1981 1660 1979 1978 1977 1976 605 443 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1814 1946 1945 1944 1943 1026 194...

output:

424669338

result:

ok 1 number(s): "424669338"

Test #22:

score: 0
Accepted
time: 60ms
memory: 18896kb

input:

2000
2000 1999 1998 1997 1996 1995 1994 671 1992 1991 1990 1989 1988 1987 1986 1985 1627 578 1982 1981 1503 1979 1486 1957 1611 1975 1275 1973 1057 1971 1970 1969 1968 1815 1966 1965 1964 1963 1013 1961 1960 1959 1958 1977 1956 1955 1954 1953 1952 1113 1950 1949 1948 1657 1946 1945 1944 57 1942 1941...

output:

94089828

result:

ok 1 number(s): "94089828"
English 繁體中文 简体中文

服务器时间: 2024-12-05 00:07:57 | 开源项目