带参数的矩阵乘法

#include<bits/stdc++.h>
using namespace std;

const int N=3;  //矩阵维数
typedef vector<pair<string,int> > VSI;
typedef pair<string,int> SI;

//带参数的矩阵乘法
void mul(VSI ans[N][N],SI a[N][N])
{
    VSI res[N][N];  //临时矩阵

    //模拟
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
            {
                string s2=a[k][j].first;    //参数
                int i2=a[k][j].second;  //系数
                if(i2==0) continue;   //优化，f(x)*0=0，不必继续往下计算
                for(int l=0;l<ans[i][k].size();l++)
                {
                    string s1=ans[i][k][l].first;
                    int i1=ans[i][k][l].second;
                    if(s2!="1"/*省略1*/) s1+=s2;
                    res[i][j].push_back({s1,i1*i2});    //参数：字符串直接加在后面；系数：直接相乘
                }
            }

    //将临时矩阵复制到答案矩阵        
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            ans[i][j].clear();
            for(int k=0;k<res[i][j].size();k++) ans[i][j].push_back(res[i][j][k]);
        }

    return ;
}

//计数排序
unordered_map<char,int> h;
void Hash(char a)
{
    if(!h.count(a)) h[a]=1;
    else h[a]++;
    return ;
}

//计数排序求最简单项式
string get_min(string a)
{
    string res;
    h.clear();
    for(int i=0;i<a.length();i++) Hash(a[i]);
    for(char x='a';x<='z';x++)
        for(int i=1;i<=h[x];i++)
            if(x!='h') res.push_back(x);
    return res;
}

//化简
void simplify(VSI ans[N][N])
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            //对组成多项式的单项式求最简式
            for(int k=0;k<ans[i][j].size();k++) ans[i][j][k].first=get_min(ans[i][j][k].first);

            //排列项
            sort(ans[i][j].begin(),ans[i][j].end());

            //合并同类项
            VSI res;    //临时矩阵
            int ne=0,num=0;
            for(int k=0;k<ans[i][j].size();k=ne)
            {
                num=ans[i][j][k].second;
                ne=k+1;
                while(ne<ans[i][j].size() && ans[i][j][k].first==ans[i][j][ne].first)
                {
                    num+=ans[i][j][ne].second;
                    ne++;
                }
                res.push_back({ans[i][j][k].first,num});
            }

            //将临时矩阵复制到答案矩阵
            ans[i][j].clear();
            for(int k=0;k<res.size();k++) if(res[k].second!=0) ans[i][j].push_back(res[k]);
        }
    return ;
}

//输出
void print(VSI ans[N][N])
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<ans[i][j].size();k++) cout<<ans[i][j][k].second<<ans[i][j][k].first<<' ';
            puts("");
        }
    puts("");
    return ;
}

int main()
{
    //填入第一个矩阵
    VSI ans[N][N];
    ans[0][0].push_back({"b",1});
    ans[0][1].push_back({"a",1});
    ans[0][2].push_back({"0",0});
    ans[1][0].push_back({"a",-1});
    ans[1][1].push_back({"b",1});
    ans[1][2].push_back({"0",0});
    ans[2][0].push_back({"0",0});
    ans[2][1].push_back({"0",0});
    ans[2][2].push_back({"1",1});

    //填入后面相乘的矩阵
    SI op1[N][N]=
    {
        {{"d",1},{"0",0},{"c",1}},
        {{"0",0},{"1",1},{"0",0}},
        {{"c",-1},{"0",0},{"d",1}}
    };
    SI op2[N][N]=
    {
        {{"1",1},{"0",0},{"0",0}},
        {{"0",0},{"f",1},{"e",-1}},
        {{"0",0},{"e",1},{"f",1}}
    };
    SI op3[N][N]=
    {
        {{"d",1},{"0",0},{"c",-1}},
        {{"0",0},{"1",1},{"0",0}},
        {{"c",1},{"0",0},{"d",1}}
    };
    SI op4[N][N]=
    {
        {{"b",1},{"a",-1},{"0",0}},
        {{"a",1},{"b",1},{"0",0}},
        {{"0",0},{"0",0},{"1",1}}
    };

    //带参数的矩阵乘法
    mul(ans,op1);
    mul(ans,op2);
    mul(ans,op3);
    mul(ans,op4);

    //化简
    simplify(ans);

    //输出
    print(ans);

    return 0;
}