解题思路

乍一看，本题题意极其通俗易懂，似乎与往年第三题的风格不太相符，其难点正在于无法将我们脑中简单的偏导数运算过程转化成代码，具体表现为几个关键小问题：我该如何存储最终要求导的多项式？在求偏导数时我该如何忽略其他无关变量？常系数应该如何处理，是否应该和其他乘积项统一成同一种形式？如果这些问题可以解决那么本题就可以解决了。
根据我们的数学直觉，最终要求偏导数的多项式一定是 a x1qx2w. . . xne+ b x1rx2t. . . xny+ . . . + z x1ux2i. . . xno ax_1^qx_2^w…x_n^e+bx_1^rx_2^t…x_n^y+…+zx_1^ux_2^i…x_n^oax1q​x2w​…xne​+bx1r​x2t​…xny​+…+zx1u​x2i​…xno​，通过观察这个多项式，我们首先要思考的是如何存储多项式中的乘积项 a x1qx2w. . . xne ax_1^qx_2^w…x_n^eax1q​x2w​…xne​，若以下面的方式存储，单独的一个常数也可以视为乘积项的特殊形式

struct item{ll coefficient;//系数或常数 map<int,int>mp;//一个下标对应一个指数 例如x2的5次方 那么key值为2，value值为5item(ll coe,map<int,int>mp):coefficient(coe),mp(mp) {}//结构体构造函数};//乘积项

有了上面的基础，多项式可以以下面的方式进行存储，vector中每一项都是一个乘积项，且默认这些乘积项都由加号连接，那么遇到减号该如何处理呢？答案是可以将减号看成一个负号乘到每一个乘积项的系数coefficient中。

struct formula{vector<item>vec;//规定所有乘积项均用+连接formula(vector<item>vec):vec(vec) {}};//多项式

到此为止，最关键的数据结构模型已经建立好了，随后的多项式加法，减法，乘法，乃至求偏导，都是非常基础的模拟过程，具体请详见下方完整代码。

题目链接

ccf-csp认证-梯度求解

AC代码

#include#include#include#include#includeusing namespace std;typedef long long ll;ll mod=1e9+7;stack<formula>st;//栈Svector<ll>val;//存储求导时的变量值struct item{ll coefficient;//系数或常数 map<int,int>mp;//一个下标对应一个指数 例如x2的5次方 那么key值为2，value值为5item(ll coe,map<int,int>mp):coefficient(coe),mp(mp) {}//结构体构造函数};//乘积项 struct formula{vector<item>vec;//规定所有乘积项均用+连接formula(vector<item>vec):vec(vec) {}};//多项式 ll convert(string str)//字符串转换成数字 {ll num=0;for(int i=(str[0]=='-')?1:0;i<str.length();i++){num*=10;num+=str[i]-'0';}return (str[0]=='-')?-1*num:num; }item item_mul(item A,item B)//乘积项乘法函数 {ll coefficient_c=A.coefficient*B.coefficient;map<int,int>mp_c;map<int,int>::iterator it;for(it=A.mp.begin();it!=A.mp.end();it++){mp_c[it->first]=A.mp[it->first]+B.mp[it->first];B.mp.erase(it->first);}for(it=B.mp.begin();it!=B.mp.end();it++){mp_c[it->first]=B.mp[it->first];}return item(coefficient_c,mp_c);}formula formula_mul(formula A,formula B)//多项式乘法 {vector<item>vec;for(int i=0;i<A.vec.size();i++){for(int j=0;j<B.vec.size();j++){vec.push_back(item_mul(A.vec[i],B.vec[j]));}}return formula(vec);}formula formula_add(formula A,formula B)//多项式加法 {for(int i=0;i<B.vec.size();i++){A.vec.push_back(B.vec[i]);}return A;}formula formula_sub(formula A,formula B)//多项式减法 {for(int i=0;i<A.vec.size();i++){A.vec[i].coefficient*=-1;}return formula_add(B,A);}ll function(formula A,int goal)//求导函数 对最终的formula求导 {ll sum=0,mul;for(int i=0;i<A.vec.size();i++){item now=A.vec[i];mul=1;if(now.mp.find(goal)!=now.mp.end()){//此乘积项含有要求导的变量才拥有计算价值mul=(now.coefficient*now.mp[goal])%mod;now.mp[goal]--;for(map<int,int>::iterator it=now.mp.begin();it!=now.mp.end();it++){for(int k=0;k<it->second;k++){mul=(mul*val[it->first])%mod;}}sum=(sum+mul)%mod;}}return sum;}int main(){int n,m;cin>>n>>m;//求解函数中所含自变量的个数和要求解的偏导数的个数getchar();//很重要，如果缺少这行代码会导致str为空string str,temp;getline(cin,str);stringstream sin(str);while(sin>>temp){if(temp=="+" || temp=="-" || temp=="*"){//运算符formula A=st.top(); st.pop();//从栈中依次弹出两个formulaformula 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));//A B的顺序很重要 }}else{map<int,int>mp;//下标 指数 vector<item>vec;if(temp[0]=='x'){//自变量 mp[convert(temp.substr(1,temp.length()-1))]=1;vec.push_back(item(1,mp));//把乘积项包装成多项式 }else{//常数vec.push_back(item(convert(temp),mp));//把乘积项包装成多项式 }st.push(formula(vec));}}for(int i=0;i<m;i++){ll value;for(int j=0;j<n+1;j++){cin>>value;val.push_back(value);}ll ans=function(st.top(),val[0]);cout<<((ans<0)?ans+mod:ans)<<endl;//当计算整数n对M的模时，若n为负数,需要注意将结果调整至区间[0,M)内val.clear();}return 0;}

测试结果

心得

选择合适的数据结构是解决大模拟问题的关键，一旦选定了合适的数据结构，题目也就迎刃而解了，通常使用的数据结构有栈（STL模板库），map,vector,结构体及其复杂嵌套结构，具体应该如何嵌套，具体情况具体分析。