iwtgm-12

补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;
    }
}