QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#5917 | #1302. 表达式求值 | Qingyu | 100 ✓ | 73ms | 7992kb | C++17 | 2.8kb | 2021-02-06 20:30:46 | 2021-12-19 07:09:07 |
Judging History
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
*/
详细
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"