XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#47981 #1258. 地底蔷薇 Accepted 100 4935 ms 73116 K C++ 17 / 1.3 K Komeiji Koishi 2021-05-10 12:40:59
显示原始代码 
#include <cstdio>
#include <algorithm>
using namespace std;
int n, dp[2005][2005], a[2005], inv[2005], cnt[2005], sum[2005], suf[2005];
int tr[4][2005][2005], ty;  // hou qian
const int mod = 1e9 + 7;
int lowbit(int p) { return p & -p; }
int mypow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1)
            ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int M(int x) { return x >= mod ? x - mod : x; }
int ask(int pos, int p) {
    int ans = 0;
    while (p) {
        ans = M(ans + tr[ty][pos][p]);
        p -= lowbit(p);
    }
    return ans;
}
void modify(int pos, int p, int v) {
    while (p <= n + 2) {
        tr[ty][pos][p] = M(tr[ty][pos][p] + v);
        p += lowbit(p);
    }
}
int main() {
    scanf("%d", &n);
    inv[1] = 1;
    for (int i = 2; i <= n + 2; i++) inv[i] = mypow(i, mod - 2);
    a[0] = 1;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i]++;
    a[n + 1] = n + 2;
    for (int l = 2; l <= n + 2; l++) {
        for (int i = 0; i <= n + 2 - l; i++) {
            int j = i + l - 1;
            if (a[i] > a[j])
                continue;
            ty = 0;
            int sum = ask(j, n + 2) - ask(j, a[i]);
            if (sum > 0) {
                ty = 1;
                int res1 = M(ask(j, n + 2) - ask(j, a[i]) + mod);
                ty = 3;
                int res2 = ask(i, a[j]);
                dp[i][j] = M(1ll * M(res1 + res2) * inv[sum] % mod + 1);
            }
            ty = 0;
            modify(j, a[i], 1);
            ty = 1;
            modify(j, a[i], dp[i][j]);
            ty = 2;
            modify(i, a[j], 1);
            ty = 3;
            modify(i, a[j], dp[i][j]);
        }
    }
    printf("%d\n", dp[0][n + 1]);
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：448 ms
内存：73116 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
内存：340 KiB

输入文件（sample_01.in） 

3
3 1 2

答案文件（sample_01.out） 

666666673

用户输出 

666666673

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：46 ms
内存：47832 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
内存：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
用时：1 ms
内存：248 KiB

输入文件（random_03.in） 

1
1

答案文件（random_03.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：434 ms
内存：73104 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
用时：385 ms
内存：72960 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
用时：381 ms
内存：73116 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
用时：386 ms
内存：73044 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
用时：399 ms
内存：72952 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
用时：444 ms
内存：72988 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
用时：425 ms
内存：72948 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
用时：304 ms
内存：64372 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
用时：368 ms
内存：71468 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
用时：298 ms
内存：66292 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
用时：53 ms
内存：24052 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
用时：39 ms
内存：19572 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
内存：22172 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
用时：146 ms
内存：46964 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
用时：207 ms
内存：57608 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
用时：63 ms
内存：27124 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
内存：9104 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
用时：1 ms
内存：376 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
内存：472 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
内存：248 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
内存：424 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
内存：248 KiB

输入文件（random_28.in） 

1
1

答案文件（random_28.out） 

1

用户输出 

1

系统信息 

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

输入文件（random_32.in） 

6
1 3 5 4 6 2

答案文件（random_32.out） 

200000005

用户输出 

200000005

系统信息 

Exited with return code 0
测试点 #35
Accepted
得分：100
用时：3 ms
内存：376 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
内存：308 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
内存：476 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
内存：248 KiB

输入文件（random_40.in） 

2
2 1

答案文件（random_40.out） 

1

用户输出 

1

系统信息 

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