2022-9-26总结

Sasha and a Very Easy Test

原题 CF1109E

因为模数 $P$ 不一定是质数，可能不存在逆元，所以除法比较难搞。

考虑一个数只有与模数 $P$ 不互质时才没有逆元，我们可以考虑将 $P$ 质因数分解，并把操作的每一个数都分离出 $P$ 的因子来。

这样一个数被分成两部分：与 $P$ 互质的部分 和 与 $P$ 不互质的部分。

互质的部分就直接乘逆元就行了，不互质的部分可以记录一个数所含 $P$ 的每个质因子的指数，将这两部分乘起来就可以得到原数，除法的话直接指数相减再更新答案就没事了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 5e5+15;

struct type {
    int cnt[10];
    ll mul;
    type()
    {
        memset(cnt, 0, sizeof(cnt));
        mul = 1;
    }
};

namespace tree {
    struct node {
        int l, r;
        ll sum;
        type lz;
    } a[N*4];
    ll val[N];
    void build(int l, int r, int i = 1);
    void modify(int ql, int qr, type &tmp, int i = 1);
    void div(int pos, type &tmp, int i = 1);
    ll query(int ql, int qr ,int i = 1);
}
using namespace tree;

int n, P, q;
int data[N];
int p[10], tot;
int pow_v[10][N*20];

void divide();
void prework_pow();
ll get_pow(int i, int j);

signed main()
{
    cin >> n >> P;
    for(int i = 1; i <= n; i++)
        cin >> data[i];
    divide();
    prework_pow();
    tree::build(1, n);
    cin >> q;
    int opt, l, r, x;
    for(int i = 1; i <= q; i++)
    {
        cin >> opt;
        if(opt == 1)
        {
            cin >> l >> r >> x;
            type tmp;
            for(int j = 1; j <= tot; j++)
                while(x%p[j] == 0)
                    x /= p[j], tmp.cnt[j]++;
            tmp.mul = x;
            tree::modify(l, r, tmp);
        }
        else if(opt == 2)
        {
            cin >> l >> x;
            type tmp;
            for(int j = 1; j <= tot; j++)
                while(x%p[j] == 0)
                    x /= p[j], tmp.cnt[j]++;
            tmp.mul = x;
            tree::div(l, tmp);
        }
        else if(opt == 3)
        {
            cin >> l >> r;
            cout << tree::query(l, r) << "\n";
        }
    }
}

void divide()
{
    int tmp = P;
    for(int i = 2; (ll)i*i <= tmp; i++)
    {
        if(tmp%i == 0)
        {
            p[++tot] = i;
            while(tmp%i == 0) tmp /= i;
        }
    }
    if(tmp != 1) p[++tot] = tmp;
}
void prework_pow()
{
    for(int i = 1; i <= tot; i++)
    {
        pow_v[i][0] = 1;
        for(int j = 1; j < N*20; j++)
            pow_v[i][j] = (ll)pow_v[i][j-1]*p[i]%P;
    }
}
ll get_pow(int i, int j)
{
//    ll ans = 1, a = p[i];
//    for(; j; j >>= 1, a = a*a%P)
//        if(j&1) ans = ans*a%P;
//    return ans;
    return pow_v[i][j];
}

namespace tree {
    #define ls (i<<1)
    #define rs (i<<1|1)
    ll exgcd(ll a, ll b, ll &x, ll &y)
    {
        if(!b) return x = 1, y = 0, b;
        ll d = exgcd(b, a%b, y, x);
        y -= (a/b)*x;
        return d;
    }
    ll inv(ll a, ll p)
    {
        ll x, y;
        exgcd(a, p, x, y);
        x = (x%p+p)%p;
        return x;
    }
    void modify(node &i, type &tmp)
    {
        (i.sum *= tmp.mul) %= P;
        (i.lz.mul *= tmp.mul) %= P;
        if(i.l == i.r)
            (val[i.l] *= tmp.mul) %= P;
        for(int j = 1; j <= tot; j++)
        {
            i.lz.cnt[j] += tmp.cnt[j];
            (i.sum *= get_pow(j,tmp.cnt[j])) %= P;
        }
    }
    void push_up(int i)
    {
        a[i].sum = (a[ls].sum + a[rs].sum)%P;
    }
    void push_down(int i)
    {
        modify(a[ls], a[i].lz);
        modify(a[rs], a[i].lz);
        memset(a[i].lz.cnt, 0, sizeof(a[i].lz.cnt));
        a[i].lz.mul = 1;
    }
    void build(int l, int r, int i)
    {
        a[i].l = l, a[i].r = r;
        if(l == r)
        {
            int x = data[l];
            for(int j = 1; j <= tot; j++)
            {
                int cnt = 0;
                while(x%p[j] == 0)
                    x /= p[j], cnt++;
                a[i].lz.cnt[j] = cnt;
            }
            val[l] = x;
            a[i].sum = data[l]%P;
            return void();
        }
        int mid = (l+r)>>1;
        build(l, mid, ls);
        build(mid+1, r, rs);
        push_up(i);
    }
    void modify(int ql, int qr, type &tmp, int i)
    {
        if(ql <= a[i].l && a[i].r <= qr)
            return modify(a[i], tmp);
        push_down(i);
        if(ql <= a[ls].r) modify(ql, qr, tmp, ls);
        if(qr >= a[rs].l) modify(ql, qr, tmp, rs);
        push_up(i);
    }
    void div(int pos, type &tmp, int i)
    {
        if(a[i].l == a[i].r)
        {
            (val[a[i].l] *= inv(tmp.mul, P)) %= P;
            a[i].sum = val[a[i].l];
            for(int j = 1; j <= tot; j++)
            {
                a[i].lz.cnt[j] -= tmp.cnt[j];
                (a[i].sum *= get_pow(j,a[i].lz.cnt[j])) %= P;
            }
            return void();
        }
        push_down(i);
        if(pos <= a[ls].r) div(pos, tmp, ls);
        if(pos >= a[rs].l) div(pos, tmp, rs);
        push_up(i);
    }
    ll query(int ql, int qr, int i)
    {
        if(ql <= a[i].l and a[i].r <= qr)
            return a[i].sum;
        push_down(i); ll ans = 0;
        if(ql <= a[ls].r) ans += query(ql, qr, ls);
        if(qr >= a[rs].l) ans += query(ql, qr, rs);
        return ans%P;
    }
}

