fork download
copy 
  1. #include<iostream>
  2. #include<sstream>
  3. #include<vector>
  4. #include<stack>
  5. #include<map>
  6. using namespace std;
  7. typedef long long ll;
  8. ll mod=1e9+7;
  9. vector<ll>val;//存储求导时的变量值
  10. struct item
  11. {
  12. 	ll coefficient;//系数或常数 
  13. 	map<int,int>mp;//一个下标对应一个指数 例如x2的5次方 那么key值为2，value值为5
  14. 	item(ll coe,map<int,int>mp):coefficient(coe),mp(mp) {}//结构体构造函数
  15. };//乘积项 
  16. struct formula
  17. {
  18. 	vector<item>vec;//规定所有乘积项均用+连接
  19. 	formula(vector<item>vec):vec(vec) {}
  20. };//多项式 
  21. stack<formula>st;//栈S
  22. ll convert(string str)//字符串转换成数字 
  23. {
  24. 	ll num=0;
  25. 	for(int i=(str[0]=='-')?1:0;i<str.length();i++){
  26. 		num*=10;
  27. 		num+=str[i]-'0';
  28. 	}
  29. 	return (str[0]=='-')?-1*num:num; 
  30. }
  31. item item_mul(item A,item B)//乘积项乘法函数 
  32. {
  33. 	ll coefficient_c=A.coefficient*B.coefficient;
  34. 	map<int,int>mp_c;
  35. 	map<int,int>::iterator it;
  36. 	for(it=A.mp.begin();it!=A.mp.end();it++){
  37. 		mp_c[it->first]=A.mp[it->first]+B.mp[it->first];
  38. 		B.mp.erase(it->first);
  39. 	}
  40. 	for(it=B.mp.begin();it!=B.mp.end();it++){
  41. 		mp_c[it->first]=B.mp[it->first];
  42. 	}
  43. 	return item(coefficient_c,mp_c);
  44. }
  45. formula formula_mul(formula A,formula B)//多项式乘法 
  46. {
  47. 	vector<item>vec;
  48. 	for(int i=0;i<A.vec.size();i++){
  49. 		for(int j=0;j<B.vec.size();j++){
  50. 			vec.push_back(item_mul(A.vec[i],B.vec[j]));
  51. 		}
  52. 	}
  53. 	return formula(vec);
  54. }
  55. formula formula_add(formula A,formula B)//多项式加法 
  56. {
  57. 	for(int i=0;i<B.vec.size();i++){
  58. 		A.vec.push_back(B.vec[i]);
  59. 	}
  60. 	return A;
  61. }
  62. formula formula_sub(formula A,formula B)//多项式减法 
  63. {
  64. 	for(int i=0;i<A.vec.size();i++){
  65. 		A.vec[i].coefficient*=-1;
  66. 	}
  67. 	return formula_add(B,A);
  68. }
  69. ll function(formula A,int goal)//求导函数 对最终的formula求导 
  70. {
  71. 	ll sum=0,mul;
  72. 	for(int i=0;i<A.vec.size();i++){
  73. 		item now=A.vec[i];
  74. 		mul=1;
  75. 		if(now.mp.find(goal)!=now.mp.end()){//此乘积项含有要求导的变量才拥有计算价值
  76. 			mul=(now.coefficient*now.mp[goal])%mod;
  77. 			now.mp[goal]--;
  78. 			for(map<int,int>::iterator it=now.mp.begin();it!=now.mp.end();it++){
  79. 				for(int k=0;k<it->second;k++){
  80. 					mul=(mul*val[it->first])%mod;
  81. 				}
  82. 			}
  83. 			sum=(sum+mul)%mod;
  84. 		}
  85. 	}
  86. 	return sum;
  87. }
  88. int main()
  89. {
  90. 	int n,m;
  91. 	cin>>n>>m;//求解函数中所含自变量的个数和要求解的偏导数的个数
  92.     getchar();//很重要，如果缺少这行代码会导致str为空
  93. 	string str,temp;
  94. 	getline(cin,str);
  95. 	stringstream sin(str);
  96. 	while(sin>>temp){
  97. 		if(temp=="+" || temp=="-" || temp=="*"){//运算符
  98. 			formula A=st.top(); st.pop();//从栈中依次弹出两个formula
  99. 			formula B=st.top(); st.pop(); 
  100. 			if(temp=="*"){
  101. 				st.push(formula_mul(B,A));
  102. 			}else if(temp=="+"){
  103. 				st.push(formula_add(B,A));
  104. 			}else{
  105. 				st.push(formula_sub(A,B));//A B的顺序很重要 
  106. 			}
  107. 		}else{
  108. 			map<int,int>mp;//下标 指数 
  109. 			vector<item>vec;
  110. 			if(temp[0]=='x'){//自变量 
  111. 				mp[convert(temp.substr(1,temp.length()-1))]=1;
  112. 				vec.push_back(item(1,mp));//把乘积项包装成多项式 
  113. 			}else{//常数
  114. 				vec.push_back(item(convert(temp),mp));//把乘积项包装成多项式 
  115. 			}
  116. 			st.push(formula(vec));
  117. 		}
  118. 	}
  119. 	for(int i=0;i<m;i++){
  120. 		ll value;
  121. 		for(int j=0;j<n+1;j++){
  122. 			cin>>value;
  123. 			val.push_back(value);
  124. 		}
  125. 		ll ans=function(st.top(),val[0]);
  126. 		cout<<((ans<0)?ans+mod:ans)<<endl;//当计算整数n对M的模时，若n为负数,需要注意将结果调整至区间[0,M)内
  127. 		val.clear();
  128. 	}
  129.  
  130. 	return 0;
  131. }
  132.  
Success #stdin #stdout 0.51s 161896KB
comments (?)
stdin
copy 
32 1
x1 x2 + x3 x4 + * x5 x6 + x7 x8 + * * x9 x10 + x11 x12 + * x13 x14 + x15 x16 + * * * x17 x18 + x19 x20 + * x21 x22 + x23 x24 + * * x25 x26 + x27 x28 + * x29 x30 + x31 x32 + * * * * 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
stdout
copy 
0
https://ideone.com/sdeyOK
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!