Ural 1560 牛顿恒等式 + 线段树

题意

传送门 Ural 1560 Elementary Symmetric Functions

题解

根据牛顿恒等式
∑ i = 1 k S i b k − i + k × b k = 0 , k ∈ N + \sum\limits_{i=1}^{k} S_ib_{k-i} + k\times b_k = 0, k\in N^+ i=1∑k​Si​bk−i​+k×bk​=0,k∈N+ 其中 S k = ∑ l ≤ i ≤ r a i k S_k = \sum_{l\leq i\leq r} a_i^k Sk​=∑l≤i≤r​aik​，且 b k = ( − 1 ) k f k b_k = (-1)^kf_k bk​=(−1)kfk​
f k = ∑ l ≤ i 1 < ⋯ < i k ≤ r ( ∏ m = 1 k x i m ) f_k = \sum\limits_{l\leq i_1<\dots fk​=l≤i1​<⋯<ik​≤r∑​(m=1∏k​xim​​) 基本对称多项式 f f f 的边界情况 f 0 = 1 , f k = 0 ( k > r − l + 1 ) f_0 = 1, f_k = 0(k > r - l + 1) f0​=1,fk​=0(k>r−l+1)。

已知 k k k 次项求和结果，则可以递推出 f f f。

维护 k k k 棵线段树即可。

总时间复杂度 O ( k q log ⁡ n ) O(kq\log n) O(kqlogn)。

#include 
using namespace std;
using ll = long long;
constexpr int MAXN = 8E4 + 5, SZ = 1 << 18;
int N, M, P;
ll A[MAXN];

struct ST
{
    int lim;
    ll dat[SZ];
    void set(int x) { lim = x; }
    void init(int k = 0, int l = 0, int r = N)
    {
        if (r - l == 1)
        {
            ll t = 1;
            for (int i = 0; i < lim; ++i)
                t = t * A[l] % P;
            dat[k] = t;
            return;
        }
        int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
        init(chl, l, m), init(chr, m, r);
        dat[k] = (dat[chl] + dat[chr]) % P;
    }
    void change(int a, int b, ll x, int k = 0, int l = 0, int r = N)
    {
        if (r <= a || b <= l)
            return;
        if (a <= l && r <= b)
        {
            ll t = 1;
            for (int i = 0; i < lim; ++i)
                t = t * x % P;
            dat[k] = t;
            return;
        }
        int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
        change(a, b, x, chl, l, m), change(a, b, x, chr, m, r);
        dat[k] = (dat[chl] + dat[chr]) % P;
    }
    ll ask(int a, int b, int k = 0, int l = 0, int r = N)
    {
        if (a <= l && r <= b)
            return dat[k];
        int m = (l + r) / 2, chl = k * 2 + 1, chr = k * 2 + 2;
        if (b <= m)
            return ask(a, b, chl, l, m);
        else if (m <= a)
            return ask(a, b, chr, m, r);
        return (ask(a, b, chl, l, m) + ask(a, b, chr, m, r)) % P;
    }
} tr[4];

ll inv(ll x)
{
    ll res = 1, n = P - 2, mod = P;
    while (n > 0)
    {
        if (n & 1)
            res = res * x % mod;
        x = x * x % mod, n >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M >> P;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    for (int i = 0; i < 4; ++i)
    {
        tr[i].set(i + 1);
        tr[i].init();
    }
    while (M--)
    {
        char op;
        cin >> op;
        if (op == 'I')
        {
            int p, d;
            cin >> p >> d;
            --p;
            A[p] = (A[p] + d) % P;
            for (int i = 0; i < 4; ++i)
                tr[i].change(p, p + 1, A[p]);
        }
        else
        {
            int l, r, lim;
            cin >> l >> r >> lim;
            --l;
            vector<ll> s(lim + 1), f(lim + 1);
            for (int i = 0; i < lim; ++i)
                s[i + 1] = tr[i].ask(l, r);
            f[0] = 1;
            ll mod = P;
            for (int k = 1; k <= lim; ++k)
            {
                ll sum = 0;
                for (int i = 1; i <= k; ++i)
                {
                    ll d = s[i] * f[k - i] % mod;
                    if ((k - i) & 1)
                        d = mod - d;
                    sum += d;
                }
                if ((k + 1) & 1)
                    sum = mod - sum;
                sum = sum % mod * inv(k) % mod;
                f[k] = (sum + mod) % mod;
            }
            for (int i = 0; i <= lim; ++i)
                cout << f[i] << (i == lim ? '\n' : ' ');
        }
    }
    return 0;
}