【CCF-CSP】 202309-3 梯度求解

思路：

将表达式整理成只有目标求导变量的无括号加法表达式，其他变量均代入其值，然后利用最简单的求导公式，求出最终值。

样例1
x1 x1 x1 * x2 + *转换成 x1*x1*x1+x1*x2
若求导x1，则只留下x1，变为 x1*x1*x1+x1*3
求导完就是 3*x1*x1+3

更一般的，我们可以只记录表达式的系数和指数，那么我们要将每个运算数转换为一元表达式

x1*x1*x1+x1*3转换为
指数1 系数3
指数3 系数1求导之后为
指数0 系数3*1
指数2 系数1*3

对于+运算和-运算，对最终表达式就是直接相加和相减就好了，对*运算，我们要将两个表达式进行乘法运算，指数相加，系数相乘

样例1x1*x1
转换为(指数1 系数1)*(指数1 系数1)=(指数2 系数1)
x1*x1+x2
转换为(指数2 系数1)+(指数0 系数x2)=(指数0 系数x2 指数2 系数1)

代码：

#include <bits/stdc++.h>
#define N 105
using namespace std;
typedef long long ll;
const int mod=1e9+7;int n,m;
ll a[N],k;
string str,s;
vector<string> ve;
stack<map<ll,ll> > st;//记录运算数的一元表达式的系数和指数int main(){cin>>n>>m;getchar();getline(cin,str);stringstream ss(str);while(ss>>s){//所有的运算符和运算数ve.push_back(s);}for(int t=0;t<m;t++){cin>>k;str="x"+to_string(k);//求导变量for(int i=1;i<=n;i++) cin>>a[i];for(int i=0;i<ve.size();i++){s=ve[i];if(s=="+"||s=="-"||s=="*"){//运算符map<ll,ll> mp2=st.top(); st.pop();map<ll,ll> mp1=st.top(); st.pop();map<ll,ll> mp;if(s=="+"){//加法mp=mp1;for(map<ll,ll>::iterator it=mp2.begin();it!=mp2.end();it++){mp[it->first]+=it->second;mp[it->first]%=mod;}}else if(s=="-"){//减法mp=mp1;for(map<ll,ll>::iterator it=mp2.begin();it!=mp2.end();it++){mp[it->first]-=it->second;mp[it->first]%=mod;}}else{//乘法for(map<ll,ll>::iterator it1=mp1.begin();it1!=mp1.end();it1++){for(map<ll,ll>::iterator it2=mp2.begin();it2!=mp2.end();it2++){mp[it1->first+it2->first]+=it1->second*it2->second;mp[it1->first+it2->first]%=mod;}}}mp1.clear(); mp2.clear();st.push(mp);}else if(s==str){//是求导变量，保留map<ll,ll> mp;mp[1]=1;st.push(mp);}else if(s[0]=='x'){//是其他变量，则代入其值int d=stod(s.substr(1));map<ll,ll> mp;mp[0]=a[d]%mod;st.push(mp);}else{//是数字ll d=stol(s);map<ll,ll> mp;mp[0]=d%mod;st.push(mp);}}map<ll,ll> mp=st.top(); st.pop();//获得结果的一元表达式ll ans=0,fac=1,pree=0;for(map<ll,ll>::iterator it=mp.begin();it!=mp.end();it++){ll e=it->first,c=it->second;for(int i=pree+1;i<e;i++) fac=fac*a[k]%mod; pree=e==0?0:e-1;ans=(ans+c*e*fac)%mod;//简单求导公式}cout<<(ans+mod)%mod<<endl;mp.clear();}return 0;
}