XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#49295 #1258. 地底蔷薇 Accepted 100 5529 ms 96264 K C++ 17 / 2.5 K 丁丁跑卡车 2021-06-17 18:18:16
显示原始代码 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ud unsigned int
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
//#define pi 3.141592653589
#define eps 1e-9
#define F(x) ((x) / 3 + ((x) % 3 == 1 ? 0 : tb))
#define G(x) ((x) < tb ? (x)*3 + 1 : ((x)-tb) * 3 + 2)
//#define p 2173412051LL
//#define sz 2

using namespace std;

template <typename T>
void read(T &x) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while (!isdigit(ch)) {
        if (ch == '-')
            f *= -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const ll p = 1e9 + 7;

int n;
int a[2010];
ll inv[2010];
ll sumL[2010][2010], sumR[2010][2010], totL[2010][2010];
ll f[2010][2010];

void pre(int);
int low_bit(int);
void update(ll *, int, ll);
ll query(ll *, int);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 2; i <= n + 1; ++i) {
        cin >> a[i];
        ++a[i];
    }
    a[1] = 1;
    a[n + 2] = n + 2;
    n += 2;
    pre(n);
    for (int len = 2; len <= n + 1; ++len) {
        for (int i = 1, j = len; j <= n; ++i, ++j) {
            if (a[i] >= a[j])
                continue;
            f[i][j] = (query(sumL[i], a[j] - 1) + query(sumR[j], n) - query(sumR[j], a[i]) +
                       query(totL[i], a[j] - 1) + p) *
                      inv[query(totL[i], a[j] - 1)] % p;
            update(sumL[i], a[j], f[i][j]);
            update(sumR[j], a[i], f[i][j]);
            update(totL[i], a[j], 1);
        }
    }
    cout << f[1][n];
    return 0;
}

void pre(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) inv[i] = (p - p / i) * inv[p % i] % p;
}

int low_bit(int x) { return x & -x; }

void update(ll *f, int i, ll x) {
    while (i <= n) {
        f[i] = (f[i] + x) % p;
        i += low_bit(i);
    }
}

