补G题
一个大模拟
首先p不一定是质数，不能用逆元，用到了杨辉三角处理二次项系数
首先输入就很唬人，看题解学到用标记的方式分隔
系数默认为1，幂默认为1
有两个字符变量相同的情况，把系数合并
系数不为0才输出，系数为1不输出1，非1才有乘号，幂为1不输出
t次方就是杨辉三角的第t行，0-t就是从左到右的二次项系数，第一个变量和系数的幂次是t-i，第二个是i
ll p,t;//模数、幂
string vv[2];//两个字母变量
ll x[2];//两个系数
string s;//输入字符串
ll C[N][N];//杨辉三角得到二次项系数，因为p不一定为质数，所以不能用逆元，用杨辉三角
void init(){
C[0][0]=1;
for(int i=1;i<N;i++){
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}
}
}
ll ksm(ll a,ll b){
a%=p;
ll res=1;
while(b){
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
void solve(){
cin>>s;
int zt=0;//标记，用来处理字符串
x[0]=x[1]=1;//系数默认为1
t=1;//幂默认为1
string tmp="";//字母变量
ll a=0;//字符串->数字用
for(int i=0;i<s.size();i++){
if(s[i]=='('){
zt=1;//此时处理第一个系数
}else if(s[i]=='+'){
zt=2;//此时处理第二个系数
}else if(s[i]==')'){
zt=3;
}else if(s[i]=='^'){
zt=4;//此时处理幂
}else if(s[i]=='%'){//%一定出现
if(a){//有幂则更新幂
t=a;
a=0;
}
zt=5;//处理模数
}else{
if(zt==1){
if(s[i]>='0'&&s[i]<='9'){
a=a*10+(s[i]-'0');
}else{
if(a){//a为系数
x[0]=a;
}
a=0;
tmp+=s[i];
vv[0]=tmp;//第一个字符变量
tmp="";
}
}else if(zt==2){
if(s[i]>='0'&&s[i]<='9'){
a=a*10+(s[i]-'0');
}else{
if(a){//第二个系数
x[1]=a;
}
a=0;
tmp+=s[i];
vv[1]=tmp;//第二个字符变量
tmp="";
}
}else if(zt==4){
if(s[i]>='0'&&s[i]<='9'){
a=a*10+(s[i]-'0');
}
}else if(zt==5){
if(s[i]>='0'&&s[i]<='9'){
a=a*10+(s[i]-'0');
}
}
}
}
p=a;//得到模数
init();//杨辉三角
if(vv[0]==vv[1]){//两个字符变量相同，则把系数合并
ll xx=(x[0]+x[1])%p;
vector<ll>v;
ll now=ksm(xx,t)%p;
if(now){//系数不为0
v.push_back(now);
}
if(v.size()==0){//系数为0，不输出
cout<<s<<" = "<<"0";
}else{
cout<<s<<" = ";
if(now!=1)//系数为1，1不输出
cout<<now<<"*";
cout<<vv[0];
if(t!=1){//幂为1，1不输出
cout<<"^"<<t;
}
cout<<"%"<<p;
}
return ;
}
vector<pair<ll,pair<int,int>>>v;
for(ll i=0;i<=t;i++){//t次方就是杨辉三角的第t行，0-t就是从左到右的二次项系数，第一个变量和系数的幂次是t-i，第二个是i
ll now=C[t][i]*ksm(x[0],t-i)%p*ksm(x[1],i)%p;//二次项系数*变量系数
if(now!=0){//系数不为0才要输出
v.push_back({now,{t-i,i}});//存下要输出的系数、幂次
}
}
if(v.size()==0){//系数全为0，不输出
cout<<s;
cout<<" = ";
cout<<"0";
}else if(v.size()==1){//只有一项，没有括号
cout<<s;
cout<<" = ";
int fg=0;
if(v[0].first!=1){
cout<<v[0].first;
fg=1;//系数不为0
}
if(v[0].second.first){
if(fg==1){//系数不为0，才有乘号
cout<<"*"<<vv[0];
}else{
cout<<vv[0];
}
fg=1;
if(v[0].second.first!=1){//幂次不为1才有"^"
cout<<"^"<<v[0].second.first;
}
}
if(v[0].second.second){//同理
if(fg==1){
cout<<"*"<<vv[1];
}else{
cout<<vv[1];
}
fg=0;
if(v[0].second.second!=1){
cout<<"^"<<v[0].second.second;
}
}
cout<<"%"<<p;
}else{//多项，有括号
cout<<s;
cout<<" = ";
cout<<"(";
int tot=0;
for(auto i:v){
int fg=0;
if(i.first!=1) {
cout << i.first;
fg=1;
}
if(i.second.first){
if(fg==1){
cout<<"*"<<vv[0];
}
else{
cout<<vv[0];
}
fg=1;
if(i.second.first!=1){
cout<<"^"<<i.second.first;
}
}
if(i.second.second){
if(fg==1){
cout<<"*"<<vv[1];
}
else{
cout<<vv[1];
}
fg=0;
if(i.second.second!=1){
cout<<"^"<<i.second.second;
}
}
if(tot!=v.size()-1){
cout<<"+";
}
tot++;
}
cout<<")";
cout<<"%"<<p;
}
}