reference resources

Reference problem solution 1
The blogger above actually said it very carefully. Maybe the polynomial is a little obscure, but after understanding it, I found that the blogger did say it in detail.

calculation g ( x ) g(x) g(x)

The first difficulty in this problem is how to calculate polynomials g ( x ) g(x) g(x).
According to the title description, you can know g ( x ) = ( x − 3 ) ⋅ ( x − 3 2 ) ⋅ . . . ⋅ ( x − 3 k ) g(x)=(x-3)·(x-3^2)·...·(x-3^k) g(x)=(x−3)⋅(x−32)⋅...⋅(x−3k)
I remember the teacher taught me a method, that is, if you want to calculate the expansion of parentheses, x j x^j Coefficient of xj a j a_j aj, so a j a_j aj# must be from the shape x m ⋅ x n , s . t . m + n = j x^m·x^n,s.t. m+n=j xm ⋅ xn,s.t.m+n=j, so the coefficient of a certain term is given as follows: a j = ∑ ∀ m , n , m + n = j a m ⋅ a n a_j=\sum_{{{\forall}}m,n, \\m+n=j}a_m·a_n aj​=∀m,n,m+n=j∑​am​⋅an​

However, it is unrealistic to finish the calculation in one breath. In fact, it can be combined one by one according to the two brackets. Altogether k k k parentheses, then you need to merge k − 1 k-1 k − 1 time.

For example, let's merge first q 2 ( x ) = ( x − 3 ) ⋅ ( x − 3 2 ) q_2(x)=(x-3)·(x-3^2) q2​(x)=(x−3)⋅(x−32),
Re merge q 3 ( x ) = q 2 ( x ) ⋅ ( x − 3 3 ) q_3(x)=q_2(x)·(x-3^3) q3 (x)=q2 (x) ⋅ (x − 33) then becomes a dynamic programming. As you can see, this question contains x x If the number of times of each bracket of x is 1, the initial state can be determined first G [ k ] = − 3 , G [ k − 1 ] = 1 G[k]=-3,G[k-1]=1 G[k]=−3,G[k−1]=1

We want to start from low order ( x − 3 ) (x-3) (x − 3) pushed x k x^k Coefficient of xk G [ 0 ] G[0] G[0], so as to determine the coefficient of each number of times.

Then merge with the above q 2 ( x ) = ( x − 3 ) ( x − 3 2 ) q_2(x)=(x-3)(x-3^2) When q2 (x)=(x − 3)(x − 32) is taken as an example, it can be seen that the maximum number of merging of these two items is 2, and can only be determined by x ⋅ x x·x X ⋅ x composition. So you can fill in G [ k − 2 ] = 1 G[k-2]=1 G[k−2]=1

Since the first bracket and the second bracket are currently combined, i=0 still exists at this time, so it is accurate G [ k − 2 − i ] = 1 G[k-2-i]=1 G[k−2−i]=1

about q 2 ( x ) q_2(x) Other powers of q2 (x), such as x = x 1 x=x^1 x=x1, then q 2 ( x ) q_2(x) The coefficient of the first-order term of q2 (x), which can be multiplied by the X of the first bracket by the coefficient of the second bracket( − 9 -9 − 9), and the second bracket x x x times the coefficient of the first bracket ( − 3 ) (-3) (− 3) is obtained by adding.
In principle, if the bracket here is also a polynomial, it will be very troublesome. Fortunately, each bracket is a polynomial. So after the merger x j x_j xj# must come from the previous x j x_j The coefficient of xj ， is multiplied by the constant of the brackets to be merged, plus the original x j − 1 x_{j-1} Factor of xj − 1 multiplied by new bracket x x The coefficients of x (identical to 1) are added together.

For code implementation, the current polynomial will be recorded before merging parentheses to avoid coverage.

Polynomial division

This is the second difficulty. I'm stupid. I've been thinking about the blogger's code for a long time. In fact, the polynomial division of code is simpler than manual calculation, because manual calculation still needs to determine how many times to multiply it. But in fact, when the code is implemented, it only cares about the current multiplication coefficient, that is, the coefficient with the highest divisor.

Because we use arrays to represent polynomials, multiply x x The operation of the power of x is just the way of array. In fact, using bit 0 to represent the highest degree of the current polynomial implies the operation of alignment.

Store checksum

By reason, you can D ( x ) D(x) Update and store the check code in place on D(x), but directly D ( x ) D(x) D(x) how many more digits( k − 1 k-1 K − 1 polynomial is an array of length k) so that k-1 polynomial can be saved to avoid tossing.

At this point, the problem is almost finished.

code

#include <iostream>
#include <vector>
#include <valarray>

using namespace std;
int w, s;
int UPPER = 0;
int LOWER = 1;
int DIGIT = 2;

