QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318236#1302. 表达式求值ushg8877100 ✓294ms6648kbC++141.8kb2024-01-30 19:36:132024-01-30 19:36:14

Judging History

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

  • [2024-01-30 19:36:14]
  • 评测
  • 测评结果:100
  • 用时:294ms
  • 内存:6648kb
  • [2024-01-30 19:36:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=5e4+5;
const int MOD=1e9+7;
int n,m;
int a[10][MAXN];string s;
ll F[1<<10|10];
char suf[MAXN],opt[MAXN];int cnt,top;// 后缀表达式 
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<m;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; 
	cin>>s;
	for(int i=0;i<s.length();i++){
		char c=s[i];
		if(c>='0'&&c<='9') suf[++cnt]=c;
		else if(c=='(') opt[++top]=c;
		else if(c=='<'||c=='>'||c=='?'){
			while(opt[top]=='<'||opt[top]=='>'||opt[top]=='?') suf[++cnt]=opt[top--];
			opt[++top]=c;
		}else if(c==')'){
			while(opt[top]!='(') suf[++cnt]=opt[top--];
			top--;
		}
	}
	while(top) suf[++cnt]=opt[top--];
	for(int S=0;S<(1<<m);S++){
		static ll f[MAXN],g[MAXN],top;
		memset(f,0,sizeof(f));memset(g,0,sizeof(g));top=0;
		for(int i=1;i<=cnt;i++){
			if(suf[i]>='0'&&suf[i]<='9') ++top,f[top]=(S>>(suf[i]-'0')&1),g[top]=1-f[top];
			else if(suf[i]=='<'){
				ll F=f[top]*f[top-1]%MOD,G=(f[top]+g[top])*(f[top-1]+g[top-1])%MOD-F;
				top--;f[top]=(F%MOD+MOD)%MOD;g[top]=(G%MOD+MOD)%MOD;
			}else if(suf[i]=='>'){
				ll G=g[top]*g[top-1]%MOD,F=(f[top]+g[top])*(f[top-1]+g[top-1])%MOD-G;
				top--;f[top]=(F%MOD+MOD)%MOD;g[top]=(G%MOD+MOD)%MOD;
			}else{
				ll F=f[top]*(f[top-1]+g[top-1])+f[top-1]*(f[top]+g[top]);
				ll G=g[top]*(f[top-1]+g[top-1])+g[top-1]*(f[top]+g[top]);
				top--;f[top]=(F%MOD+MOD)%MOD;g[top]=(G%MOD+MOD)%MOD;
			}
		}
		F[S]=f[1];
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		vector<int> val;val.push_back(0);
		for(int j=0;j<m;j++) val.push_back(a[j][i]);
		sort(val.begin(),val.end());
		for(int j=1;j<=m;j++){
			int S=0;
			for(int k=0;k<m;k++) if(a[k][i]>=val[j]) S|=(1<<k);
			ans+=F[S]*(val[j]-val[j-1])%MOD;
		}
	}
	cout<<ans%MOD<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 1ms
memory: 6256kb

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: 1ms
memory: 4396kb

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: 1ms
memory: 5668kb

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: 1ms
memory: 4548kb

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: 4ms
memory: 6244kb

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 644873...

output:

624158291

result:

ok 1 number(s): "624158291"

Test #6:

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

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 3...

output:

774045051

result:

ok 1 number(s): "774045051"

Test #7:

score: 5
Accepted
time: 13ms
memory: 4332kb

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 886534...

output:

578589820

result:

ok 1 number(s): "578589820"

Test #8:

score: 5
Accepted
time: 42ms
memory: 6188kb

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...

output:

206787250

result:

ok 1 number(s): "206787250"

Test #9:

score: 5
Accepted
time: 42ms
memory: 6184kb

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...

output:

809724564

result:

ok 1 number(s): "809724564"

Test #10:

score: 5
Accepted
time: 24ms
memory: 4440kb

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)...

output:

438872671

result:

ok 1 number(s): "438872671"

Test #11:

score: 5
Accepted
time: 29ms
memory: 4468kb

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?...

output:

292181640

result:

ok 1 number(s): "292181640"

Test #12:

score: 5
Accepted
time: 32ms
memory: 4640kb

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 226...

output:

360684575

result:

ok 1 number(s): "360684575"

Test #13:

score: 5
Accepted
time: 36ms
memory: 4536kb

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 4074...

output:

870145312

result:

ok 1 number(s): "870145312"

Test #14:

score: 5
Accepted
time: 37ms
memory: 4648kb

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 319...

output:

801430798

result:

ok 1 number(s): "801430798"

Test #15:

score: 5
Accepted
time: 294ms
memory: 6416kb

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 3567...

output:

179958101

result:

ok 1 number(s): "179958101"

Test #16:

score: 5
Accepted
time: 289ms
memory: 6476kb

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 8951...

output:

563943527

result:

ok 1 number(s): "563943527"

Test #17:

score: 5
Accepted
time: 293ms
memory: 6648kb

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 25707...

output:

430538563

result:

ok 1 number(s): "430538563"

Test #18:

score: 5
Accepted
time: 241ms
memory: 6528kb

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 9980644...

output:

162621711

result:

ok 1 number(s): "162621711"

Test #19:

score: 5
Accepted
time: 263ms
memory: 6428kb

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 4885...

output:

361022397

result:

ok 1 number(s): "361022397"

Test #20:

score: 5
Accepted
time: 256ms
memory: 6432kb

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 4820...

output:

645459025

result:

ok 1 number(s): "645459025"