Ccf-csp 202112-3 boarding pass bar code 100 points

Original link ：CCF-CSP 202112-3 Boarding pass bar code

Reference blog ：
CSP 202112-3 Boarding pass bar code
CSP 202112-3 Boarding pass bar code （ Detailed illustration ）

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=929;

int main()
{
    
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int w,s; cin>>w>>s;
    string str; cin>>str;
    vector<int> v;
    for(int i=0;i<str.size();i++)
    {
    
        if(i==0)// At the beginning of coding , Encoder in uppercase mode .
        {
        // If the first character is lowercase 
            if(islower(str[i])) v.push_back(27);
            else if(isdigit(str[i])) v.push_back(28);
        }
        if(isdigit(str[i]))
        {
    
            // Big / A lowercase letter -> Numbers 
            if(i-1>=0 && !isdigit(str[i-1])) v.push_back(28);
            int tmp=str[i]-'0';
            v.push_back(tmp);
        }
        else if(isupper(str[i]))
        {
    
            // Numbers -> Capitalization 
            if(i-1>=0 && isdigit(str[i-1])) v.push_back(28);
            // A lowercase letter -> Capitalization 
            if(i-1>=0 && islower(str[i-1]))
            {
    
                v.push_back(28);
                v.push_back(28);
            }
            int tmp=str[i]-'A';
            v.push_back(tmp);
        }
        else if(islower(str[i]))
        {
    
            if(i-1>=0 && !islower(str[i-1])) v.push_back(27);
            int tmp=str[i]-'a';
            v.push_back(tmp);
        }
    }
    if((int)v.size()%2!=0) v.push_back(29);
    vector<int> d;
    for(int i=0;i<v.size();i+=2)
    {
    
        int tmp=30*v[i]+v[i+1];
        d.push_back(tmp);
    }
    if(s==-1)
    {
    
        int len=1+d.size();
        if(len>w) w=(len/w+1)*w;
        while(len<w)
        {
    
            d.push_back(900);
            len++;
        }
        cout<<len<<endl;
        for(auto tmp:d) cout<<tmp<<endl;
    }
    else
    {
    
        int k=pow(2,s+1);// Check the number of codewords 
        int ltmp=1+d.size()+k;
        while(ltmp%w!=0)
        {
    
            d.push_back(900);
            ltmp++;// Full length 
        }
        int len=ltmp-k;// Number of all data codewords , Including length codewords 、 Valid data codeword 、 Fill codeword 
        // Calculation dx
        vector<int> dx(len+k,0);// The length of itself len, multiply x Of k Power , So add k The length of 
        dx[0]=len;
        for(int i=0;i<d.size();i++)
        {
    
            dx[i+1]=d[i];
            dx[i+1]%=mod;
        }
        // Calculation dx
        vector<int> gx(k+1,0);
        gx[0]=-3; gx[1]=1;
        for(int i=2;i<=k;i++)
        {
    
            vector<int> tmp;
            tmp.assign(gx.begin(),gx.end());
            gx[0]=0;
            for(int j=1;j<=k;j++) gx[j]=tmp[j-1];
            ll tt=1;
            for(int j=0;j<i;j++) tt=(tt*3)%mod;
            for(int j=0;j<=k;j++)
            {
    
                tmp[j]=(tmp[j]*tt)%mod;
                tmp[j]*=-1;
                gx[j]=(tmp[j]+gx[j])%mod;
            }
        }
        reverse(gx.begin(),gx.end());
        for(int i=0;i<dx.size()-k;i++)
        {
    
            int tt=dx[i];
            for(int j=0;j<gx.size();j++)
            {
    
                dx[i+j]=(dx[i+j]-(tt*gx[j])%mod)%mod;
            }
        }
        for(int i=dx.size()-k;i<dx.size();i++)
        {
    
            if(-dx[i]<0)
            {
    
                dx[i]%=mod;
                d.push_back(mod-dx[i]);
            }
            else 
            {
    
                dx[i]%=mod;
                d.push_back(-dx[i]);
            }
        }
        cout<<len<<endl;
        for(auto tmp:d) cout<<tmp<<endl;
    }
    return 0;
}