QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62327 | #1302. 表达式求值 | perspective | 100 ✓ | 242ms | 206376kb | C++14 | 3.4kb | 2022-11-18 00:30:27 | 2022-11-18 00:30:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<const int mod>
struct modint{
int x;
modint<mod>(int o=0){x=o;}
modint<mod> &operator = (int o){return x=o,*this;}
modint<mod> &operator +=(modint<mod> o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint<mod> &operator -=(modint<mod> o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint<mod> &operator *=(modint<mod> o){return x=1ll*x*o.x%mod,*this;}
modint<mod> &operator ^=(int b){
modint<mod> a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint<mod> &operator /=(modint<mod> o){return *this *=o^=mod-2;}
modint<mod> &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
modint<mod> &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
modint<mod> &operator *=(int o){return x=1ll*x*o%mod,*this;}
modint<mod> &operator /=(int o){return *this *= ((modint<mod>(o))^=mod-2);}
template<class I>friend modint<mod> operator +(modint<mod> a,I b){return a+=b;}
template<class I>friend modint<mod> operator -(modint<mod> a,I b){return a-=b;}
template<class I>friend modint<mod> operator *(modint<mod> a,I b){return a*=b;}
template<class I>friend modint<mod> operator /(modint<mod> a,I b){return a/=b;}
friend modint<mod> operator ^(modint<mod> a,int b){return a^=b;}
friend bool operator ==(modint<mod> a,int b){return a.x==b;}
friend bool operator !=(modint<mod> a,int b){return a.x!=b;}
bool operator ! () {return !x;}
modint<mod> operator - () {return x?mod-x:0;}
modint<mod> &operator++(int){return *this+=1;}
};
typedef modint<1000000007> mint;
const int N=5e4+10;
int n,m,a[10][N];
char s[N];
int op[N],lc[N],rc[N];//表达式树 直接存字符即可因为数字<10
mint dp[N][1<<10],sum[N];
int maxst;
void dfs(int x){
if(!x)return;
if(op[x]<10){
sum[x]=1;
for(int S=0;S<maxst;S++)
if((S>>op[x])&1)
dp[x][S]++;
//dp[x][1<<op[x]]=1;
return;
}
dfs(lc[x]);dfs(rc[x]);
sum[x]=sum[lc[x]]*sum[rc[x]];
if(op[x]=='?')sum[x]*=2;
for(int S=0;S<maxst;S++){
if(op[x]=='<'||op[x]=='?'){
dp[x][S]+=dp[lc[x]][S]*dp[rc[x]][S];
}if(op[x]=='>'||op[x]=='?'){
dp[x][S]+=dp[lc[x]][S]*sum[rc[x]]+(sum[lc[x]]-dp[lc[x]][S])*dp[rc[x]][S];
}
}
}
signed main(){
scanf("%d%d",&n,&m);maxst=1ll<<m;
for(int i=0;i<m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
scanf("%s",s+1);
int len=strlen(s+1);
int cnt=0;stack<int>s1;stack<int>s2;
//数字栈与符号栈
s[0]='(';s[len+1]=')';
for(int i=0;i<=len+1;i++){
if(isdigit(s[i])){
s1.push(++cnt);op[cnt]=s[i]-'0';
}
else if(s[i]=='?'||s[i]=='<'||s[i]=='>'){
while(s2.size()&&s2.top()!=-1){
++cnt;
lc[cnt]=s1.top();s1.pop();
rc[cnt]=s1.top();s1.pop();
op[cnt]=s2.top();s2.pop();
s1.push(cnt);
}
s2.push(s[i]);
}
else if(s[i]=='('){
s2.push(-1);
}
else if(s[i]==')'){
while(s2.top()!=-1){
++cnt;
lc[cnt]=s1.top();s1.pop();
rc[cnt]=s1.top();s1.pop();
op[cnt]=s2.top();s2.pop();
s1.push(cnt);
}
s2.pop();
}
}
int rt=s1.top();
dfs(rt);mint ans=0;
for(int i=1;i<=n;i++){
static pair<int,int> num[11];
for(int j=0;j<m;j++)num[j]={a[j][i],j};
sort(num,num+m);reverse(num,num+m);
for(int i=0;i<m;i++){
int st=0;
for(int j=0;j<=i;j++)
st|=1<<num[j].second;
ans+=(dp[rt][st]-dp[rt][st^(1<<num[i].second)])*num[i].first;
}
}
printf("%d",ans.x);
return 0;
}
詳細信息
Test #1:
score: 5
Accepted
time: 35ms
memory: 203816kb
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: 29ms
memory: 203928kb
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: 31ms
memory: 203772kb
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: 28ms
memory: 203792kb
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: 32ms
memory: 203804kb
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: 36ms
memory: 203992kb
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: 32ms
memory: 203828kb
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: 58ms
memory: 204164kb
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: 56ms
memory: 203952kb
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: 32ms
memory: 204020kb
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: 33ms
memory: 203820kb
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: 35ms
memory: 204260kb
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: 56ms
memory: 204136kb
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: 36ms
memory: 204236kb
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: 160ms
memory: 206144kb
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: 171ms
memory: 206280kb
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: 160ms
memory: 206296kb
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: 242ms
memory: 206204kb
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: 215ms
memory: 206216kb
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: 234ms
memory: 206376kb
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"