标签: NTT

  • CFGYM 102823 CCPC2018 桂林 B题 Array Modify

    题倒是还行,达标找规律找出来结论,然后就想到了一个多项式快速幂的做法。

    一开始写的两个log的快速幂,TLE。

    然后尝试改成exp+log,跑得看起来快了,但是遇到多组数据(n的大小递增的时候)就挂掉了?

    仔细调查后发现源于自己一直以来exp函数内一直存在的错误:

    exp内调用了log,log内调用了inv,exp内给G0(用以存储log返回值的数组)预留了upper2n(2*n)的空间,但是inv内却使用了upper2n(3*n+1)的空间!

    (调试方法:数组切换为动态分配并开启内存检查)

    对于只计算exp一次而言,这个错误不会造成影响,但是计算多次的时候由于空间污染会导致错误结果。

    解决方法:在exp内也预留upper2n(3*n)的空间,通过本题。

    另外小测试了一下,两个log的多项式快速幂跑本题极限数据,NTT变换的多项式总长度为“27262976”,而exp+log实现的快速幂,NTT变换的多项式总长度为 19922408,我原本以为因为常数原因,exp+log会跑得更慢,没想到事实并非如此。

     

    // luogu-judger-enable-o2
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using int_t = long long int;
    using std::cin;
    using std::cout;
    using std::endl;
    const int mod = 998244353;
    const int g = 3;
    const int LARGE = 1 << 20;
    int revs[21][LARGE + 1];
    
    int power(int base, int index);
    void transform(int* A, int len, int arg);
    void poly_inv(const int* A, int n, int* result);
    void poly_log(const int* A, int n, int* result);
    void poly_exp(const int* A, int n, int* result);
    
    std::vector transform_count;
    #ifdef TDEBUG
    #define TRANSFORM_DEBUG(n) \
        { transform_count.push_back(n); }
    #else
    #define TRANSFORM_DEBUG(n)
    #endif
    int bitRev(int base, int size2) {
        int result = 0;
        for (int i = 1; i < size2; i++) {
            result |= (base & 1);
            base >>= 1;
            result <<= 1;
        }
        result |= (base & 1);
        return result;
    }
    int upper2n(int x) {
        int result = 1;
        while (result < x)
            result *= 2;
        return result;
    }
    int main() {
        std::ios::sync_with_stdio(false);
    
        for (int i = 0; (1 << i) <= LARGE; i++) {
            for (int j = 0; j < LARGE; j++) {
                revs[i][j] = bitRev(j, i);
            }
        }
        static int F[LARGE + 1], G[LARGE + 1];
        static int arr[LARGE + 1];
        int T;
        cin >> T;
        for (int_t _i = 1; _i <= T; _i++) {
            memset(F, 0, sizeof(F));
            memset(G, 0, sizeof(G));
            memset(arr, 0, sizeof(arr));
            int_t n, L, m;
            cin >> n >> L >> m;
    
            for (int_t i = 1; i <= n; i++)
                cin >> arr[i];
            int size2 = upper2n(4 * (n + 1));
            for (int i = 0; i < size2; i++) {
                if (i < L)
                    F[i] = 1;
                else
                    F[i] = 0;
                G[i] = 0;
            }
    #ifdef DEBUG
            cout << "init = " << endl;
            cout << "F = ";
            for (int_t i = 0; i < 2 * n; i++)
                cout << F[i] << " ";
            cout << endl;
    
            cout << "G = ";
            for (int_t i = 0; i < 2 * n; i++)
                cout << G[i] << " ";
            cout << endl;
    #endif
    
            poly_log(F, n, G);
    #ifdef DEBUG
            cout << "after log = " << endl;
            cout << "G = ";
            for (int_t i = 0; i < 2 * n; i++)
                cout << G[i] << " ";
            cout << endl;
    #endif
            for (int i = 0; i < n; i++)
                G[i] = G[i] * m % mod;
            for (int i = 0; i < size2; i++)
                F[i] = 0;
    #ifdef DEBUG
            cout << "before exp = " << endl;
            cout << "G = ";
            for (int_t i = 0; i < 2 * n; i++)
                cout << G[i] << " ";
            cout << endl;
    #endif
            poly_exp(G, n, F);
    #ifdef DEBUG
            cout << "after exp = " << endl;
            cout << "F = ";
            for (int_t i = 0; i < 2 * n; i++)
                cout << F[i] << " ";
            cout << endl;
    #endif
    
            for (int i = 0; i < size2; i++) {
                if (i >= n)
                    F[i] = 0;
                if (i >= n && i < 2 * n)
                    G[i] = arr[i - n + 1];
                else
                    G[i] = 0;
            }
            std::reverse(G + n, G + 2 * n);
    
    #ifdef DEBUG
            cout << "F = ";
            for (int_t i = 0; i < 2 * n; i++)
                cout << F[i] << " ";
            cout << endl;
    
            cout << "G = ";
            for (int_t i = 0; i < 2 * n; i++)
                cout << G[i] << " ";
            cout << endl;
    #endif
    
            transform(F, size2, 1);
            transform(G, size2, 1);
            for (int i = 0; i < size2; i++)
                F[i] = (int_t)F[i] * G[i] % mod;
            transform(F, size2, -1);
            int inv = power(size2, -1);
            std::reverse(F + n, F + 2 * n);
            cout << "Case " << _i << ": ";
    
            for (int i = n; i < 2 * n; i++) {
                cout << (int_t)F[i] * inv % mod << " ";
            }
            cout << endl;
    #ifdef DEBUG
            for (int i = 0; i < n; i++) {
                cout << "F " << i << " = " << F[i] << endl;
            }
    #endif
    #ifdef TDEBUG
            for (auto x : transform_count) {
                cout << x << " ";
            }
            cout << endl;
    #endif
        }
        return 0;
    }
    
    int power(int base, int index) {
        const int phi = mod - 1;
        index = (index % phi + phi) % phi;
        base = (base % mod + mod) % mod;
        int result = 1;
        while (index) {
            if (index & 1)
                result = (int_t)result * base % mod;
            base = (int_t)base * base % mod;
            index >>= 1;
        }
        return result;
    }
    void transform(int* A, int len, int arg) {
        TRANSFORM_DEBUG(len);
        int size2 = int(log2(len) + 0.5);
        for (int i = 0; i < len; i++) {
            int x = revs[size2][i];
            if (x > i)
                std::swap(A[i], A[x]);
        }
        for (int i = 2; i <= len; i *= 2) {
            int mr = power(g, (int_t)arg * (mod - 1) / i);
            for (int j = 0; j < len; j += i) {
                int curr = 1;
                for (int k = 0; k < i / 2; k++) {
                    int u = A[j + k];
                    int t = (int_t)A[j + k + i / 2] * curr % mod;
                    A[j + k] = (u + t) % mod;
                    A[j + k + i / 2] = (u - t + mod) % mod;
                    curr = (int_t)curr * mr % mod;
                }
            }
        }
    }
    //计算多项式A在模x^n下的逆元
    // C(x)<-2B(x)-A(x)B^2(x)
    void poly_inv(const int* A, int n, int* result) {
        if (n == 1) {
            result[0] = power(A[0], -1);
            return;
        }
        poly_inv(A, n / 2 + n % 2, result);
        static int temp[LARGE + 1];
        int size2 = upper2n(3 * n + 1);
        for (int i = 0; i < size2; i++) {
            if (i < n)
                temp[i] = A[i];
            else
                temp[i] = 0;
        }
        transform(temp, size2, 1);
        transform(result, size2, 1);
        for (int i = 0; i < size2; i++) {
            result[i] =
                ((int_t)2 * result[i] % mod -
                 (int_t)temp[i] * result[i] % mod * result[i] % mod + 2 * mod) %
                mod;
        }
        transform(result, size2, -1);
        for (int i = 0; i < size2; i++) {
            if (i < n) {
                result[i] = (int_t)result[i] * power(size2, -1) % mod;
            } else {
                result[i] = 0;
            }
        }
    }
    void poly_log(const int* A, int n, int* result) {
        int size2 = upper2n(3 * n + 1);
        static int Ad[LARGE + 1];
        for (int i = 0; i < size2; i++) {
            if (i < n) {
                Ad[i] = (int_t)(i + 1) * A[i + 1] % mod;
            } else {
                Ad[i] = 0;
            }
            result[i] = 0;
        }
        transform(Ad, size2, 1);
        poly_inv(A, n, result);
        transform(result, size2, 1);
        for (int i = 0; i < size2; i++) {
            result[i] = (int_t)result[i] * Ad[i] % mod;
        }
        transform(result, size2, -1);
        for (int i = 0; i < size2; i++)
            if (i < n)
                result[i] = (int_t)result[i] * power(size2, -1) % mod;
            else
                result[i] = 0;
        for (int i = n - 1; i >= 1; i--) {
            result[i] = (int_t)result[i - 1] * power(i, -1) % mod;
        }
        result[0] = 0;
    }
    void poly_exp(const int* A, int n, int* result) {
        if (n == 1) {
            assert(A[0] == 0);
            result[0] = 1;
            return;
        }
        poly_exp(A, n / 2 + n % 2, result);
        static int Ax[LARGE + 1];
        // memset(G0, 0, sizeof(G0));
        // memset(Ax,0,sizeof(Ax));
        int size2 = upper2n(3 * n + 1);
        // int* G0 = new int[size2];
        static int G0[LARGE + 1];
        for (int_t i = 0; i < size2; i++) {
            if (i < n)
                Ax[i] = A[i];
            else
                Ax[i] = 0;
            G0[i] = 0;
        }
        poly_log(result, n, G0);
    
        transform(Ax, size2, 1);
        transform(G0, size2, 1);
        transform(result, size2, 1);
        for (int i = 0; i < size2; i++)
            result[i] =
                (result[i] - (int_t)result[i] * (G0[i] - Ax[i] + mod) % mod + mod) %
                mod;
        transform(result, size2, -1);
        for (int i = 0; i < size2; i++)
            if (i < n)
                result[i] = (int_t)result[i] * power(size2, -1) % mod;
            else
                result[i] = 0;
        // delete[] G0;
    }
    
  • UOJ86 mx的组合数

    没看题解A的第一道多项式题…开心qwq

    还是一遍A的

    $$ \text{直接考虑卢卡斯定理。} \\ \text{首先考虑求出来模}p\text{为0的方案数。} \\ \text{设}n\text{的}p\text{进制下为}n_1n_2….n_k \\ \left( \begin{array}{c} x\\ n\\ \end{array} \right) =\left( \begin{array}{c} x_1\\ n_1\\ \end{array} \right) \left( \begin{array}{c} x_2\\ n_2\\ \end{array} \right) …\left( \begin{array}{c} x_k\\ n_k\\ \end{array} \right) \\ \text{显然如果存在任意}x_i<n_i,\text{则}\left( \begin{array}{c} x\\ n\\ \end{array} \right) =0\left( \text{mod }p \right) \\ \text{设}f\left( n,k \right) \text{表示考虑低}n\text{位,是否卡中}x\text{的上界时的结果多项式。} \\ \text{令}g\text{为模}p\text{意义下的原根,这个多项式的}i\text{次项的意义是选定的组合数在模}p\text{意义下为}g^i\text{的方案数。} \\ f\left( -\text{1,}true \right) =f\left( -\text{1,}false \right) =1 \\ \text{对于}i\ge \text{0,}f\left( i,false \right) =\left( \sum_{n_i\le k\le p-1}{x^y\left( \text{其中}g^y=\left( \begin{array}{c} k\\ n_i\\ \end{array} \right) \,\,\text{mod }p \right)} \right) f\left( i-\text{1,}false \right) \\ f\left( i,true \right) =x^y\left( \text{其中}g^y=\left( \begin{array}{c} x_i\\ n_i\\ \end{array} \right) \text{mod }p \right) f\left( i-\text{1,}true \right) +\left( \sum_{n_i\le k\le x_i-1}{x^y\left( \text{其中}g^y=\left( \begin{array}{c} k\\ n_i\\ \end{array} \right) \,\,\text{mod }p \right)} \right) f\left( i-\text{1,}false \right) \\ \text{所有卷积均为指数模}\varphi \left( p \right) \text{意义下的循环卷积。} \\ \text{最终}f\left( \lceil \log _px \rceil ,true \right) \text{即为结果多项式,}k\text{次项前的系数表示使得}\left( \begin{array}{c} x\\ n\\ \end{array} \right) =g^k\text{的方案数}\left( \text{不包括}0 \right) \text{。} \\ \text{复杂度}O\left( p\log p\log r \right) \\ \\ $$

    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <vector>
    using int_t = long long int;
    using lint_t = __int128;
    
    using std::cin;
    using std::cout;
    using std::endl;
    
    const int_t mod = 998244353;
    const int_t g0 = 3;
    const int_t LARGE = 1 << 16;
    int revs[17][LARGE];
    //模p意义下的某个数对应的原根的指数
    int_t map[LARGE];
    int_t fact[LARGE];
    std::vector<int_t> ndiv;
    int_t p, g, phi;
    lint_t n;
    int_t power(int_t base, int_t index, int_t mod = ::mod);
    void transform(int_t* A, int_t len, int_t arg);
    template <class T>
    void read(T& x) {
        x = 0;
        auto chr = getchar();
        while (isdigit(chr) == false) {
            chr = getchar();
        }
        while (isdigit(chr)) {
            x = x * 10 + chr - '0';
            chr = getchar();
        }
    }
    int_t bitRev(int_t x, int_t len) {
        int_t result = 0;
        for (int i = 1; i < len; i++) {
            result |= (x & 1);
            x >>= 1;
            result <<= 1;
        }
        return result | (x & 1);
    }
    int_t upper2n(int_t x) {
        int_t result = 1;
        while (result < x) result *= 2;
        return result;
    }
    void poly_mul(const int_t* A, const int_t* B, int_t* C) {
        static int_t Ax[LARGE], Bx[LARGE];
        std::copy(A, A + p, Ax);
        std::copy(B, B + p, Bx);
    #ifdef DEBUG
        cout << "mul " << endl;
        for (int i = 0; i < p; i++) cout << A[i] << " ";
        cout << endl;
        for (int i = 0; i < p; i++) cout << B[i] << " ";
        cout << endl;
    
    #endif
        int_t size2 = upper2n(2 * p);
        for (int_t i = p; i < size2; i++) Ax[i] = Bx[i] = 0;
    
        transform(Ax, size2, 1);
        transform(Bx, size2, 1);
        for (int_t i = 0; i < size2; i++) Ax[i] = Ax[i] * Bx[i] % mod;
        transform(Ax, size2, -1);
    #ifdef DEBUG
        cout << "mul got ";
        for (int i = 0; i < size2; i++)
            cout << Ax[i] * power(size2, -1) % mod << " ";
        cout << endl;
    #endif
        for (int_t i = phi; i < size2; i++) {
            Ax[i % phi] = (Ax[i % phi] + Ax[i]) % mod;
        }
        const auto inv = power(size2, -1, mod);
    #ifdef DEBUG
        cout << "C = ";
    #endif
        for (int_t i = 0; i < phi; i++) {
            C[i] = Ax[i] * inv % mod;
    #ifdef DEBUG
            cout << C[i] << " ";
    #endif
        }
    }
    const int_t OFFSET = 1;
    std::vector<int_t> div(lint_t x) {
        std::vector<int_t> result;
        while (x) {
            result.push_back(x % p);
            x /= p;
        }
        return result;
    }
    int_t C(int_t n, int_t m) {
        return ((fact[n] - fact[m] - fact[n - m]) % phi + phi) % phi;
    }
    void process(lint_t x, int_t* output) {
        static int_t dp[103][2][LARGE];
        memset(dp, 0, sizeof(dp));
        dp[-1 + OFFSET][0][0] = dp[-1 + OFFSET][1][0] = 1;
        auto xdiv = div(x);
        int_t size = std::max(xdiv.size(), ndiv.size()) + 1;
        xdiv.resize(size);
        ndiv.resize(size);
        for (int_t i = 0; i < size; i++) {
            // false
            {
                static int_t poly[LARGE];
                std::fill(poly, poly + p, 0);
                for (int_t j = ndiv[i]; j <= p - 1; j++) {
                    poly[C(j, ndiv[i])] += 1;
                }
                poly_mul(poly, dp[i - 1 + OFFSET][0], dp[i + OFFSET][0]);
            }
            // true
            {
                auto& curr = dp[i + OFFSET][1];
                static int_t poly[LARGE], output[LARGE];
                std::fill(poly, poly + p, 0);
                for (int_t j = ndiv[i]; j <= xdiv[i] - 1; j++)
                    poly[C(j, ndiv[i])] += 1;
                poly_mul(poly, dp[i - 1 + OFFSET][0], output);
                std::fill(poly, poly + p, 0);
                for (int j = 0; j < phi; j++) curr[j] = (curr[j] + output[j]) % mod;
                if (xdiv[i] >= ndiv[i]) poly[C(xdiv[i], ndiv[i])] += 1;
                poly_mul(poly, dp[i - 1 + OFFSET][1], output);
                for (int j = 0; j < phi; j++) curr[j] = (curr[j] + output[j]) % mod;
            }
        }
        int_t zero = x % mod;
        for (int i = 0; i < phi; i++) {
            int_t x = power(g, i, p);
            output[x] = (output[x] + dp[size - 1 + OFFSET][1][i]) % mod;
            zero = (zero - dp[size - 1 + OFFSET][1][i] + mod) % mod;
        }
        output[0] = zero;
    }
    int main() {
        for (int i = 1; i <= 16; i++) {
            for (int j = 0; j < (1 << i); j++) {
                revs[i][j] = bitRev(j, i);
            }
        }
        lint_t left, right;
        read(p);
        read(n);
        read(left);
        read(right);
        phi = p - 1;
        ndiv = div(n);
        std::vector<int_t> divisors;
        for (int_t i = 2; i * i <= phi; i++) {
            if (phi % i == 0) {
                divisors.push_back(i);
                if (i * i != phi) divisors.push_back(phi / i);
            }
        }
        for (g = 2; g <= p - 1; g++) {
            bool ok = true;
            for (int_t x : divisors) {
                if (power(g, x, p) == 1 && x != phi) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                break;
            }
        }
        for (int i = 0; i < phi; i++) map[power(g, i, p)] = i;
        for (int_t i = 2; i < p; i++) fact[i] = (fact[i - 1] + map[i]) % phi;
        static int_t rights[LARGE], lefts[LARGE];
        process(right, rights);
        process(left - 1, lefts);
        for (int i = 0; i < p; i++) {
            printf("%lld\n", (rights[i] - lefts[i] + mod) % mod);
        }
        return 0;
    }
    
    void transform(int_t* A, int_t len, int_t arg) {
        int_t size2 = log2(len);
        for (int i = 0; i < len; i++) {
            int x = revs[size2][i];
            if (x > i) std::swap(A[i], A[x]);
        }
        for (int i = 2; i <= len; i *= 2) {
            int_t mr = power(g0, arg * (mod - 1) / i, mod);
            for (int_t j = 0; j < len; j += i) {
                int_t curr = 1;
                for (int_t k = 0; k < i / 2; k++) {
                    int_t u = A[j + k], t = A[j + k + i / 2] * curr % mod;
                    A[j + k] = (u + t) % mod;
                    A[j + k + i / 2] = (u - t + mod) % mod;
                    curr = curr * mr % mod;
                }
            }
        }
    }
    
    int_t power(int_t base, int_t index, int_t mod) {
        int_t result = 1;
        if (index < 0) index = (index % (mod - 1) + mod - 1) % (mod - 1);
        while (index) {
            if (index & 1) result = result * base % mod;
            base = base * base % mod;
            index >>= 1;
        }
        return result;
    }

     

  • 洛谷4173 残缺的字符串

    $$ \text{这东西好神奇啊}qwq \\ \text{求出字符串}B\text{在字符串}A\text{中所有出现的位置。} \\ \text{设字符串下标均从0开始} \\ \text{设}A_x\text{表示}A\text{的第}x\text{个字符。} \\ \text{来定义一个神奇的函数,称之为匹配函数} \\ \text{设}m\text{为}B\text{串的长度} \\ P\left( x \right) =\sum_{0\le i<m}{\left( \begin{array}{c} A_{x-m+1+i}-B_i\\ \end{array} \right) ^2} \\ \text{注意到这个函数当且仅当字符串}B\text{出现在串}A\text{以}x\text{结尾的位置时才为}0 \\ \text{暴力计算起来仍然是}O\left( n^2 \right) \text{的} \\ \text{考虑拆开} \\ P\left( x \right) =\sum_{0\le i<m}{\begin{array}{c} B_i^2+A_{x-m+1+i}^2-2B_iA_{x-m+1+i}\\ \end{array}} \\ =\sum_{0\le i<m}{B_i^2}+\sum_{0\le i<m}{A_{x-m+1+i}^2}-2\sum_{0\le i<m}{B_iA_{x-m+1+i}} \\ \text{前两个求和符号可以直接计算。} \\ \text{第三个怎么搞?} \\ \text{设}T=B^R,\text{即}T\text{是}B\text{的反串。} \\ \text{所以存在}T_x=B_{m-x-1} \\ \text{故}P\left( x \right) =\sum_{0\le i<m}{T_i^2}+\sum_{0\le i<m}{A_{x-m+1+i}^2}-2\sum_{0\le i<m}{T_{m-i-1}A_{x-m+1+i}} \\ \text{注意到一个细节,}\left( m-i-1 \right) +\left( x-m+1+i \right) =x \\ \text{所以我们可以强行凑成卷积} \\ \sum_{0\le i<m}{T_{m-i-1}A_{x-m+1+i}} \\ =\sum_{0<m-i\le m}{T_{m-i-1}A_{x-m+1+i}} \\ =\sum_{0<i\le m}{T_{i-1}A_{x-i+1}} \\ =\sum_{-1<i-1\le m-1}{T_{i-1}A_{x-i+1}} \\ =\sum_{0\le i\le m-1}{T_iA_{x-i}} \\ =\sum_{i+j=x}{T_iA_j} \\ P\left( x \right) =\sum_{0\le i<m}{T_i^2}+\sum_{0\le i<m}{A_{x-i}^2}-2\sum_{i+j=x}{T_iA_j} \\ \text{当}x\ge m-\text{1的时候,}\sum_{0\le i\le m-1}{T_iA_{x-i}}=\sum_{0\le i\le x}{T_iA_{x-i}} \\ \text{然后可以卷积了}qwq \\ \text{带通配符怎么办?} \\ \text{设通配符的字符代码为}0 \\ \text{匹配函数变成}P\left( x \right) =\sum_{0\le i<m}{\left( \begin{array}{c} A_{x-m+1+i}-B_i\\ \end{array} \right) ^2A_{x-m+1+i}B_i} \\ =\sum_{0\le i<m}{\left( B_i^2+A_{x-m+1+i}^2-2B_iA_{x-m+1+i} \right) A_{x-m+1+i}B_i} \\ =\sum_{0\le i<m}{B_{i}^{3}A_{x-m+1+i}}+\sum_{0\le i<m}{B_iA_{x-m+1+i}^3}-2\sum_{0\le i<m}{A_{x-m+1+i}^2B_i^2} \\ B_x=T_{m-x-1} \\ P\left( x \right) =\sum_{0\le i<m}{T_{m-i-1}^3A_{x-m+1+i}}+\sum_{0\le i<m}{T_{m-i-1}A_{x-m+1+i}^3}-2\sum_{0\le i<m}{A_{x-m+1+i}^2T_{m-i-1}^2} \\ P\left( x \right) =\sum_{i+j=x}{T_i^3A_j}+\sum_{i+j=x}{T_iA_j^3}-2\sum_{i+j=x}{A_i^2T_j^2} \\ \text{仍然大力卷积即可。} \\ $$

    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <vector>
    using int_t = long long int;
    using std::cin;
    using std::cout;
    using std::endl;
    const int_t mod = 998244353;
    const int_t g = 3;
    const int_t LARGE = 1 << 20;
    int_t power(int_t base, int_t index);
    void transform(int_t* A, int_t size, int_t arg = 1);
    int_t bitRev(int_t x, int_t size2) {
        int_t result = 0;
        for (int_t i = 1; i < size2; i++) {
            result |= (x & 1);
            x >>= 1;
            result <<= 1;
        }
        return result | (x & 1);
    }
    constexpr inline int_t upper2n(int_t x) {
        int_t result = 1;
        while (result < x) result *= 2;
        return result;
    }
    int main() {
        int n, m;
        static char As[LARGE], Bs[LARGE], Ts[LARGE];
        scanf("%d%d%s%s", &m, &n, Bs, As);
        std::reverse_copy(Bs, Bs + m, Ts);
        // cout << Ts << endl;
        static int_t A1[LARGE], A2[LARGE], A3[LARGE];
        static int_t T1[LARGE], T2[LARGE], T3[LARGE];
        for (int_t i = 0; i < n; i++) {
            A1[i] = As[i];
            if (As[i] == '*') A1[i] = 0;
            A2[i] = A1[i] * As[i];
            A3[i] = A2[i] * As[i];
        }
        for (int_t i = 0; i < m; i++) {
            T1[i] = Ts[i];
            if (Ts[i] == '*') T1[i] = 0;
            T2[i] = T1[i] * Ts[i];
            T3[i] = T2[i] * Ts[i];
        }
        int_t size = upper2n(n + m + 1);
        transform(A1, size);
        transform(A2, size);
        transform(A3, size);
        transform(T1, size);
        transform(T2, size);
        transform(T3, size);
        static int_t result[LARGE];
        for (int_t i = 0; i < size; i++) {
            result[i] = (T3[i] * A1[i] % mod + T1[i] * A3[i] % mod -
                         2 * A2[i] * T2[i] % mod + 3 * mod) %
                        mod;
        }
        transform(result, size, -1);
        for (int_t i = 0; i < size; i++) {
            result[i] = result[i] * power(size, -1) % mod;
            // cout << "pos " << i << " " << result[i] << endl;
        }
        std::vector<int> results;
        for (int_t i = 0; i < n; i++) {
            if (result[i] == 0 && (i - m + 2 >= 1)) {
                results.push_back(i - m + 2);
            }
        }
        printf("%d\n", (int)results.size());
        for (int x : results) printf("%d ", x);
        return 0;
    }
    
    int_t power(int_t base, int_t index) {
        const auto phi = mod - 1;
        index = (index % phi + phi) % phi;
        base = (base % mod + mod) % mod;
        int_t result = 1;
        while (index) {
            if (index & 1) result = result * base % mod;
            index >>= 1;
            base = base * base % mod;
        }
        return result;
    }
    void transform(int_t* A, int_t size, int_t arg) {
        int_t size2 = log2(size);
        for (int_t i = 0; i < size; i++) {
            int_t x = bitRev(i, size2);
            if (x > i) std::swap(A[i], A[x]);
        }
        for (int_t i = 2; i <= size; i *= 2) {
            int_t mr = power(g, arg * (mod - 1) / i);
            for (int_t j = 0; j < size; j += i) {
                int_t curr = 1;
                for (int_t k = 0; k < i / 2; k++) {
                    int_t u = A[j + k];
                    int_t t = A[j + k + i / 2] * curr % mod;
                    A[j + k] = (u + t) % mod;
                    A[j + k + i / 2] = (u - t + mod) % mod;
                    curr = curr * mr % mod;
                }
            }
        }
    }

     

  • TJOI2016 求和

    $$ \text{题意:} \\ \text{求}f\left( n \right) =\sum_{0\le i\le n}{\sum_{0\le j\le i}{S_2\left( i,j \right) \times 2^j\times j!}} \\ \text{第二类斯特林数的通项公式:} \\ S\left( i,j \right) =\frac{1}{j!}\sum_{0\le k\le j}{\left( \begin{array}{c} j\\ k\\ \end{array} \right) \left( -1 \right) ^{j-k}k^i} \\ \text{代入,因为}j>i\text{时,}S_2\left( i,j \right) \text{为0,所以求和上界可以放到}n \\ f\left( n \right) =\sum_{0\le j\le n}{2^j\times j!\sum_{0\le i\le n}{S\left( i,j \right)}} \\ f\left( n \right) =\sum_{0\le j\le n}{2^j\sum_{0\le i\le n}{\sum_{0\le k\le j}{\left( \begin{array}{c} j\\ k\\ \end{array} \right) \times \left( -1 \right) ^{j-k}k^i}}} \\ \text{整理一下} \\ f\left( n \right) =\sum_{0\le j\le n}{j!\sum_{0\le k\le j}{\frac{2^j}{k!\left( j-k \right) !}\times \left( -1 \right) ^{j-k}}\sum_{0\le i\le n}{k^i}} \\ \text{注意,}\sum_{0\le i\le n}{k^i}\text{可以直接用等比数列求和公式}O\left( 1 \right) \text{计算!} \\ =\sum_{0\le j\le n}{j!\times 2^j\sum_{0\le k\le j}{\frac{\sum_{0\le i\le n}{k^i}}{k!}\times \frac{\left( -1 \right) ^{j-k}}{\left( j-k \right) !}}} \\ \text{这个式子可以卷积} \\ f\left( n \right) =\sum_{0\le j\le n}{j!\sum_{0\le k\le j}{\frac{\left( -1 \right) ^k\sum_{0\le i\le n}{k^i}}{k!}\times \frac{1}{\left( j-k \right) !}}} \\ \\ $$

     

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using std::cin;
    using std::cout;
    using std::endl;
    
    using int_t = long long int;
    
    const int_t mod = 998244353;
    const int_t g = 3;
    const int_t LARGE = 1 << 20;
    
    int_t power(int_t base, int_t index);
    int_t bitRev(int_t x, int_t size2);
    template <int_t arg = 1>
    void transform(int_t *A, int_t size);
    int_t upper2n(int_t x);
    
    int_t sum(int_t k, int_t n)
    {
        if (k == 1)
            return (n + 1) % mod;
        // if(k==0) return 0;s
        return ((power(k, n + 1) - 1) % mod * power(k - 1, -1) % mod) % mod;
    }
    
    int main()
    {
        int_t n;
        cin >> n;
        static int_t fact[LARGE] = {1};
        for (int_t i = 1; i <= n * 2; i++)
        {
            fact[i] = (fact[i - 1] * i) % mod;
        }
        static int_t A[LARGE];
        static int_t B[LARGE];
        int_t size = upper2n(2 * n + 1);
        for (int_t i = 0; i <= n; i++)
        {
            A[i] = ((sum(i, n)) % mod * power(fact[i], -1) % mod + mod) % mod;
            B[i] = power(fact[i], -1) * power(-1, i) % mod;
            // cout<<A[i]<<" ";
        }
        transform(A, size);
        transform(B, size);
        for (int_t i = 0; i <= size; i++)
            A[i] = A[i] * B[i] % mod;
        transform<-1>(A, size);
        int_t result = 0;
        for (int_t i = 0; i <= n; i++)
        {
            A[i] = A[i] * power(size, -1) % mod * fact[i] % mod * power(2, i) % mod;
            result = (result + A[i]) % mod;
        }
        cout << result << endl;
        return 0;
    }
    
    template <int_t arg = 1>
    void transform(int_t *A, int_t size)
    {
        int_t size2 = log2(size);
        for (int_t i = 0; i < size; i++)
        {
            int_t x = bitRev(i, size2);
            if (x > i)
                std::swap(A[i], A[x]);
        }
        for (int_t i = 2; i <= size; i *= 2)
        {
            int_t mr = power(g, arg * (mod - 1) / i);
            for (int_t j = 0; j < size; j += i)
            {
                int_t curr = 1;
                for (int_t k = 0; k < i / 2; k++)
                {
                    int_t u = A[j + k];
                    int_t t = A[j + k + i / 2] * curr % mod;
                    A[j + k] = (u + t) % mod;
                    A[j + k + i / 2] = (u - t + mod) % mod;
                    curr = (curr * mr) % mod;
                }
            }
        }
    }
    
    int_t upper2n(int_t x)
    {
        int_t result = 1;
        while (result < x)
            result *= 2;
        return result;
    }
    
    int_t bitRev(int_t x, int_t size2)
    {
        int_t result = 0;
        for (int_t i = 1; i < size2; i++)
        {
            result |= (x & 1);
            x >>= 1;
            result <<= 1;
        }
        return result | (x & 1);
    }
    int_t power(int_t base, int_t index)
    {
        base = (base % mod + mod) % mod;
        if (index < 0)
        {
            index *= -1;
            base = power(base, mod - 2);
        }
        int_t result = 1;
        while (index)
        {
            if (index & 1)
            {
                result = result * base % mod;
            }
            base = base * base % mod;
            index >>= 1;
        }
        return result;
    }

     

  • 洛谷4389 付公主的背包

    多项式指数函数的板子…

    大概就是n个物品的完全背包,求凑出来某个容量的方案数

    设第i个物品的体积是$a_i$,那么第i个物品的生成函数是$\frac 1 {1-x^{a_i}}$,分别表示取0,1,2,3,……….$\infty$个的方案数

    然后把所有物品的生成函数乘起来即可。

    直接暴力求逆计算的话,复杂度很容易被卡到$O(n^2)$,即使分治计算复杂度也是$O(nlog^2n)$,所以考虑多项式对数函数和指数函数

    $$
    \text{计算}F\left( x \right) =\prod_{1\le i\le n}{\frac{1}{1-x^{a_i}}}
    \\
    \text{先计算}\ln\text{\ }F\left( z \right) \equiv -\sum_{1\le i\le n}{\ln \left( 1-x^{a_i} \right) \}
    \\
    \text{麦克劳林展开}
    \\
    =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\frac{x^{a_ij}}{j}}}
    \\
    \text{整理}
    \\
    =\sum_{1\le i\le m}{x^i\times \frac{1}{i}\sum_{a_j|i}{a_i}}
    \\
    \text{设}f\left( i \right) =\frac{1}{i}\times \sum_{a_j|i}{a_j}
    \\
    \text{预处理出}f\left( i \right) ,\text{然后求出}\ln\text{\ }F\left( x \right) \text{,然后求其指数函数即可}
    \\
    \text{注意,如果存在容量相同的物品要注意把}a_j\text{变成}ka_j\text{,否则很容易卡成}O\left( n^2 \right) 
    $$
    
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <assert.h>
    #include <sstream>
    #include <vector>
    using int_t = long long int;
    using std::cin;
    using std::cout;
    using std::endl;
    
    const int_t mod = 998244353;
    const int_t g = 3;
    int_t power(int_t base, int_t index);
    int_t upper2n(int_t x);
    int_t bitReverse(int_t bits, int_t size2);
    template <int_t arg = 1>
    void transform(int_t *A, int_t size);
    void poly_inv(int_t *A, int_t *inv, int_t n);
    void poly_sqrt(int_t *A, int_t *result, int_t n);
    void poly_log(int_t *A, int_t n);
    void poly_exp(int_t *A, int_t *result, int_t n);
    const int_t LARGE = 1 << 21;
    std::string tostr(int_t *A, int_t size)
    {
        std::ostringstream oss;
        for (int_t i = 0; i < size; i++)
            oss << A[i] << " ";
        return oss.str();
    }
    int main()
    {
        int n, m;
        scanf("%d%d",&n,&m);
        static int_t A[LARGE];
        static int_t f[LARGE];
        static int_t result[LARGE];
        static int_t count[LARGE];
        std::vector<int_t> items;
    
        for (int_t i = 1; i <= n; i++)
        {
            int x;
            scanf("%d",&x);
            // cin >> x;
            items.push_back(x);
            count[x]++;
        }
        std::sort(items.begin(), items.end());
        items.resize(std::unique(items.begin(), items.end()) - items.begin());
        for (int_t x : items)
        {
            for (int_t i = 1; i * x <= m; i++)
            {
                f[i * x] = (f[i * x] + count[x] * x) % mod;
            }
        }
        for (int_t i = 1; i <= m; i++)
        {
            A[i] = power(i, -1) * f[i] % mod;
        }
        poly_exp(A, result, m + 1);
        for (int_t i = 1; i <= m; i++)
        {
            printf("%d\n",(int)result[i]);
        }
        return 0;
    }
    //多项式指数函数
    //计算e^{A(z)},结果存放在result中,对x^n取模
    void poly_exp(int_t *A, int_t *result, int_t n)
    {
        static int_t Ax[LARGE];
        static int_t logx[LARGE];
        if (n == 1)
        {
            assert(A[0] == 0);
            result[0] = 1;
            return;
        }
        poly_exp(A, result, n / 2 + n % 2);
        int_t size = upper2n(n * 2);
        for (int_t i = 0; i < size; i++)
        {
            Ax[i] = A[i];
            logx[i] = result[i];
            if (i >= n)
                Ax[i] = 0;
        }
        poly_log(logx, n);
        //需要使用到的多项式都必须要求值
        transform(Ax, size);
        transform(logx, size);
        transform(result, size);
        for (int_t i = 0; i < size; i++)
        {
            result[i] = (result[i] * (1 - logx[i] + Ax[i] + mod) % mod) % mod;
        }
        transform<-1>(result, size);
        for (int_t i = 0; i < size; i++)
        {
            result[i] = (result[i] * power(size, -1)) % mod;
            if (i >= n)
                result[i] = 0;
        }
    }
    //多项式对数函数,计算ln A(z),结果存放在A中
    //对x^n取模
    void poly_log(int_t *A, int_t n)
    {
        int_t size = upper2n(2 * n);
        static int_t inv[LARGE];
        std::fill(inv, inv + size, 0);
        poly_inv(A, inv, n);
        for (int_t i = 0; i < n; i++)
        {
            A[i] = (A[i + 1] * (i + 1)) % mod;
        }
        transform(A, size);
        transform(inv, size);
        for (int_t i = 0; i < size; i++)
        {
            A[i] = (A[i] * inv[i]) % mod;
        }
        transform<-1>(A, size);
        for (int_t i = n - 1; i >= 1; i--)
        {
            A[i] = A[i - 1] * power(i, -1) % mod * power(size, -1) % mod;
        }
        A[0] = 0;
    }
    //多项式开方
    //计算sqrt(A),结果存放在result中,系数对x^n取模
    //需要保证常数项是0或者1,这个函数不会计算二次剩余
    void poly_sqrt(int_t *A, int_t *result, int_t n)
    {
        static int_t Ax[LARGE];
        if (n == 1)
        {
            assert(A[0] == 1 || A[0] == 0);
            result[0] = A[0];
            return;
        }
        poly_sqrt(A, result, n / 2 + n % 2);
        int_t size = upper2n(3 * n - 1);
        for (int_t i = 0; i < size; i++)
        {
            Ax[i] = A[i];
            if (i >= n)
                Ax[i] = 0;
        }
        static int_t inv[LARGE];
        std::fill(inv, inv + size, 0);
        poly_inv(result, inv, n);
        for (int_t i = 0; i < size; i++)
        {
            inv[i] = (inv[i] * power(2, -1)) % mod;
        }
        transform(result, size);
        transform(Ax, size);
        transform(inv, size);
        for (int_t i = 0; i < size; i++)
        {
            result[i] = (result[i] - (result[i] * result[i] % mod - Ax[i] + mod) % mod * inv[i] % mod + mod) % mod;
        }
        transform<-1>(result, size);
        for (int_t i = 0; i < size; i++)
        {
            if (i < n)
            {
                result[i] = (result[i] * power(size, -1)) % mod;
            }
            else
            {
                result[i] = 0;
            }
        }
    }
    //多项式求逆
    //计算A^{-1}(z),结果存放在inv中,对x^n取模
    void poly_inv(int_t *A, int_t *inv, int_t n)
    {
        static int_t Ax[LARGE];
        if (n == 1)
        {
            inv[0] = power(A[0], -1);
            return;
        }
        poly_inv(A, inv, n / 2 + n % 2);
        int_t size = upper2n(n * 3 - 1);
        //一个坑,注意每次弄完后要把Ax中次数大等于n的项清零
        for (int_t i = 0; i < size; i++)
        {
    
            if (i < n)
            {
                Ax[i] = A[i];
            }
            else
            {
                Ax[i] = 0;
            }
        }
        //C(x)<-2B(x)-B^2(x)A(x)
    
        transform(inv, size);
        transform(Ax, size);
        for (int_t i = 0; i < size; i++)
        {
            inv[i] = (2 * inv[i] - inv[i] * inv[i] % mod * Ax[i] % mod + mod) % mod;
        }
        transform<-1>(inv, size);
        for (int_t i = 0; i < n; i++)
        {
            inv[i] = (inv[i] * power(size, -1)) % mod;
        }
        for (int_t i = n; i < size; i++)
        {
            inv[i] = 0;
        }
    }
    //NTT
    template <int_t arg = 1>
    void transform(int_t *A, int_t size)
    {
        int_t size2 = log2(size);
        for (int_t i = 0; i < size; i++)
        {
            int_t x = bitReverse(i, size2);
            if (x > i)
            {
                std::swap(A[i], A[x]);
            }
        }
        for (int_t i = 2; i <= size; i *= 2)
        {
            int_t mr = power(g, arg * (mod - 1) / i);
            for (int_t j = 0; j < size; j += i)
            {
                int_t curr = 1;
                for (int_t k = 0; k < i / 2; k++)
                {
                    int_t u = A[j + k];
                    int_t t = A[j + k + i / 2] * curr % mod;
                    A[j + k] = (u + t) % mod;
                    A[j + k + i / 2] = (u - t + mod) % mod;
                    curr = (curr * mr) % mod;
                }
            }
        }
    }
    
    int_t bitReverse(int_t bits, int_t size2)
    {
        int_t result = 0;
        for (int_t i = 1; i < size2; i++)
        {
            result |= (bits & 1);
            result <<= 1;
            bits >>= 1;
        }
        return result | (bits & 1);
    }
    int_t upper2n(int_t x)
    {
        int_t result = 1;
        while (result < x)
            result *= 2;
        return result;
    }
    int_t power(int_t base, int_t index)
    {
        int_t result = 1;
        if (index < 0)
        {
            index *= -1;
            base = power(base, mod - 2);
        }
        while (index)
        {
            if (index & 1)
            {
                result = (result * base) % mod;
            }
            index >>= 1;
            base = (base * base) % mod;
        }
        return result;
    }

    多项式板子粘贴自https://yutong.site/?p=691

  • 第二类斯特林数的一些小东西…

    考生物时闲得无聊推的qwq..

    $$\left( \text{考生物时无聊推的}.. \right) \\\text{设}S_2\left( n,k \right) \text{表示把}n\text{个元素划分成}k\text{个集合的方案数}\\\text{则有}\\m^n=\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) S_2\left( n,i \right) i!}\\\text{解释:枚举不为空的集合的数量,乘上把}n\text{个元素划分成}i\text{个集合的方案数,再乘上集合的数量(因为集合有序)}\\\text{设}f\left( m \right) =m^n,g\left( i \right) =S_2\left( n,i \right) i!\\\text{则有}f\left( m \right) =\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) g\left( i \right)}\\\text{二项式反演可得}\\g\left( m \right) =\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) \left( -1 \right) ^{m-i}f\left( i \right)}\\\text{代入}\\S_2\left( n,m \right) \times m!=\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) \times \left( -1 \right) ^{m-i}\times i^n}\\\text{整理一下}\\S_2\left( n,m \right) =\frac{1}{m!}\sum_{0\le i\le m}{\left( \begin{array}{c} m\\ i\\\end{array} \right) \times \left( -1 \right) ^{m-i}\times i^n}\\\text{这是斯特林数的通项}\\\text{再整理一下,展开}\left( \begin{array}{c} m\\ i\\\end{array} \right) \\S_2\left( n,m \right) =\frac{1}{m!}\sum_{0\le i\le m}{\frac{m!}{i!\times \left( m-i \right) !}\times \left( -1 \right) ^{m-i}\times i^n}\\=\sum_{0\le i\le m}{\frac{i^n\times \left( -1 \right) ^{m-i}}{i!\times \left( m-i \right) !}}\\\text{然后发现这个式子可以卷积}…\\\text{设}A\left( x \right) =\sum_{0\le i\le m}{x^iS_2\left( n,i \right) =\sum_{0\le i\le m}{x^i\sum_{0\le j\le i}{\frac{j^n}{j!}\times \frac{\left( -1 \right) ^{i-j}}{\left( i-j \right) !}}}}\\\text{构造两个}m\text{次多项式}\\B\left( x \right) =\sum_{0\le i\le m}{\frac{i^n}{i!}x^i}\\C\left( x \right) =\sum_{0\le i\le m}{\frac{\left( -1 \right) ^i}{i!}x^i}\\B\left( x \right) C\left( x \right) \text{的}i\text{次项前的系数即为}S_2\left( n,i \right) $$

  • 多项式相关板子

    包括NTT,多项式求逆,多项式开方,多项式对数函数,多项式指数函数.

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <assert.h>
    #include <sstream>
    using int_t = long long int;
    using std::cin;
    using std::cout;
    using std::endl;
    
    const int_t mod = 998244353;
    const int_t g = 3;
    int_t power(int_t base, int_t index);
    int_t upper2n(int_t x);
    int_t bitReverse(int_t bits, int_t size2);
    template <int_t arg = 1>
    void transform(int_t *A, int_t size);
    void poly_inv(int_t *A, int_t *inv, int_t n);
    void poly_sqrt(int_t *A, int_t *result, int_t n);
    void poly_log(int_t *A, int_t n);
    void poly_exp(int_t *A, int_t *result, int_t n);
    const int_t LARGE = 1 << 21;
    std::string tostr(int_t *A, int_t size)
    {
        std::ostringstream oss;
        for (int_t i = 0; i < size; i++)
            oss << A[i] << " ";
        return oss.str();
    }
    int main()
    {
        static int_t A[LARGE];
        static int_t result[LARGE];
        int_t n;
        scanf("%lld", &n);
        for (int_t i = 0; i < n; i++)
            scanf("%lld", &A[i]);
        for (int_t i = 0; i < n; i++)
        {
            printf("%d ", (int)(result[i]));
        }
        return 0;
    }
    //多项式指数函数
    //计算e^{A(z)},结果存放在result中,对x^n取模
    void poly_exp(int_t *A, int_t *result, int_t n)
    {
        static int_t Ax[LARGE];
        static int_t logx[LARGE];
        if (n == 1)
        {
            assert(A[0] == 0);
            result[0] = 1;
            return;
        }
        poly_exp(A, result, n / 2 + n % 2);
        int_t size = upper2n(n * 2);
        for (int_t i = 0; i < size; i++)
        {
            Ax[i] = A[i];
            logx[i] = result[i];
            if (i >= n)
                Ax[i] = 0;
        }
        poly_log(logx, n);
        //需要使用到的多项式都必须要求值
        transform(Ax, size);
        transform(logx, size);
        transform(result, size);
        for (int_t i = 0; i < size; i++)
        {
            result[i] = (result[i] * (1 - logx[i] + Ax[i] + mod) % mod) % mod;
        }
        transform<-1>(result, size);
        for (int_t i = 0; i < size; i++)
        {
            result[i] = (result[i] * power(size, -1)) % mod;
            if (i >= n)
                result[i] = 0;
        }
    }
    //多项式对数函数,计算ln A(z),结果存放在A中
    //对x^n取模
    void poly_log(int_t *A, int_t n)
    {
        int_t size = upper2n(2 * n);
        static int_t inv[LARGE];
        std::fill(inv, inv + size, 0);
        poly_inv(A, inv, n);
        for (int_t i = 0; i < n; i++)
        {
            A[i] = (A[i + 1] * (i + 1)) % mod;
        }
        transform(A, size);
        transform(inv, size);
        for (int_t i = 0; i < size; i++)
        {
            A[i] = (A[i] * inv[i]) % mod;
        }
        transform<-1>(A, size);
        for (int_t i = n - 1; i >= 1; i--)
        {
            A[i] = A[i - 1] * power(i, -1) % mod * power(size, -1) % mod;
        }
        A[0] = 0;
    }
    //多项式开方
    //计算sqrt(A),结果存放在result中,系数对x^n取模
    //需要保证常数项是0或者1,这个函数不会计算二次剩余
    void poly_sqrt(int_t *A, int_t *result, int_t n)
    {
        static int_t Ax[LARGE];
        if (n == 1)
        {
            assert(A[0] == 1 || A[0] == 0);
            result[0] = A[0];
            return;
        }
        poly_sqrt(A, result, n / 2 + n % 2);
        int_t size = upper2n(3 * n - 1);
        for (int_t i = 0; i < size; i++)
        {
            Ax[i] = A[i];
            if (i >= n)
                Ax[i] = 0;
        }
        static int_t inv[LARGE];
        std::fill(inv, inv + size, 0);
        poly_inv(result, inv, n);
        for (int_t i = 0; i < size; i++)
        {
            inv[i] = (inv[i] * power(2, -1)) % mod;
        }
        transform(result, size);
        transform(Ax, size);
        transform(inv, size);
        for (int_t i = 0; i < size; i++)
        {
            result[i] = (result[i] - (result[i] * result[i] % mod - Ax[i] + mod) % mod * inv[i] % mod + mod) % mod;
        }
        transform<-1>(result, size);
        for (int_t i = 0; i < size; i++)
        {
            if (i < n)
            {
                result[i] = (result[i] * power(size, -1)) % mod;
            }
            else
            {
                result[i] = 0;
            }
        }
    }
    //多项式求逆
    //计算A^{-1}(z),结果存放在inv中,对x^n取模
    void poly_inv(int_t *A, int_t *inv, int_t n)
    {
        static int_t Ax[LARGE];
        if (n == 1)
        {
            inv[0] = power(A[0], -1);
            return;
        }
        poly_inv(A, inv, n / 2 + n % 2);
        int_t size = upper2n(n * 3 - 1);
        //一个坑,注意每次弄完后要把Ax中次数大等于n的项清零
        for (int_t i = 0; i < size; i++)
        {
    
            if (i < n)
            {
                Ax[i] = A[i];
            }
            else
            {
                Ax[i] = 0;
            }
        }
        //C(x)<-2B(x)-B^2(x)A(x)
    
        transform(inv, size);
        transform(Ax, size);
        for (int_t i = 0; i < size; i++)
        {
            inv[i] = (2 * inv[i] - inv[i] * inv[i] % mod * Ax[i] % mod + mod) % mod;
        }
        transform<-1>(inv, size);
        for (int_t i = 0; i < n; i++)
        {
            inv[i] = (inv[i] * power(size, -1)) % mod;
        }
        for (int_t i = n; i < size; i++)
        {
            inv[i] = 0;
        }
    }
    //NTT
    template <int_t arg = 1>
    void transform(int_t *A, int_t size)
    {
        int_t size2 = log2(size);
        for (int_t i = 0; i < size; i++)
        {
            int_t x = bitReverse(i, size2);
            if (x > i)
            {
                std::swap(A[i], A[x]);
            }
        }
        for (int_t i = 2; i <= size; i *= 2)
        {
            int_t mr = power(g, arg * (mod - 1) / i);
            for (int_t j = 0; j < size; j += i)
            {
                int_t curr = 1;
                for (int_t k = 0; k < i / 2; k++)
                {
                    int_t u = A[j + k];
                    int_t t = A[j + k + i / 2] * curr % mod;
                    A[j + k] = (u + t) % mod;
                    A[j + k + i / 2] = (u - t + mod) % mod;
                    curr = (curr * mr) % mod;
                }
            }
        }
    }
    
    int_t bitReverse(int_t bits, int_t size2)
    {
        int_t result = 0;
        for (int_t i = 1; i < size2; i++)
        {
            result |= (bits & 1);
            result <<= 1;
            bits >>= 1;
        }
        return result | (bits & 1);
    }
    int_t upper2n(int_t x)
    {
        int_t result = 1;
        while (result < x)
            result *= 2;
        return result;
    }
    int_t power(int_t base, int_t index)
    {
        int_t result = 1;
        if (index < 0)
        {
            index *= -1;
            base = power(base, mod - 2);
        }
        while (index)
        {
            if (index & 1)
            {
                result = (result * base) % mod;
            }
            index >>= 1;
            base = (base * base) % mod;
        }
        return result;
    }

     

  • CF438E 多项式开根 多项式牛顿迭代

    多项式真好玩qwq.jpg

    $$\text{显然满足权值为}S\text{的二叉树的个数是有限的}\\\text{设}T\left( z \right) =\sum_{s\in \left\{ c_i \right\}}{z^s}\text{,即如果集合}\left\{ c_i \right\} \text{中存在元素}x,\text{那么}T\left( z \right) \text{中就存在项}z^x\\\text{设}G\left( z \right) \text{表示一棵有根二叉树的方案数的生成函数,其中}G^{\left[ i \right]}\left( z \right) \text{为权值为}i\text{的二叉树的数目}\\\text{则有递归}\\G\left( z \right) =1+T\left( z \right) G^2\left( z \right) \\\text{其中1表示这是棵空树,非空情况下,}T\left( z \right) \text{表示树根的取值,而}G^2\left( z \right) \text{表示两棵子树的取值}\\\text{解方程}\\T\left( z \right) G^2\left( z \right) -G\left( z \right) +1=0\\G\left( z \right) =\frac{1\pm \sqrt{1-4T\left( z \right)}}{2T\left( z \right)}\\\text{因为}G\left( 0 \right) =\text{1,所以}G\left( z \right) =\frac{1+\sqrt{1-4T\left( z \right)}}{2T\left( z \right)}\\\text{因为}T\left( z \right) \text{的常数项为0,不能求逆,所以我们变一下形}\\G\left( z \right) =\frac{\left( 1+\sqrt{1-4T\left( z \right)} \right) \left( 1-\sqrt{1-4T\left( z \right)} \right)}{2T\left( z \right) \left( 1-\sqrt{1-4T\left( z \right)} \right)}=\frac{2}{1-\sqrt{1-4T\left( z \right)}}\\\text{我们需要做的只剩下多项式开根和求逆了}\\\\\text{多项式开根与牛顿迭代:}\\\text{设}F\left( X\left( z \right) \right) =X^2\left( z \right) -A\left( z \right) \\\text{要计算}\sqrt{A\left( z \right)}\text{,等价于解方程}F\left( X\left( z \right) \right) \equiv \text{0\ }mod\ z^n\\n=\text{1时,}X\left( z \right) \equiv \sqrt{A^{\left[ 0 \right]}\left( z \right)}\\n\ge \text{2时,考虑倍增}\\\text{假设已经计算出了}X_0\left( z \right) ,\text{使得}G\left( X_0\left( z \right) \right) \equiv \text{0\ }mod\ z^{\lceil \left. \frac{n}{2} \rceil \right.}\\\text{现在要求}G\left( X_1\left( z \right) \right) \equiv \text{0\ }mod\ z^n\\\text{将}G\left( X\left( z \right) \right) \text{在}X\left( z \right) =X_0\left( z \right) \text{处泰勒展开}\\G\left( X_1\left( z \right) \right) \equiv \sum_{i\ge 0}{\frac{\left( X_1\left( z \right) -X_0\left( z \right) \right) ^i}{i!}G^{\left( i \right)}\left( X_0\left( z \right) \right)}\ \\\equiv G\left( X_0\left( z \right) \right) +\left( X_1\left( z \right) -X_0\left( z \right) \right) G`\left( X_0\left( z \right) \right) +\sum_{i\ge 2}{\frac{\left( X_1\left( z \right) -X_0\left( z \right) \right) ^i}{i!}G^{\left( i \right)}\left( X_0\left( z \right) \right)}\\\text{因为}X_1\left( z \right) \text{与}X_0\left( z \right) \text{的低}\lceil \frac{n}{2} \rceil \text{次项相同,所以}X_1\left( z \right) -X_0\left( z \right) \text{的不为0的次数最低的项不会小于}\lceil \frac{n}{2} \rceil \\\therefore \left( X_1\left( z \right) -X_0\left( z \right) \right) ^i\left( i\ge 2 \right) \text{的次数最低的项不会小于}n\\\therefore \left( X_1\left( z \right) -X_0\left( z \right) \right) ^i\equiv \text{0\ }\left( mod\ z^n \right) \left( i\ge 2 \right) \\\therefore G\left( X_1\left( z \right) \right) \equiv G\left( X_0\left( z \right) \right) +\left( X_1\left( z \right) -X_0\left( z \right) \right) G`\left( X_0\left( z \right) \right) \equiv \text{0\ }\left( mod\ z^n \right) \\\text{整理一下}G\left( X_0\left( z \right) \right) +X_1\left( z \right) G`\left( X_0\left( z \right) \right) -X_0\left( z \right) G`\left( X_0\left( z \right) \right) \equiv \text{0\ }\left( mod\ z^n \right) \\\text{整理出}X_1\left( z \right) \\X_1\left( z \right) \equiv X_0\left( z \right) -\frac{G\left( X_0\left( z \right) \right)}{G`\left( X_0\left( z \right) \right)}\ \left( mod\ z^n \right) \\\text{在计算}\sqrt{A\left( z \right)}\text{的情况下,}G\left( X_0\left( z \right) \right) =X_{0}^{2}\left( z \right) -A\left( z \right) \\G`\left( X\left( z \right) \right) \equiv 2X\left( z \right) \\X_1\left( z \right) \equiv X_0\left( z \right) -\frac{X_{0}^{2}\left( z \right) -A\left( z \right)}{2X_0\left( z \right)}\ \left( mod\ z^n \right) \\$$

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <assert.h>
    #include <sstream>
    using int_t = long long int;
    using std::cin;
    using std::cout;
    using std::endl;
    
    const int_t mod = 998244353;
    const int_t g = 3;
    int_t power(int_t base, int_t index);
    int_t upper2n(int_t x);
    int_t bitReverse(int_t bits, int_t size2);
    template <int_t arg = 1>
    void transform(int_t *A, int_t size);
    void poly_inv(int_t *A, int_t *inv, int_t n);
    void poly_sqrt(int_t *A, int_t *result, int_t n);
    const int_t LARGE = 1 << 21;
    std::string tostr(int_t *A, int_t size)
    {
        std::ostringstream oss;
        for (int_t i = 0; i < size; i++)
            oss << A[i] << " ";
        return oss.str();
    }
    int main()
    {
        static int_t T[LARGE];
        static int_t Tsqrt[LARGE];
        static int_t Tinv[LARGE];
        static int_t result[LARGE];
        int_t n, m;
        scanf("%lld%lld", &n, &m);
        int_t size = upper2n(2 * m + 1);
        {
            for (int_t i = 1; i <= n; i++)
            {
                int_t x;
                scanf("%lld", &x);
                T[x] = 1;
            }
            // cout << "T=" << tostr(T, size) << endl;
        }
    
        {
            for (int_t i = 0; i <= m; i++)
            {
                T[i] = (-4 * T[i] + mod) % mod;
            }
            T[0] = 1;
            poly_sqrt(T, Tsqrt, m + 1);
            Tsqrt[0] = (Tsqrt[0] + 1);
            poly_inv(Tsqrt, result, m + 1);
        }
        for (int_t i = 1; i <= m; i++)
        {
            printf("%d\n", (int)(result[i] * 2 % mod));
        }
        return 0;
    }
    void poly_sqrt(int_t *A, int_t *result, int_t n)
    {
        static int_t Ax[LARGE];
        if (n == 1)
        {
            assert(A[0] == 1 || A[0] == 0);
            result[0] = A[0];
            return;
        }
        poly_sqrt(A, result, n / 2 + n % 2);
        int_t size = upper2n(3 * n - 1);
        for (int_t i = 0; i < size; i++)
        {
            Ax[i] = A[i];
            if (i >= n)
                Ax[i] = 0;
        }
        static int_t inv[LARGE];
        std::fill(inv, inv + size, 0);
        poly_inv(result, inv, n);
        for (int_t i = 0; i < size; i++)
        {
            inv[i] = (inv[i] * power(2, -1)) % mod;
        }
        transform(result, size);
        transform(Ax, size);
        transform(inv, size);
        for (int_t i = 0; i < size; i++)
        {
            result[i] = (result[i] - (result[i] * result[i] % mod - Ax[i] + mod) % mod * inv[i] % mod + mod) % mod;
        }
        transform<-1>(result, size);
        for (int_t i = 0; i < size; i++)
        {
            if (i < n)
            {
                result[i] = (result[i] * power(size, -1)) % mod;
            }
            else
            {
                result[i] = 0;
            }
        }
        // cout << "sqrt mod x^" << n << " = ";
        // for (int_t i = 0; i < size; i++)
        // cout << result[i] << " ";
        // cout << endl;
    }
    void poly_inv(int_t *A, int_t *inv, int_t n)
    {
        static int_t Ax[LARGE];
        if (n == 1)
        {
            inv[0] = power(A[0], -1);
            return;
        }
        poly_inv(A, inv, n / 2 + n % 2);
        int_t size = upper2n(n * 3 - 1);
        //一个坑,注意每次弄完后要把Ax中次数大等于n的项清零
        for (int_t i = 0; i < size; i++)
        {
    
            if (i < n)
            {
                Ax[i] = A[i];
            }
            else
            {
                Ax[i] = 0;
            }
        }
        //C(x)<-2B(x)-B^2(x)A(x)
    
        transform(inv, size);
        transform(Ax, size);
        for (int_t i = 0; i < size; i++)
        {
            inv[i] = (2 * inv[i] - inv[i] * inv[i] % mod * Ax[i] % mod + mod) % mod;
        }
        transform<-1>(inv, size);
        for (int_t i = 0; i < n; i++)
        {
            inv[i] = (inv[i] * power(size, -1)) % mod;
        }
        for (int_t i = n; i < size; i++)
        {
            inv[i] = 0;
        }
    }
    
    template <int_t arg = 1>
    void transform(int_t *A, int_t size)
    {
        int_t size2 = log2(size);
        for (int_t i = 0; i < size; i++)
        {
            int_t x = bitReverse(i, size2);
            if (x > i)
            {
                std::swap(A[i], A[x]);
            }
        }
        for (int_t i = 2; i <= size; i *= 2)
        {
            int_t mr = power(g, arg * (mod - 1) / i);
            for (int_t j = 0; j < size; j += i)
            {
                int_t curr = 1;
                for (int_t k = 0; k < i / 2; k++)
                {
                    int_t u = A[j + k];
                    int_t t = A[j + k + i / 2] * curr % mod;
                    A[j + k] = (u + t) % mod;
                    A[j + k + i / 2] = (u - t + mod) % mod;
                    curr = (curr * mr) % mod;
                }
            }
        }
    }
    
    int_t bitReverse(int_t bits, int_t size2)
    {
        int_t result = 0;
        for (int_t i = 1; i < size2; i++)
        {
            result |= (bits & 1);
            result <<= 1;
            bits >>= 1;
        }
        return result | (bits & 1);
    }
    int_t upper2n(int_t x)
    {
        int_t result = 1;
        while (result < x)
            result *= 2;
        return result;
    }
    int_t power(int_t base, int_t index)
    {
        int_t result = 1;
        if (index < 0)
        {
            index *= -1;
            base = power(base, mod - 2);
        }
        while (index)
        {
            if (index & 1)
            {
                result = (result * base) % mod;
            }
            index >>= 1;
            base = (base * base) % mod;
        }
        return result;
    }