XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#49175 #1258. 地底蔷薇 Wrong Answer 60 5505 ms 102372 K C++ 11 / 2.2 K Rhodoks 2021-05-22 22:37:57
显示原始代码 
#include <bits/stdc++.h>
#define DB double
#define LL long long

#define MST(a, b) memset((a), (b), sizeof(a))

#ifdef _DEBUG_
#define MRK() cout << "Mark" << endl;
#define WRT(x) cout << #x << " = " << (x) << endl;
#else
#define MRK() ;
#define WRT(x) ;
#endif

#define MAXN 2010
#define MAXM 2010000
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-5

#define _ 0
using namespace std;

template <class DataType>
class BinaryIndexTree {
public:
    vector<DataType> bit;

    BinaryIndexTree(int _size = MAXN) { bit.resize(_size + 2); }

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

    void add(int x, int a) {
        for (; x < bit.size(); x += lowbit(x)) bit[x] += a;
    }

    DataType query(int x) {
        DataType ans = 0;
        for (; x; x -= lowbit(x)) ans += bit[x];
        return ans;
    }

    DataType query(int x, int y) {
        if (x > y)
            return 0;
        return query(y) - query(x - 1);
    }
};
#define BIT BinaryIndexTree

LL mpow(LL x, LL n) {
    LL ans = 1;
    while (n) {
        if (n & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return ans;
}

LL dp[MAXN][MAXN];
BIT<LL> bitdp1[MAXN];
BIT<LL> bitdp2[MAXN];
BIT<int> bitcnt[MAXN];
int n;
int a[MAXN];
LL inv[MAXN];
void init() {
    for (int i = 0; i < MAXN; i++) inv[i] = mpow(i, MOD - 2);
}

void work() {
    cin >> n;
    for (int i = 2; i <= n + 1; i++) {
        cin >> a[i];
        a[i]++;
    }
    n += 2;
    a[1] = 1;
    a[n] = n;

    for (int j = 1; j <= n; j++) {
        for (int i = j - 1; i; i--) {
            if (a[i] < a[j]) {
                int cnt = bitcnt[j].query(a[i] + 1, a[j] - 1);
                LL dp1 = bitdp1[j].query(a[i] + 1, a[j] - 1);
                LL dp2 = bitdp2[i].query(a[i] + 1, a[j] - 1);
                if (cnt)
                    dp[i][j] = (dp1 + dp2) * inv[cnt] % MOD + 1;
                // cout<<i<<' '<<j<<' '<<dp1<<' '<<dp2<<' '<<dp[i][j]<<endl;
            }
            bitcnt[j].add(a[i], 1);
            bitdp1[j].add(a[i], dp[i][j]);
            bitdp2[i].add(a[j], dp[i][j]);
        }
    }
    cout << dp[1][n] << endl;
}

int main() {
#ifdef _DEBUG_
    freopen("C:/Users/DELL/Documents/Dev-C++/sample.in", "r", stdin);
#endif
    init();
    int casenum = 1;
    // scanf("%d",&casenum);
    for (int testcase = 1; testcase <= casenum; testcase++) {
#ifdef _DEBUG_
        printf("Case #%d:\n", testcase);
#endif
        work();
    }
    return ~~(0 ^ _ ^ 0);
}
子任务 #1
Wrong Answer
得分：59
测试点 #1
Accepted
得分：100
用时：262 ms
内存：102372 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
用时：57 ms
内存：79604 KiB

输入文件（sample_01.in） 

3
3 1 2

答案文件（sample_01.out） 

666666673

用户输出 

666666673

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：187 ms
内存：79736 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
用时：57 ms
内存：79720 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
用时：56 ms
内存：79688 KiB

输入文件（random_03.in） 

1
1

答案文件（random_03.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #6
Wrong Answer
得分：0
用时：268 ms
内存：102180 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

用户输出 

-152726755

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #7
Wrong Answer
得分：0
用时：314 ms
内存：102156 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

用户输出 

358042037

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #8
Wrong Answer
得分：0
用时：319 ms
内存：102132 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

用户输出 

629080124

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #9
Wrong Answer
得分：0
用时：327 ms
内存：102128 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

用户输出 

118633604

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #10
Wrong Answer
得分：0
用时：329 ms
内存：102132 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

用户输出 

526476270

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #11
Wrong Answer
得分：0
用时：325 ms
内存：102116 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

用户输出 

-771536925

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #12
Wrong Answer
得分：0
用时：330 ms
内存：102032 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

用户输出 

-232771247

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #13
Wrong Answer
得分：0
用时：271 ms
内存：98676 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

用户输出 

720020429

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #14
Wrong Answer
得分：0
用时：289 ms
内存：101380 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

用户输出 

108494162

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #15
Wrong Answer
得分：0
用时：252 ms
内存：99444 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

用户输出 

964389076

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #16
Wrong Answer
得分：0
用时：87 ms
内存：85364 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

用户输出 

-263792378

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #17
Wrong Answer
得分：0
用时：78 ms
内存：84152 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

用户输出 

967714426

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #18
Wrong Answer
得分：0
用时：84 ms
内存：84852 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

用户输出 

-7241015

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #19
Wrong Answer
得分：0
用时：150 ms
内存：91892 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

用户输出 

-235921937

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #20
Wrong Answer
得分：0
用时：205 ms
内存：95968 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

用户输出 

-855192194

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #21
Wrong Answer
得分：0
用时：96 ms
内存：86132 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

用户输出 

991232372

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #22
Wrong Answer
得分：0
用时：61 ms
内存：81480 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

用户输出 

-545504982

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：55 ms
内存：79596 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
用时：56 ms
内存：79604 KiB

输入文件（random_22.in） 

4
1 2 4 3

答案文件（random_22.out） 

3

用户输出 

3

系统信息 

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

输入文件（random_24.in） 

1
1

答案文件（random_24.out） 

1

用户输出 

1

系统信息 

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

输入文件（random_25.in） 

3
3 1 2

答案文件（random_25.out） 

666666673

用户输出 

666666673

系统信息 

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

输入文件（random_26.in） 

4
1 2 3 4

答案文件（random_26.out） 

4

用户输出 

4

系统信息 

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

输入文件（random_27.in） 

6
6 5 4 3 2 1

答案文件（random_27.out） 

1

用户输出 

1

系统信息 

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

输入文件（random_28.in） 

1
1

答案文件（random_28.out） 

1

用户输出 

1

系统信息 

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

输入文件（random_30.in） 

3
2 3 1

答案文件（random_30.out） 

666666673

用户输出 

666666673

系统信息 

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

输入文件（random_31.in） 

5
2 1 3 4 5

答案文件（random_31.out） 

4

用户输出 

4

系统信息 

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

输入文件（random_32.in） 

6
1 3 5 4 6 2

答案文件（random_32.out） 

200000005

用户输出 

200000005

系统信息 

Exited with return code 0
测试点 #35
Accepted
得分：100
用时：55 ms
内存：79708 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
用时：54 ms
内存：79588 KiB

输入文件（random_34.in） 

4
2 1 4 3

答案文件（random_34.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #37
Accepted
得分：100
用时：56 ms
内存：79604 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
用时：57 ms
内存：79640 KiB

输入文件（random_36.in） 

6
5 1 2 3 4 6

答案文件（random_36.out） 

800000010

用户输出 

800000010

系统信息 

Exited with return code 0
测试点 #39
Accepted
得分：100
用时：54 ms
内存：79604 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
用时：54 ms
内存：79692 KiB

输入文件（random_38.in） 

4
4 3 1 2

答案文件（random_38.out） 

500000005

用户输出 

500000005

系统信息 

Exited with return code 0
测试点 #41
Accepted
得分：100
用时：56 ms
内存：79604 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
用时：56 ms
内存：79620 KiB

输入文件（random_40.in） 

2
2 1

答案文件（random_40.out） 

1

用户输出 

1

系统信息 

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