void
coding(string &input, vector<int> &vec) {
    int state = UPPER;
    for (int i = 0; i < input.length(); ++i) {
        if ('A' <= input[i] && input[i] <= 'Z') {
            // UPPER
            if (state == LOWER) {
                // LOWER -> DIGIT -> UPPER
                vec.push_back(28);
                vec.push_back(28);
            } else if (state == DIGIT) {
                vec.push_back(28);
            }
            vec.push_back(input[i] - 'A');
            state = UPPER;
        } else if ('a' <= input[i] && input[i] <= 'z') {
            if (state != LOWER) {
                vec.push_back(27);
            }
            vec.push_back(input[i] - 'a');
            state = LOWER;
        } else if ('0' <= input[i] && input[i] <= '9') {
            if (state != DIGIT) {
                vec.push_back(28);
            }
            vec.push_back(input[i] - '0');
            state = DIGIT;
        }
    }
}

int mazi(int a, int b) {
    return 30 * a + b;
}

void
mazi(vector<int> &code, vector<int> &ma) {
    for (int i = 0; i < code.size(); i += 2) {
        ma.push_back(mazi(code[i], code[i + 1]));
    }

}


ostream &operator<<(ostream &os, vector<int> &m) {
    for (auto &x: m) {
        cout << x << "\n";
    }
    return os;
}

int MOD = 929;


int main() {
    cin >> w >> s;
    string raw_str;
    cin >> raw_str;
    vector<int> coded;
    coding(raw_str, coded);

    if (coded.size() % 2 == 1) {
        coded.push_back(29);
    }
    vector<int> mazied;
    mazi(coded, mazied);

    int k = s != -1  ? pow(2, s + 1)  : 0;
    while ((mazied.size() + k + 1) % w != 0) {
        mazied.push_back(900);
    }
    cout << mazied.size() + 1 << "\n";

    if (s != -1) {

        // construct k polynomial, G[0] means the x^k, G[1] means x^{k-1}, ..., x^2, x ,C
        vector<int> G(k + 1, 0);
        G[k] = -3;
        G[k - 1] = 1;
        // (x^2 - 9)
        int tmp_C = -9;

        // calc our G(x), follow (x-3) * (x-3^2) ..
        for (int i = 0; i < k - 1; ++i) {
            vector<int> old_G(k + 1);
            for (int j = k - i - 1; j <= k; ++j) {
                old_G[j] = G[j];
            }

            /**
             * for example:
             * (x-3)(x-3^2)
             * we know G[k] = -3,G[k-1] = 1 ( as we see (x-3) here)
             * then going to multiply to (x^2 - 9) (why tmp_C = - 9 here)
             * update C(x^1) = G[k-1] = -9 + (-3) = G[k-1] * tmp_C + G[k-2] = G[k-1] * tmp_C + old_G[k]
             * */
            for (int j = k - i - 1; j <= k; ++j) {
                G[j] = (G[j] % MOD) * (tmp_C % MOD) % MOD;
            }
            for (int j = k - i - 1; j < k; ++j) {
                // consider lower index will also construct this
                G[j] += old_G[j + 1] % MOD;
            }
            // as we multiply each loop,
            // the current highest must construct by all x param, so must be 1
            G[k - i - 2] = 1;
            tmp_C *= 3;
            tmp_C %= MOD;
        }
        vector<int> D(mazied.size() + 1 + k,0);
        D[0] = mazied.size() + 1;
        for (int i = 0; i < mazied.size(); ++i) {
            D[i+1] = mazied[i];
            D[i+1] %= MOD;
        }
        auto polynomial_divide = [&k, &mazied](vector<int> &Dx, vector<int> &Gx) {
            /**
             * Dx/Gx
             * */
            // the divide means, we will align the low index to high poly index,
            // so for each param in Gx, we will multiply them as D(x) current high poly param
            // i=0 for the highest index
            for (int i = 0; i < Dx.size() - k; ++i) {
                int current_C = Dx[i];
                // multiply all poly in Gx by C
                // Gx[0] is x^k
                for (int j = 0; j < Gx.size(); ++j) {
                    Dx[i + j] = Dx[i + j] - ((Gx[j] * current_C) % MOD);
                    Dx[i + j] %= MOD;
                }
            }
            //update checksum
            for (long long i = Dx.size() - Gx.size() + 1; i < Dx.size(); ++i) {
                if (-Dx[i] < 0)
                    mazied.push_back(MOD+ (-Dx[i] % MOD));
                else
                    mazied.push_back(-Dx[i] % MOD);

            }
//            cout << Gx;
        };
//        cout << "D=" << D;
//        cout << "G=" << G;
        polynomial_divide(D, G);

    }
    cout << mazied;
}