Squirrel Migration

原题 AT3728

考虑每一条边的最大贡献。

对于树上的一条边，把它切断树会分成 $S_1$ 和 $S_2$ 两个联通块，设 $|S_1| < |S_2|$。

那么这一条边最多被经过 $2|S_1|$ 次。

此时有 $\forall x \in S_1, p_x \in S_2$。

考虑将重心 $G$ 作为根，那么现在的每一个 $S_1$ 都是 $G$ 的一棵子树，那么使得权值最大的条件即为 $\forall x \in subtree(y), p_x \not \in subtree(y)$。

现在有了结论，就可以容斥求答案了。

设 $f(i)$ 表示至少有 $i$ 个点的 $p_x$ 属于 $i$ 所在子树的答案，则题目所求为 $\sum\limits _{i=1}^{n} (-1)^i*f(i)*(n-i)!$

单独考虑每一个子树 $subtree(y)$，设其子树大小为 $siz(y)$，则在这个子树中 $f(i) = \binom{x}{i}^2*i!$。

最终以 $G$ 为根的 $f$ 就是把所有子树使用背包合并起来，时间复杂度 $O(n^2)$。

考虑到这个子树背包的形式与多项式乘法一样，我们可以将每个子树的 $f$ 看成一个多项式，每次选出两个长度最短的多项式相乘，因为所有多项式的总长度为 $n$，所以时间复杂度是 $O(n \log^2 n)$ 的。(有点类似于启发式合并)。

当然 AtCoder 上的原题中模数是 $10^9+7$，所以用不了 NTT。

#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
 
namespace polynomial {
    typedef long long ll;
    const int P = 998244353;
    const int g = 3, gi = 332748118;
    int lim, bit;
    vector<int> r;
    struct poly : vector<ll> {
        poly() {};
        poly(ll a)
        {
            resize(1);
            (*this)[0] = (a%P+P)%P;
        }
        poly& modx(int n)
        {
            resize(n);
            return *this;
        }
    };
    inline ll qpow(ll a, ll b, ll p = P)
    {
        ll ans = 1;
        for(; b; b >>= 1, a = a*a%p)
            if(b&1) ans = ans*a%p;
        return ans;
    }
    inline void dnt_prework(int n)
    {
        lim = 1, bit = 0;
        while(lim < n+1) lim <<= 1, bit++;
        r.resize(lim);
        for(int i = 0; i < lim; i++)
            r[i] = (r[i>>1]>>1) | ((i&1)<<(bit-1));
    }
    inline void builtin_change(poly &a, bool type)
    {
        for(int i = 0; i < lim; i++)
            if(i < r[i]) swap(a[i], a[r[i]]);
        for(int mid = 1; mid < lim; mid <<= 1)
        {
            ll wn = qpow(type?g:gi, (P-1)/(mid<<1));
            for(int j = 0, k = 0; j < lim; j += (mid<<1), k = j)
            {
                for(ll w = 1; k < j+mid; k++, w = w*wn%P)
                {
                    ll x = a[k], y = w*a[k+mid]%P;
                    a[k] = (x+y)%P, a[k+mid] = (x-y+P)%P;
                }
            }
        }
    }
    inline void dnt(poly &a)
    {
        a.resize(lim);
        builtin_change(a, true);
    }
    inline void idnt(poly &a)
    {
        a.resize(lim);
        builtin_change(a, false);
        ll liminv = qpow(lim, P-2);
        for(int i = 0; i < lim; i++)
            a[i] = a[i]*liminv%P;
    }
     
