题目链接：http://118.190.20.162/view.page?gpid=T173

大意是给出逆波兰表达式，给出每个x的值求对某x的偏导。

整理了一些模板，参考 https://blog.csdn.net/qq_62571980/article/details/133958027  码风真好orz

显是多项式的模板，重点是item和formula的表示

struct item{
	ll changshu;
	map<int,int> mp;// x2^5 , mp[2]=5
	// item(ll coe,map<int,int>mp):coefficient(coe),mp(mp) {}//结构体构造函数
};
struct formula{
	vector<item> ve;//多个乘项的链接
};
item item_mul(item a,item b){
	//对常数计算，将b中有a的部分合并到a，剩余添加到a
	ll csc = a.changshu*b.changshu;
	map<int,int> mpc;
	for(auto it=a.mp.begin();it!=a.mp.end();it++){
		mpc[it->first] = a.mp[it->first]+b.mp[it->first];
		b.mp.erase(it->first);
	}
	for(auto it=b.mp.begin();it!=b.mp.end();it++){
		mpc[it->first] = b.mp[it->first];
	}
	item titem;titem.mp = mpc,titem.changshu = csc;
	return titem;
}
formula formula_mul(formula a,formula b){
	//形如f(x)+f(x)+f(x) *  f(x)+f(x)+f(x)
	vector<item>ve;
	for(int i=0;i<a.ve.size();i++){
		for(int j=0;j<b.ve.size();j++){
			ve.push_back(item_mul(a.ve[i],b.ve[j]));
		}
	}
	formula kk; kk.ve = ve;
	return kk;
}
formula formula_add(formula a,formula b){
	//相加用链接的方式
	for(int i=0;i<b.ve.size();i++){
		a.ve.push_back(b.ve[i]);
	}
	return a;
}
formula formula_sub(formula a,formula b){
	for(int i=0;i<a.ve.size();i++){
		a.ve[i].changshu*=-1;
	}
	return formula_add(b,a);
}

然后是求导函数，求导部分。编写代码注意求导直接为0的部分。另一个点就是其余项直接代数计算更加方便。

ll run(formula a,int aim){ //求导函数
	//找到每一项，存在目标进行求导并添加，否则就不用操作0。
	ll sum = 0,mul;
	for(int i=0;i<a.ve.size();i++){
		item cur = a.ve[i];
		mul  = 1;
		if(cur.mp.find(aim)!=cur.mp.end()){
			mul = (cur.changshu*cur.mp[aim])%mod;
			cur.mp[aim]--;
			for(auto it = cur.mp.begin();it!=cur.mp.end();it++){//其余项直接代数
				for(int k=0;k<it->second;k++){
					mul = (mul*val[it->first])%mod;
				}
			}
			sum = (sum+mul)%mod;
		}
	}
	return sum;
}

逆波兰式部分，顺清思路，有了多项式操作的函数比较容易处理。

for(int i=0;i<=s.size();i++){
		if(i==s.size()||s[i]==' '){
			if(temp=="+" || temp=="-" || temp=="*"){
				formula a = st.top(); st.pop();
				formula b = st.top(); st.pop();
				if(temp=="*"){
					st.push(formula_mul(b,a));
				}else if(temp=="+"){
					st.push(formula_add(b,a));
				}else{
					st.push(formula_sub(a,b));
				}
			}else{
				map<int,int> mp;
				vector<item> ve;
				if(temp[0]=='x'){
					int num = to_number(temp.substr(1,temp.size()-1));
					mp[num] = 1;
					item titem;titem.changshu = 1,titem.mp = mp;
					ve.push_back(titem);
				}else{
					int num = to_number(temp);
					item titem;titem.mp = mp,titem.changshu = num;
					ve.push_back(titem);
				}
				formula kk;kk.ve = ve;
				st.push(kk);
			}
			temp = "";
		}else{
			temp+=s[i];
		}
	}