XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#49222 #1258. 地底蔷薇 Accepted 100 18544 ms 116980 K C++ 17 / 1.5 K wahahah 2021-05-28 21:31:44
显示原始代码 
#include <bits/stdc++.h>
#define PI 3.141592653589793238462
#define eps 1e-20
#define fi first
#define se second
using namespace std;
using cd = complex<double>;
typedef long long ll;
typedef long double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
ll tree[3][2005][2005], a[2005], mod = 1e9 + 7, n, c[2005], d[2005][2005];
void add(ll t, ll s, ll x, ll v) {
    while (x <= n + 2) {
        tree[t][s][x] += v;
        tree[t][s][x] %= mod;
        x += x & (-x);
    }
}
ll query(ll t, ll s, ll x) {
    ll res = 0;
    while (x) {
        res += tree[t][s][x];
        x -= x & (-x);
        res %= mod;
    }
    return res % mod;
}
ll qpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1)
            res = res * x % mod;
        y /= 2;
        x = x * x % mod;
    }
    return res % mod;
}
int main() {
    cin >> n;
    for (ll i = 2; i <= n + 1; i++) {
        cin >> a[i];
        a[i]++;
    }
    for (ll i = 1; i <= n + 2; i++) {
        c[i] = qpow(i, mod - 2);
    }
    a[1] = 1;
    a[n + 2] = n + 2;
    for (ll i = 1; i <= n + 2; i++) {
        for (ll j = i - 1; j > 0; j--) {
            if (a[i] > a[j]) {
                ll num = query(0, i, a[i] - 1) - query(0, i, a[j]);
                ll v1 = query(1, i, a[i] - 1) - query(1, i, a[j]);
                ll v2 = query(2, j, a[i] - 1) - query(2, j, a[j]);
                v1 = (v1 % mod + mod) % mod;
                v2 = (v2 % mod + mod) % mod;
                if (num) {
                    d[j][i] = 1 + (v1 + v2) % mod * c[num] % mod;
                    d[j][i] %= mod;
                }
            }
            add(0, i, a[j], 1);
            add(1, i, a[j], d[j][i]);
            add(2, j, a[i], d[j][i]);
        }
    }
    cout << d[1][n + 2] << endl;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：1673 ms
内存：101056 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
用时：563 ms
内存：89204 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
用时：2 ms
内存：760 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
内存：376 KiB

输入文件（random_03.in） 

1
1

答案文件（random_03.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：1652 ms
内存：101880 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
用时：1423 ms
内存：116980 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
用时：1431 ms
内存：116936 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
用时：1423 ms
内存：116952 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
用时：1455 ms
内存：116912 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
用时：1472 ms
内存：116980 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
用时：1487 ms
内存：116920 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
用时：1181 ms
内存：103412 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
用时：1331 ms
内存：114420 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
用时：1181 ms
内存：106460 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
用时：187 ms
内存：31172 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
用时：129 ms
内存：23796 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
用时：165 ms
内存：28456 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
用时：604 ms
内存：70644 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
用时：879 ms
内存：92532 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
用时：226 ms
内存：36212 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
用时：36 ms
内存：9668 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
内存：376 KiB

输入文件（random_27.in） 

6
6 5 4 3 2 1

答案文件（random_27.out） 

1

用户输出 

1

系统信息 

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

输入文件（random_28.in） 

1
1

答案文件（random_28.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #31
Accepted
得分：100
用时：2 ms
内存：504 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
内存：376 KiB

输入文件（random_30.in） 

3
2 3 1

答案文件（random_30.out） 

666666673

用户输出 

666666673

系统信息 

Exited with return code 0
测试点 #33
Accepted
得分：100
用时：2 ms
内存：376 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
内存：376 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
内存：476 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
内存：376 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号