    inline poly operator + (const poly &a, const poly &b)
    {
        poly c = a;
        if(a.size() < b.size()) c.resize(b.size());
        for(int i = 0; i < b.size(); i++)
            c[i] = (c[i]+b[i])%P;
        return c;
    }
    inline poly operator - (const poly &a, const poly &b)
    {
        poly c = a;
        if(a.size() < b.size()) c.resize(b.size());
        for(int i = 0; i < b.size(); i++)
            c[i] = (c[i]-b[i]+P)%P;
        return c;
    }
    poly operator * (poly a, poly b)
    {
        int len = a.size()+b.size()-2;
        dnt_prework(len);
        poly ans; ans.resize(lim+1);
        dnt(a); dnt(b);
        for(int i = 0; i < lim; i++)
            ans[i] = a[i]*b[i]%P;
        idnt(ans);
        ans.resize(len+1);
        return ans;
    }
    inline poly operator * (poly a, const ll &k)
    {
        for(int i = 0; i < a.size(); i++)
            a[i] = a[i]*k%P;
        return a;
    }
     
    inline poly derivation(const poly &a)
    {
        poly b; b.resize(a.size()-1);
        for(int i = 1; i < a.size(); i++)
            b[i-1] = a[i]*i%P;
        return b;
    }
    inline poly integral(const poly &a)
    {
        poly b; b.resize(a.size()+1);
        for(int i = a.size()-1; i >= 1; i--)
            b[i] = a[i-1]*qpow(i, P-2)%P;
        return b;
    }
    inline poly inv(const poly &a)
    {
        stack<int> st;
        int n = a.size();
        while(n > 1) st.push(n), n = (n+1)/2;
        poly b = qpow(a[0], P-2);
        while(st.size())
        {
            n = st.top(); st.pop();
            poly c = a; c.modx(n); b.modx(n);
            b = (b*2-((c*b).modx(n)*b).modx(n)).modx(n);
        }
        return b.modx(a.size());
    }
    inline poly ln(const poly &a)
    {
        poly b, tmp;
        b = integral((derivation(a)*inv(a)));
        return b.modx(a.size());
    }
    inline poly sqrt(const poly &a)
    {
        stack<int> st;
        int n = a.size();
        while(n > 1) st.push(n), n = (n+1)/2;
        poly b = qpow(a[0], P-2);
        while(st.size())
        {
            n = st.top(); st.pop();
            poly c = a;
            c.modx(n); b.modx(n);
            b = ((c+(b*b).modx(n))*inv(b*2)).modx(n);
        }
        return b.modx(a.size());
    }
    inline poly exp(const poly &a)
    {
        stack<int> st;
        int n = a.size();
        while(n > 1) st.push(n), n = (n+1)/2;
        poly b = 1;
        while(st.size())
        {
            n = st.top(); st.pop();
            poly c = a;
            b.modx(n); c.modx(n);
            b = ((1-ln(b)+c)*b).modx(n);
        }
        return b.modx(a.size());
    }
    inline poly pow(const poly &a, const ll &k)
    {
        return exp(k*ln(a));
    }
}
using namespace polynomial;
 
typedef long long ll;
const int N = 1e5+10;
 
int n;
vector<int> ver[N];
int G, Gmx, siz[N];
ll fact[N], finv[N];
 
void fact_prework(int n);
void dfs(int x, int fa);
ll C(int n, int m);
 
bool operator < (const poly &a, const poly &b)
    { return a.size() < b.size(); }
 
int main()
{
    cin >> n;
    fact_prework(n);
    for(int i = 1; i < n; i++)
    {
        int a, b; cin >> a >> b;
        ver[a].push_back(b);
        ver[b].push_back(a);
    }
    Gmx = n; dfs(1, 0);
    dfs(G, 0);
     
     
    priority_queue<poly, vector<poly>, greater<poly>> q;
    poly f;
    for(auto y : ver[G])
    {
        f.resize(siz[y]+1); f[0] = 1;
        for(int i = 0; i <= siz[y]; i++)
            f[i] = C(siz[y],i)%P * C(siz[y],i)%P * fact[i]%P;
        q.push(f);
    }
     
    while(q.size() > 1)
    {
        poly a = q.top(); q.pop();
        poly b = q.top(); q.pop();
        a = a*b;
        if((int)a.size() > n+2) a.resize(n+2);
        q.push(a);
    }
    f = q.top();
     
    ll ans = 0;
    for(int i = 0; i <= min(n,(int)f.size()-1); i++)
        (ans += ((i%2?-1:1) * f[i]%P * fact[n-i]%P + P)%P) %= P;
     
    cout << ans << "\n";
}
 
void dfs(int x, int fa)
{
    int mx = 0;
    siz[x] = 1;
    for(auto y : ver[x])
    {
        if(y == fa) continue;
        dfs(y, x); siz[x] += siz[y];
        mx = max(mx, siz[y]);
    }
    mx = max(mx, n-siz[x]);
    if(mx < Gmx) G = x, Gmx = mx;
}
ll C(int n, int m)
{
    if(n < m or n < 0 or m < 0) return 0;
    return fact[n]%P * finv[m]%P *finv[n-m]%P;
}
void fact_prework(int n)
{
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = fact[i-1]*i%P;
     
    finv[n] = qpow(fact[n], P-2);
    for(int i = n-1; i >= 0; i--)
        finv[i] = finv[i+1]*(i+1)%P;
}