rt，先考虑怎么线性构造树状数组。

其实只要对于 $i=1\sim n$

v[i+(i&-i)]+=v[i]

就行了。

树状数组差分就是这玩意倒过来做。

突然想起多项式科技能做个快速求阶乘。

那在 $p$ 为质数且 $n<=p$的时候可以直接求 $n!$、 $m!$ 和 $(n-m)!$，然后取个逆就行了。

所以可以做到 $O(\sqrt{n}\log n)$ 或在 $n>p$ 时用 lucas 做到 $O(\sqrt{p}\log^2 p)$，如果用 exlucas 应该可以做到 $O(\sqrt{p}\log^2 p)$，但是常数因为是任意模数所以很大。

如果 $p$ 是给定的用分段打表阶乘可以做到自己跑 $O(n)$ 时间，然后写出一个 $O(\frac n B)$ 的做法，考虑一般代码最多 $50000$ 字符，大约压缩一下能塞 $10^4$ 个数进去，也就是可以做到 $O(\frac n {10^4})$。

多项式科技（持续更新）

namespace poly {
    const int mod=998244353;
    long long w[1<<21];
    int rv[1<<21];
    pii exgcd(int x,int y) {
        if(y==0)return mp(1,0);
        pii t=exgcd(y,x%y);
        return mp(t.second,t.first-t.second*(x/y));
    }
    inline long long ksm(long long x,long long y) {
        long long res=1;
        while(y) {
            if(y&1)res=res*x%mod;
            x=x*x%mod,y>>=1;
        }
        return res;
    }
    inline void trans(vector<int>&a,int len,bool intt) {
        int n1=1<<len;
        a.resize(n1);
        for(int i=1; i<n1; i++) {
            rv[i]=rv[i>>1]>>1;
            if(i&1)rv[i]|=1<<len-1;
        }
        w[0]=1;
        for(int i=0; i<n1; i++)if(rv[i]<i)swap(a[i],a[rv[i]]);
        for(int i=0; i<n1; i++) {
            a[i]%=mod;
            if(a[i]<0)a[i]+=mod;
        }
        long long w1=ksm(3,mod-1>>len);
        if(intt)w1=(exgcd(mod,w1).second+mod)%mod;
        for(int t=1; t<=len; t++) {
            int t1=1<<t,t2=1<<t-1,s=n1>>t;
            long long w2=ksm(w1,s);
            for(int i=1; i<t2; i++)w[i]=w[i-1]*w2%mod;
            for(int i=0; i<n1; i+=t1) {
                for(int j=0; j<t2; j++) {
                    int u=i+j,v=i+j+t2;
                    int tt=a[u];
                    long long t=w[j]*a[v]%mod;
                    a[v]=tt-t;
                    if(a[v]<0)a[v]+=mod;
                    a[u]=tt+t;
                    if(a[u]>=mod)a[u]-=mod;
                }
            }
        }
        long long t=exgcd(mod,n1).second;
        if(intt)for(int i=0; i<n1; i++)a[i]=a[i]*t%mod;
        for(int i=0; i<n1; i++)if(a[i]<0)a[i]+=mod;
    }
    inline void tz(vector<int>&a) {
        int la=a.size();
        for(int i=a.size()-1; i>=1; i--) {
            if(a[i])break;
            la=i;
        }
        a.resize(la);
    }
    inline void qf(vector<int>&a) {
        for(int i=0; i<a.size(); i++)if(a[i])a[i]=mod-a[i];
    }
    vector<int>add(vector<int>&a,vector<int>&b) {
        int n=max(a.size(),b.size());
        vector<int>res;
        a.resize(n);
        b.resize(n);
        res.resize(n);
        for(int i=0; i<n; i++) {
            res[i]=a[i]+b[i];
            if(res[i]>=mod)res[i]-=mod;
        }
        return res;
    }
    vector<int>minus(vector<int>&a,vector<int>&b) {
        int n=max(a.size(),b.size());
        vector<int>res;
        a.resize(n);
        b.resize(n);
        res.resize(n);
        for(int i=0; i<n; i++) {
            res[i]=a[i]-b[i];
            if(res[i]<0)res[i]+=mod;
        }
        return res;
    }
    inline void mul(vector<int>&a,vector<int>&b) {
        for(int i=0; i<a.size(); i++)a[i]=(long long)a[i]*b[i]%mod;
    }
    inline int get_len(int x) {
        return log2(x)+1;
    }
    inline void prt(vector<int>&a) {
        for(int i=0; i<a.size(); i++) {
            cout<<a[i]<<" ";
        }
        cout<<"\n";
    }
    inline vector<int> conv(vector<int>a,vector<int>b) {
        int l=get_len(a.size()+b.size());
        trans(a,l,0);
        trans(b,l,0);
        mul(a,b);
        trans(a,l,1);
        return a;
    }
    void inv(vector<int>&a,int n) {
        vector<int>b;
        a.resize(n);
        for(int i=0; i<n; i++)if(a[i]<0)a[i]+=mod;
        b.pb(exgcd(mod,a[0]).second);
        for(int i=2,l=1; i<n<<1; i<<=1,l++) {
            vector<int>t,c;
            c=b;
            for(int j=0; j<c.size(); j++)c[j]=(c[j]<<1)%mod;
            t.resize(i);
            c.resize(i);
            for(int j=0; j<min(i,(int)a.size()); j++)t[j]=a[j];
            trans(t,l+1,0);
            trans(b,l+1,0);
            mul(b,b);
            mul(t,b);
            trans(t,l+1,1);
            for(int j=0; j<i; j++) {
                c[j]=(c[j]-t[j])%mod;
            }
            swap(b,c);
        }
        a=b;
    }
    vector<int> div(vector<int>a,vector<int>b) {
        tz(b);
        int n=a.size(),m=b.size();
        if(n<m)return a;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        inv(b,n-m+1);
        a.resize(n-m+1);
        a=conv(a,b);
        a.resize(n-m+1);
        reverse(a.begin(),a.end());
        return a;
    }
    vector<int> rem(vector<int>&a,vector<int>&b,vector<int>&d) {
        vector<int>t=conv(b,d);
        vector<int>res=minus(a,t);
        tz(res);
        return res;
    }
    vector<int> Mod(vector<int>a,vector<int>b) {
        vector<int>t=div(a,b);
        return rem(a,b,t);
    }
    vector<int>ny;
    inline void csh(int n) {
        ny.resize(n+1);
        ny[1]=1;
        for(int i=2; i<=n; i++) {
            ny[i]=mod-(mod/i)*(long long)ny[mod%i]%mod;
        }
    }
    vector<int> ln(vector<int>a) {
        int n=a.size();
        vector<int>b;
        b.resize(n-1);
        for(int i=0; i<n-1; i++) {
            b[i]=a[i+1]*(i+1ll)%mod;
        }
        inv(a,n-1);
        a=conv(a,b);
        a.resize(n);
        csh(n);
        for(int i=n-1; i>=1; i--) {
            a[i]=a[i-1]*(long long)ny[i]%mod;
        }
        a[0]=0;
        return a;
    }
    vector<vector<int>>vl;
    int val_one(int x,vector<int>&a) {
        int res=0,cur=1;
        for(int i=0; i<a.size(); i++) {
            res=(res+a[i]*(long long)cur)%mod;
            cur=cur*(long long)x%mod;
        }
        return res;
    }
    void val1(vector<int>&x,int wz) {
        if(x.size()==1) {
            vl[wz].resize(2);
            vl[wz][1]=1;
            vl[wz][0]=-x[0];
            return;
        }
        int mid=x.size()>>1,lt=wz<<1,rt=wz<<1|1;
        vector<int>l,r;
        l.resize(mid);
        r.resize(x.size()-mid);
        for(int i=0; i<mid; i++)l[i]=x[i];
        for(int i=mid; i<x.size(); i++)r[i-mid]=x[i];
        val1(l,lt);
        val1(r,rt);
        vl[wz]=conv(vl[lt],vl[rt]);
        tz(vl[wz]);
    }
    vector<int> val2(vector<int>&x,vector<int>&a,int wz) {
        if(x.size()==1) {
            return {val_one(x[0],a)};
        }
        int mid=x.size()>>1,lt=wz<<1,rt=wz<<1|1;
        vector<int>l,r,t=Mod(a,vl[wz]);
        l.resize(mid);
        r.resize(x.size()-mid);
        for(int i=0; i<mid; i++)l[i]=x[i];
        for(int i=mid; i<x.size(); i++)r[i-mid]=x[i];
        vector<int>res=val2(l,t,lt);
        vector<int>res1=val2(r,t,rt);
        int t1=res.size();
        res.resize(res.size()+res1.size());
        for(int i=0; i<res1.size(); i++) {
            res[t1+i]=res1[i];
        }
        return res;
    }
    vector<int>val(vector<int>a,vector<int>x) {
        vl.resize(x.size()<<2+1);
        val1(x,1);
        return val2(x,a,1);
    }
};

功能可以自己琢磨。

rt，考虑这样一个问题：

给你一棵 $n$ 个点有向图，你需要数有多少个以 $1$ 为根的内向生成树。

我们考虑刻画一个内向生成树。

首先它除根之外每个点有恰好一个出度指向父节点，考虑所有这样的图，问题是会出现环。

于是对于环的数量容斥，不难想到是一个环乘一个 $-1$ 的容斥系数。

然后发现这东西可以构造出一个矩阵行列式，于是就可以做到 $O(n^3)$ 算这东西了。

rt，如果你的信息是可差分的，直接做一遍加元素的逆运算就行了。

但是如果你的信息不可差分，可以考虑离线根号重构。

直接把最近要修改的元素放在背包末尾，然后对后面背包重跑一遍。

时间复杂度懒得分析了，视题目可以做到 $O(n^{1.5}Vq)$ 或 $O(n^{\frac 4 3}Vq)$。