QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#5917#1302. 表达式求值Qingyu100 ✓73ms7992kbC++172.8kb2021-02-06 20:30:462021-12-19 07:09:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 07:09:07]
  • 评测
  • 测评结果:100
  • 用时:73ms
  • 内存:7992kb
  • [2021-02-06 20:30:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define ll long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();

    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();

    return x;
}
void wr(int x)
{
    if (x < 0)
        putchar('-'), x = -x;

    if (x >= 10)
        wr(x / 10);

    putchar('0' + x % 10);
}
const int MAXN = 5e4 + 10, mod = 1e9 + 7;
struct node
{
    int a[1024], tot;
} s[MAXN];
int n, m, S, A[12][MAXN], len, id[MAXN];
char ss[MAXN];
stack<char>opt;
stack<node>num;
inline node calc(const node &a, const node &b, char op)
{
    node res;

    if (op == '<')
    {
        fp(i, 0, S)res.a[i] = 1ll * a.a[i] * b.a[i] % mod;
        res.tot = 1ll * a.tot * b.tot % mod;
    }
    else if (op == '>')
    {
        ll t = 1ll * a.tot * b.tot % mod;
        fp(i, 0, S)res.a[i] = (t - 1ll * (a.tot - a.a[i]) * (b.tot - b.a[i])) % mod;
        res.tot = t;
    }
    else
    {
        fp(i, 0, S)res.a[i] = (1ll * a.tot * b.a[i] + 1ll * b.tot * a.a[i]) % mod;
        res.tot = 2ll * a.tot * b.tot % mod;
    }

    return res;
}
int Y;
inline bool cmp(int q1, int q2)
{
    return A[q1][Y] > A[q2][Y];
}
inline void doit()
{
    while (!opt.empty() && opt.top() != '(')
    {
        char ch = opt.top();
        opt.pop();
        node num1 = num.top();
        num.pop();
        node num2 = num.top();
        num.pop();
        num.push(calc(num1, num2, ch));
    }
}
main()
{
    n = read();
    m = read();
    S = (1 << m) - 1;
    fp(i, 0, m - 1)fp(j, 1, n)A[i][j] = read();
    fp(i, 0, m - 1)fp(j, 0, S)s[i].a[j] = j >> i & 1;
    fp(i, 0, m - 1)s[i].tot = 1;
    scanf("%s", ss + 1);
    len = strlen(ss + 1);
    fp(i, 1, len)
    {
        char ch = ss[i];

        if (isdigit(ch))
        {
            num.push(s[ch - '0']);
            doit();
        }
        else if (ch == ')')
            opt.pop(), doit();
        else
            opt.push(ch);
    }
    node p = num.top();
    ll res = 0;
    fp(i, 0, m - 1)id[i] = i;
    fp(kk, 1, n)
    {
        Y = kk;
        sort(id, id + m, cmp);
        int t = 0;
        ll os = 0;

        fp(i, 0, m - 1)if (p.a[t |= 1 << id[i]])
        {
            res = (res + 1ll * (p.a[t] - os) * A[id[i]][Y]) % mod;
            os = p.a[t];
        }
    }
    printf("%lld\n", (res % mod + mod) % mod);
    return 0;
}
/*
3 2
1 3 5
2 2 6
0<1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 2ms
memory: 7660kb

input:

5 1
563449994 574899308 803741703 814662691 753856189
0>0<0>0>0

output:

510609864

result:

ok 1 number(s): "510609864"

Test #2:

score: 5
Accepted
time: 0ms
memory: 5684kb

input:

5 1
970618442 898372082 205838823 914063102 634278096
0<0>0>0

output:

623170524

result:

ok 1 number(s): "623170524"

Test #3:

score: 5
Accepted
time: 2ms
memory: 5676kb

input:

4 2
888391775 820498254 47915768 13936748
159197710 945021228 182725784 170636478
1>0<1<1

output:

457581193

result:

ok 1 number(s): "457581193"

Test #4:

score: 5
Accepted
time: 2ms
memory: 5680kb

input:

5 3
590479238 662611876 741340010 1428176 381033915
240774051 830284209 237962457 820464085 547379208
635393442 695144987 990748426 994330364 567256461
1>2>0<2<0

output:

376893201

result:

ok 1 number(s): "376893201"

Test #5:

score: 5
Accepted
time: 2ms
memory: 5648kb

input:

8 8
388954504 218118857 169035767 937004408 735501805 662964503 225499462 734554299
844358514 561597019 570461365 303411120 230774039 263798588 182870881 461798110
434934512 983750620 420063684 157839072 658979059 887877034 759189259 419778959
741183518 592492603 141499079 910615121 666119898 644873875 45250716 319572774
203011471 736019838 779602143 975478651 979517756 145278787 11658067 516111789
604379087 201656496 511524903 821997377 547605685 567570173 29537637 370342602
940502808 477310313...

output:

624158291

result:

ok 1 number(s): "624158291"

Test #6:

score: 5
Accepted
time: 2ms
memory: 5772kb

input:

9 9
889184406 183612169 35723644 185605372 249481533 74304364 71696614 266665531 49208228
261483901 566762104 406965660 136423522 431332678 577268698 897623560 286552745 359906818
566189947 454399372 638396472 701204492 827384132 888483796 219611554 560740709 137102900
38487069 459590936 919924917 369555039 588833349 917451267 670859009 838217513 429016671
306844695 897638647 540111551 241453385 436682285 293800373 837956155 331331656 266037318
228242169 660332438 11789367 575387242 414505450 15...

output:

774045051

result:

ok 1 number(s): "774045051"

Test #7:

score: 5
Accepted
time: 2ms
memory: 5780kb

input:

8 10
951731312 216216105 401737608 315383085 653860396 757845470 383295530 670765130
334134984 136930780 366883296 782005335 563745705 176213371 238177184 134413480
764129900 779011837 717882120 881661994 455968858 173202087 93384297 773075546
804628869 692867721 297702586 924207216 401452158 886534052 736269078 673619932
868506920 549447378 382391543 509841150 440456520 376600431 889136108 445609507
9756833 774335059 498435793 950407828 520990407 994933227 461320420 996333270
369531408 19165872...

output:

578589820

result:

ok 1 number(s): "578589820"

Test #8:

score: 5
Accepted
time: 7ms
memory: 7724kb

input:

2 10
536918706 266398645
932355940 991853245
235670474 953811450
817357119 941942594
800144791 490904823
5188387 228132606
966390744 710403744
820381508 233249393
376211710 798344799
303201934 415154501
6?4>8>6?7>8>4?2?2>0<6<4>8>1<5>8?8>8>0?5<8?6?6?5?3?0?6>0>9<7<4<0?5?8<5>7?4<9>9<8?6<9>7>0<7>5<4?5<4?3<6<1<4<6<8<9?0<4<0<7?0<4>9<2>9<9?5<2<2<4<4?7>0<2>3<9?7?9<9<5?4>9<6?4?6<0<1?2<5>4?6?6<2?8<2>9?6?1<1?3>4<4<0?0?5?1?2?3?9>2?2>8?4>8?0?5?6>8?9?5?5?4<2?6<8?9>0?6?3>2?6>6<2?4<4?3<8?5>1<2<9>1?5<0<1<5?6?0?1...

output:

206787250

result:

ok 1 number(s): "206787250"

Test #9:

score: 5
Accepted
time: 7ms
memory: 5728kb

input:

2 10
171983718 17359564
778157980 325751227
965047583 684475110
977018615 18147116
55900738 927907589
316603809 769482421
544519110 231111676
569762933 376024555
874056184 400397185
335472017 59874521
1<1<6>0?5?5?8<4>2?2<9<8?0<3<3?5?0<1<3<1<6>6>7>9?6<3>1?3>8?5?4?0?5?5?0<6>3<1<6>3?4?1<9<9?8<3>0>4?0>7<3<7<9<5<5?2<1?1>7<3<5>1<3<5?4>0>5<9?5<8<0>8>5>3?6<0>3<4<7?7>2>0>3<1?5?3<4<0?9<6>2?3?7<0<2?6<3<3?4?6>8?4<5>3?5?3>9?0<5<0<7?2?3?3?8?8?3>1?1>3?2<7?5?4?3>9?1?9?5?8<7?3<4?6<7?6?9>7?7<2>1?0<3?5<5?0<1>8>5<9...

output:

809724564

result:

ok 1 number(s): "809724564"

Test #10:

score: 5
Accepted
time: 5ms
memory: 5724kb

input:

2 10
474648502 589366333
211628540 607952348
127920410 327200223
622269818 243461833
906671293 954195759
833987541 202829215
894060313 528594129
591943765 580863628
114328131 588767072
877275552 821215582
6?(6>(0?6)?(1?(2?(2?0)))?(9>(2?7?7)?5?(0?0<3?9?6)))?(6?1)<(9?4?(6?(9?8))?(8>6?9?6<0?(2?4?4?5?0)?(7<7>1<(9?3>(2?1))?5)?(1?5?(4>(4?(5?9?2))?(2?4?1<(2?(0?2?0))?(9?3?1)?(9?(5?1))))?(8?7?3?(9?4?2?(8<3)?1?7?1?7<(7>(8>0?4?2)))))?(9?9?0<(7?2<0?9?7)?(3?(1?4)>5?2?9))?(0?5<(5?3?2?0)?(3?5?5?2?(1?(5?7?5)))?...

output:

438872671

result:

ok 1 number(s): "438872671"

Test #11:

score: 5
Accepted
time: 5ms
memory: 5732kb

input:

2 10
829278041 507157654
436087432 379126472
394625852 323032183
363240065 753505858
461880644 748333223
498500306 960927592
159263077 969910977
819167886 236990682
593960609 118222384
541226010 718554798
2?(5?6?8?(3?8))?(7?1)?(8?(9<(1?2?7?0?7?4))?(3<(4?(8?8?0?2?0)))>(8?7?(8?8<5)?6))?(1?5?(5?2))?(4?3?(9?(5?4))?(9?(0?9)?2?(3<2?2?(9<(6<6?2)?0?8)))?(2?7?9?(1?4?2?(2?1))?(2<3?3?(0?8?(5?2?2?0)))?2?(0?(4?7?3)?0?7?7?5))?(6<(3?2?(6?6?(8?9)?(2<0?4))?(3?(9<(3?6)?5?0))?3)?(7?2<6?(2<(3?8))?(8?1?3?7))?(1?(2?(...

output:

292181640

result:

ok 1 number(s): "292181640"

Test #12:

score: 5
Accepted
time: 10ms
memory: 6012kb

input:

4935 10
505994009 206058740 411853989 690198842 539018224 119517495 833328520 937831730 681650550 749278929 286845292 981768549 393401319 867552740 618679874 36815141 276776048 325450931 212940005 101157906 427619542 447609305 334373694 927712683 262035734 619363165 783468743 463173617 228599682 226610891 86997083 797343794 659188478 112614873 785077504 658082560 852803870 768783012 600720509 988961813 803817510 580633447 540643358 589599046 901610461 722396392 517353626 1105479 326174554 563711...

output:

360684575

result:

ok 1 number(s): "360684575"

Test #13:

score: 5
Accepted
time: 7ms
memory: 5952kb

input:

4938 10
644408703 817039500 972437582 334145181 308311759 991426722 583299581 253209312 450060254 725275841 593870912 758160148 303387962 915290953 869675207 857494164 141650928 241515793 411840121 457119366 182437220 689442044 704416120 44374526 625824570 932378404 295663869 777627144 46916995 407428113 392678328 527411465 465739263 101891523 946351999 407284 402771247 507892985 983643894 773803449 153592708 157291259 41812153 509694499 123168407 990914161 558621442 837574519 359626345 14724753...

output:

870145312

result:

ok 1 number(s): "870145312"

Test #14:

score: 5
Accepted
time: 4ms
memory: 5992kb

input:

4926 10
279940328 894155539 764548461 297573799 907167754 708281198 580239465 361447228 686065457 862426653 363873141 656195955 283138113 952245263 264247570 212726994 816057727 577897720 732186483 776914068 894158713 34919282 625328540 111794959 963418208 143123476 294576492 997294709 422309328 319422361 896245651 750347896 25661662 725082011 557395572 823710390 347194345 582279113 282064409 86362907 876174401 567781725 363858227 405536357 810189941 742274584 676419462 877204036 692996397 31288...

output:

801430798

result:

ok 1 number(s): "801430798"

Test #15:

score: 5
Accepted
time: 62ms
memory: 7588kb

input:

49154 10
477820661 216751471 809699382 13633832 436797615 84668036 307756511 249316578 523122746 325932801 795536330 345912088 506230587 961008119 438938543 633756353 24127348 707661973 910343125 389658824 244465038 587676955 809290132 651570250 922067294 943005103 657442858 838742188 657286405 356720264 696868044 959146594 290800749 889149695 673957812 306450183 842431772 391098930 826006463 282587610 289867526 236856263 482264123 809831483 86380095 91311293 291835670 29447539 172981379 6789122...

output:

179958101

result:

ok 1 number(s): "179958101"

Test #16:

score: 5
Accepted
time: 73ms
memory: 6876kb

input:

49383 10
585233927 551507829 652661551 697133944 59410373 331978298 396739580 65397125 691594435 372421254 442926797 18606450 259734512 597422253 316014623 530701327 997608495 327393109 642879349 882990586 237036309 287071775 493301036 549892809 352557595 528117092 514052193 348495870 982181721 895132182 289885412 537466265 879288170 287547956 980290742 251961010 944685010 974352396 304160970 500964863 506814378 35356817 462794924 8509831 217058688 604394787 465526396 819203148 829639116 1332942...

output:

563943527

result:

ok 1 number(s): "563943527"

Test #17:

score: 5
Accepted
time: 56ms
memory: 6520kb

input:

49518 10
627986275 756932340 68713552 596208202 312545709 210722198 407439480 583723497 935514583 392074971 50458374 871593077 878880549 952854574 841261136 43572501 31092277 729364915 599460926 220244978 469279642 549241083 136425352 462089488 377373349 994667052 282692893 985617084 651211250 257071815 942630361 801613408 477888802 288247031 918475805 710399999 757447697 140375660 282922987 557848051 912332179 533684470 669427191 395972504 58052675 733732987 999211435 424468505 101488201 610178...

output:

430538563

result:

ok 1 number(s): "430538563"

Test #18:

score: 5
Accepted
time: 67ms
memory: 7992kb

input:

49584 10
835285530 543293868 39564029 306438253 641932665 4458127 839554668 353994059 78772903 12503942 774097612 802622955 265467651 317533715 292276807 327616227 97856281 771782989 555459840 502108968 408425886 354019052 394754547 373424616 126554351 990166727 881400086 349048396 604809792 998064490 475108310 801158221 343745254 595465145 708888592 51283785 785623645 173389532 22555345 56819720 412544545 485213476 987475070 739869071 105463628 853178618 624713304 508941742 356483390 138746370 ...

output:

162621711

result:

ok 1 number(s): "162621711"

Test #19:

score: 5
Accepted
time: 66ms
memory: 7316kb

input:

49529 10
401230402 380706431 105451177 643923064 171097592 156617008 520835654 541491606 887467880 324980518 896651705 58713113 22545991 973348865 617693033 630847630 529343768 729692675 739422532 637224256 327114600 256937477 832295242 751397560 461196333 91395079 626276745 509024178 668251822 48859428 841653242 191255505 721994800 210247823 213322253 83149101 548828134 712175870 539732132 307017596 715274055 96904222 876646325 983215628 18396131 820622077 880534986 841689822 806047162 90779805...

output:

361022397

result:

ok 1 number(s): "361022397"

Test #20:

score: 5
Accepted
time: 54ms
memory: 7056kb

input:

49927 10
740920368 464697847 852423810 823565533 60066393 218544658 883022233 768919034 739358616 917971324 821522420 81204554 79073006 761376173 668020558 377011790 286654057 988907375 116557265 472866791 708920614 589477539 159704326 869790156 641958360 436305589 405113238 141288253 588488009 482031005 113034324 318597697 994753105 655235437 245839440 64922849 236622064 841048824 770220414 63073982 301235680 175367554 354844326 306499363 595266612 593369931 928115473 589276323 846322521 284666...

output:

645459025

result:

ok 1 number(s): "645459025"