题目描述
利用栈将逆波兰表达式建成树,按求偏导法则递归计算即可,计算过程中能取模则取模防止爆long long
C++ 代码
#include<iostream>
#include<cstring>
#include<cmath>
#include<sstream>
using namespace std;
const int N = 105,mod=1e9+7;
typedef long long LL;
struct node {
int type;
int l,r;
LL val;
//若type=2,val存储变量在a[N]中的索引
}tr[N*N];
int n, m,a[N],stk[N],top,idx;
int root;
LL get_val(int u){
if(tr[u].type==1){
LL x=get_val(tr[u].l),y=get_val(tr[u].r);
if(tr[u].val==1)return (x+y)%mod;
else if(tr[u].val==2)return (x-y)%mod;
else return x%mod*y%mod;
}
else if(tr[u].type==2){
return a[tr[u].val]%mod;
}
else {
return tr[u].val%mod;
}
}//求函数值
LL get_p(int u,int k){
if(tr[u].type==1){
LL pl=get_p(tr[u].l,k),pr=get_p(tr[u].r,k);
if(tr[u].val==1)return (pl+pr)%mod;
else if(tr[u].val==2)return (pl-pr)%mod;
else {
LL fl=get_val(tr[u].l),fr=get_val(tr[u].r);
return (pl%mod*fr+pr%mod*fl)%mod;
}
}
else if(tr[u].type==2){
if(tr[u].val==k)return 1;
else return 0;
}
else {
return 0;
}
}//对第k个变量求导
int main() {
cin >> n >> m;
string cmd;
getchar();//吸收换行符
getline(cin,cmd);
stringstream ssin(cmd);
while(ssin>>cmd){
idx++;
if(cmd=="+"||cmd=="-"||cmd=="*"){
tr[idx].type=1;
tr[idx].l=stk[top-2],tr[idx].r=stk[top-1];
top-=2;
int k;
if(cmd=="+")k=1;
else if(cmd=="-")k=2;
else if(cmd=="*")k=3;
tr[idx].val=k;
stk[top++]=idx;
}
else if(cmd[0]=='x'){
tr[idx].type=2;
string k=cmd.substr(1,cmd.size()-1);
tr[idx].val=atoll(k.c_str());
stk[top++]=idx;
}
else {
tr[idx].type=3;
tr[idx].val=atoll(cmd.c_str());
stk[top++]=idx;
}
}//建树
root=stk[top-1];
for(int i=0;i<m;i++){
int k;
cin>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
cout<<(get_p(root,k)%mod+mod)%mod<<endl;
}
}
太妙了
真nb
过奖