前言

前言之后再写。

出发问题

如何求字符串 $S$ 和 $T$ 的一个区间的 lcs。

首先求 $S$ 和 $T$ 的 lcs 就是很困难的了，目前应该没有低于 $O(\frac{|S||T|}w)$ 的做法。

因此对于这个问题，我们期待一个 $O(|S||T|+q)$ 再最多乘 ploylog 的做法。

先鸽了，不知道有生之年会不会写完——5.12

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)$。

对于一堆形如 010110001 的操作，如果你初始知道 01 的答案，并且可以合并两个操作，那么你可以预处理所有长度为 $B$ 的 $01$ 串，然后拼成答案。

这样是 $O(\frac n B + 2^B)$ 的，$B$ 取 $\log n -\log\log n$，可以做到 $O(\frac n {\log n})$。

可以用于例如 +-1 rmq 等地方。

然后考虑你的操作事实上是选两个合并起来。

做 $x$ 步只有 $\displaystyle\prod_{k=1}^x \frac {k(k+1)} 2 $ 种，开 $\log$ 后是 $O(x\ln x)$ 级别。

你要完成的操作的可能都有 $2^n$ 种了，开 $\log$ 后也就是 $n$，所以不可能做的比 $O(\frac n{\log n})$ 更好了。

其实感觉万欧之类的思想和这个有点像。

$n=10^6$，sort 跑 $70$ms 左右。

$n=10^6$，基排在值域 $10^9$ 的情况下比 sort 快 $3$ 倍，在值域是 $10^{18}$ 的情况下比 sort 快 $2$ 倍。

vector/数组 int/long long 在 sort 下没啥影响。

给定 $n,m,p$，求出 $(^n_m)\mod p$ 的值。

你可以认为 $0 \le m\le n$。

前面省略 $2^9$ 种简单求法。

$n,m\le 10^{18}$，$p\le 10^6$

这个用 exlucas 即可，时间复杂度 $O(p\log p)$ 左右，应该不能做到更优了。

$m\le 10^6$，$n\le 10^{18}$，$p\le 10^{18}$

考虑 $1$ 到 $m$ 中的质数是否是 $p$ 的因数。

如果是的话，可以考虑记录每种质数在 $m!$ 里的出现次数和在 $\frac{n!}{(n-m)!}$ 的出现次数，这就和 exlucas 有点像了。

然后因为这种质数 $t$ 不超过 $\omega(p)$（？） 个，所以可以直接枚举 $t^k$，计算出现次数。

剩下的因为和 $p$ 互质，所以可以直接全部乘起来 exgcd。

然后这样是 $O(m+\omega(p)\log n)$ 的。

$n,m,p\le 10^{18}$

这玩意看起来就不能做。

于是组合数在 $m$ 比较小或 $p$ 比较小的时候都能做。

本文的 lca 仅探讨无修改有根树（？）上的 lca 相关的求法。

有一个有 $n$ 个点的有根树，你要在树上进行 $q$ 次查询，每次查询两点间的 lca。

暴力跳

时间复杂度 $O(nq)$，空间复杂度 $O(n)$，可以在线，非常简单，可以维护一些路径上的信息。

倍增求 lca

预处理时空复杂度 $O(n\log n)$，查询单次 $O(\log n)$，可以在线，可以维护一些可合并的，具有结合律的信息，好写。

斜二倍增求 lca

预处理时空 $O(n)$，查询单次 $O(\log n)$，可以在线，可以维护一些可合并的，具有结合律的信息，比较好写，思想稍微比较难。

树剖求 lca

应该和斜二倍增差不多（？），但需要如果维护信息的话需要额外开线段树（？），这里因为跳链是一个前缀可以预处理，所以也是单次 $O(\log n)$ 的，可拓展性很强，并且查询期望跑得很快。

dfn 序/欧拉序求 lca

预处理时空 $O(n\log n)$，可以在线，单次查询 $O(1)$，可以利用树上差分维护一些信息，好写。

如果用跑得比较快的 st 表，如 +-1 st 表，预处理时空均线性，查询 $O(1)$，不太好写，可以在线，瓶颈在于路径信息需要可差分。

tarjan 求 lca

如果用通常的并查集的话，时间复杂度 $O(\min(n,q)\alpha(n)+q+n)$（大概？），空间线性，需要离线，可以维护可合并的，具有结合律的信息，挺好写的。