ll query(ll *f, int i) {
    ll res = 0;
    while (i) {
        res += f[i];
        i -= low_bit(i);
    }
    return res % p;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：465 ms
内存：96264 KiB

输入文件（random_01.in） 

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
<8798 bytes omitted>

答案文件（random_01.out） 

2000

用户输出 

2000

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（sample_01.in） 

3
3 1 2

答案文件（sample_01.out） 

666666673

用户输出 

666666673

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：54 ms
内存：48624 KiB

输入文件（random_02.in） 

2000
2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 
<8798 bytes omitted>

答案文件（random_02.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：3 ms
内存：888 KiB

输入文件（sample_02.in） 

30
26 16 28 30 23 11 29 18 22 15 20 13 27 9 21 7 5 25 4 19 8 3 1 24 10 14 17 12 2 6

答案文件（sample_02.out） 

297703424

用户输出 

297703424

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：2 ms
内存：328 KiB

输入文件（random_03.in） 

1
1

答案文件（random_03.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：470 ms
内存：96052 KiB

输入文件（random_04.in） 

2000
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36
<8798 bytes omitted>

答案文件（random_04.out） 

964900949

用户输出 

964900949

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：439 ms
内存：96084 KiB

输入文件（random_05.in） 

2000
1246 320 473 1336 755 1463 1509 1713 1778 1406 1438 1012 664 1507 44 1516 306 1419 1363 550 286
<8798 bytes omitted>

答案文件（random_05.out） 

989609100

用户输出 

989609100

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：428 ms
内存：95932 KiB

输入文件（random_06.in） 

2000
1304 1681 1730 1944 245 1774 15 1634 254 1653 659 837 1879 1506 512 1571 123 1738 1651 1514 181
<8798 bytes omitted>

答案文件（random_06.out） 

903963298

用户输出 

903963298

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：435 ms
内存：95948 KiB

输入文件（random_07.in） 

2000
497 837 1125 828 182 1161 1428 1893 1258 429 1311 1374 686 1223 1685 1365 1080 808 1658 155 113
<8798 bytes omitted>

答案文件（random_07.out） 

555364839

用户输出 

555364839

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：433 ms
内存：95940 KiB

输入文件（random_08.in） 

2000
1692 854 278 300 282 811 1510 622 1780 861 181 1972 551 1900 1263 480 1559 1373 98 1301 1671 43
<8798 bytes omitted>

答案文件（random_08.out） 

960859403

用户输出 

960859403

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：439 ms
内存：95988 KiB

输入文件（random_09.in） 

2000
70 59 1152 1991 1137 1043 1432 1706 839 1998 1719 1208 1111 1849 1906 649 80 187 443 26 955 605
<8798 bytes omitted>

答案文件（random_09.out） 

941150290

用户输出 

941150290

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：465 ms
内存：95912 KiB

输入文件（random_10.in） 

2000
1154 754 921 695 1784 1523 1106 881 1873 297 129 1845 496 1104 1509 1996 101 599 1092 767 1290 
<8798 bytes omitted>

答案文件（random_10.out） 

515073153

用户输出 

515073153

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：357 ms
内存：82420 KiB

输入文件（random_11.in） 

1785
148 748 1449 1676 1331 109 639 1337 932 572 1359 204 1038 286 987 1367 203 339 185 1292 1383 25
<7723 bytes omitted>

答案文件（random_11.out） 

676079957

用户输出 

676079957

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：443 ms
内存：93352 KiB

输入文件（random_12.in） 

1961
826 613 452 1355 1174 862 448 1549 1124 196 180 1078 1255 1468 1810 912 1189 1852 1194 831 1369
<8603 bytes omitted>

答案文件（random_12.out） 

715868914

用户输出 

715868914

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：393 ms
内存：85432 KiB

输入文件（random_13.in） 

1833
1032 1306 1801 371 1506 127 1142 1615 1027 62 602 358 1262 1043 1609 1702 1468 1681 603 1430 94
<7963 bytes omitted>

答案文件（random_13.out） 

231149025

用户输出 

231149025

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：55 ms
内存：24896 KiB

输入文件（random_14.in） 

809
533 329 768 540 551 193 650 389 361 330 351 118 787 663 624 539 61 372 549 378 333 600 715 713 7
<3032 bytes omitted>

答案文件（random_14.out） 

474487141

用户输出 

474487141

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：38 ms
内存：19480 KiB

输入文件（random_15.in） 

681
387 191 249 603 24 13 416 473 388 522 497 89 46 628 93 5 149 386 625 312 41 630 43 36 104 126 73
<2520 bytes omitted>

答案文件（random_15.out） 

18920488

用户输出 

18920488

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：50 ms
内存：22792 KiB

输入文件（random_16.in） 

762
268 594 332 676 361 505 34 98 336 670 496 669 634 190 657 529 225 303 36 180 630 123 433 740 760
<2844 bytes omitted>

答案文件（random_16.out） 

55647230

用户输出 

55647230

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：170 ms
内存：54132 KiB

输入文件（random_17.in） 

1338
136 101 470 258 1043 607 783 814 301 137 87 1232 220 46 996 1100 1337 431 48 782 638 618 1161 4
<5488 bytes omitted>

答案文件（random_17.out） 

334227892

用户输出 

334227892

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：267 ms
内存：71364 KiB

输入文件（random_18.in） 

1610
222 1106 504 856 1427 714 263 100 1007 454 130 718 357 1204 77 505 805 257 1382 1008 1533 1202 
<6848 bytes omitted>

答案文件（random_18.out） 

130746815

用户输出 

130746815

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：66 ms
内存：28340 KiB

输入文件（random_19.in） 

890
137 588 631 558 614 464 36 724 456 62 596 381 294 173 790 446 607 196 888 625 855 876 436 800 11
<3356 bytes omitted>

答案文件（random_19.out） 

551733880

用户输出 

551733880

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：14 ms
内存：8564 KiB

输入文件（random_20.in） 

362
50 181 208 99 117 288 124 229 262 192 268 52 249 296 263 180 130 108 8 12 145 325 49 361 139 177
<1244 bytes omitted>

答案文件（random_20.out） 

401464746

用户输出 

401464746

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_21.in） 

8
6 5 1 3 8 2 4 7

答案文件（random_21.out） 

454166673

用户输出 

454166673

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（random_22.in） 

4
1 2 4 3

答案文件（random_22.out） 

3

用户输出 

3

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_23.in） 

10
4 1 2 5 10 3 9 7 8 6

答案文件（random_23.out） 

619523818

用户输出 

619523818

系统信息 

Exited with return code 0
测试点 #26
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（random_24.in） 

1
1

答案文件（random_24.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #27
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（random_25.in） 

3
3 1 2

答案文件（random_25.out） 

666666673

用户输出 

666666673

系统信息 

Exited with return code 0
测试点 #28
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（random_26.in） 

4
1 2 3 4

答案文件（random_26.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #29
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_27.in） 

6
6 5 4 3 2 1

答案文件（random_27.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #30
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（random_28.in） 

1
1

答案文件（random_28.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #31
Accepted
得分：100
用时：2 ms
内存：476 KiB

输入文件（random_29.in） 

7
3 6 1 4 2 7 5

答案文件（random_29.out） 

3

用户输出 

3

系统信息 

Exited with return code 0
测试点 #32
Accepted
得分：100
用时：2 ms
内存：460 KiB

输入文件（random_30.in） 

3
2 3 1

答案文件（random_30.out） 

666666673

用户输出 

666666673

系统信息 

Exited with return code 0
测试点 #33
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_31.in） 

5
2 1 3 4 5

答案文件（random_31.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #34
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_32.in） 

6
1 3 5 4 6 2

答案文件（random_32.out） 

200000005

用户输出 

200000005

系统信息 

Exited with return code 0
测试点 #35
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_33.in） 

8
1 7 3 5 2 4 8 6

答案文件（random_33.out） 

228571434

用户输出 

228571434

系统信息 

Exited with return code 0
测试点 #36
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（random_34.in） 

4
2 1 4 3

答案文件（random_34.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #37
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_35.in） 

10
8 6 2 7 4 9 1 10 5 3

答案文件（random_35.out） 

532063499

用户输出 

532063499

系统信息 

Exited with return code 0
测试点 #38
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_36.in） 

6
5 1 2 3 4 6

答案文件（random_36.out） 

800000010

用户输出 

800000010

系统信息 

Exited with return code 0
测试点 #39
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_37.in） 

8
1 5 8 7 3 4 2 6

答案文件（random_37.out） 

357142863

用户输出 

357142863

系统信息 

Exited with return code 0
测试点 #40
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（random_38.in） 

4
4 3 1 2

答案文件（random_38.out） 

500000005

用户输出 

500000005

系统信息 

Exited with return code 0
测试点 #41
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（random_39.in） 

10
2 1 6 3 8 7 4 9 5 10

答案文件（random_39.out） 

5

用户输出 

5

系统信息 

Exited with return code 0
测试点 #42
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（random_40.in） 

2
2 1

答案文件（random_40.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号