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)$（大概？），空间线性，需要离线，可以维护可合并的，具有结合律的信息，挺好写的。

Day1

见到了六年级大佬，感觉被单调队列了。通过讲座第一次知道 pku AI 好像比 thu 牛（？）。

试机赛怎么这么难，T2 一分没拿，好在 T1 勉强切了。

开打前就敲了一个头文件，其他蓝的敲，直接睡了。醒来后开的 T1，思考一下发现 $a>b+1$ 是不难的，其他情况大胆猜测 $\frac{(a+b)\times(a+b-1)-a\times(a-1)}{2}+1$，提交发现还过了 $a=2$ 的点，手推了下 $n=3$ 的情况，大胆猜测尽可能平均分成 $a-1$ 个完全图，过了。

然后开 T2，怎么是困难数据结构题，跳了，看 T3。T3 读懂题面后感觉很难，滚回去把 T2 24pts $O(n^2\log n)$ 的暴力跳lca+暴力去重的代码写了，继续想了一下后感觉一点不会，去开 T3，此时 1h30min。

T3 直接思考特殊性质，一番思索后无果。尝试写 $O(nmk)$ 暴力 dp，$dp_{i,j}$ 表示从第 $i$ 个点开始，从第 $r=j$ 时能否获胜，从它的所有可达节点转移，写了没过，此时 2h30min，非常恼火。

想了一下后突然发现要强连通分量缩点，然后就成了一个 DAG，然后注意到对于每个点它所有的可达节点所有可能获胜的 $r$，它的直接子结点一定一定包含所有这样的 $r$，强连通分量内的转移和孤点特判一下就可以做到 $O(mk)$。花 40min 写过了 20pts，感觉这就是最终得分了。

由于不会 T2 继续想 T3，于是发现特殊性质 B 只有最小能达到 $r$ 的是重要的，直接分讨一下好像就对完了。10min 写过了 50pts，又 10min 写过了 75pts，还有半小时尝试推正解，未果。

Day1：$100+24+75=199$

Day2

上午非常好讲座，和在大学听讲座一样（什）。

比赛先开的 T1，拼尽全力无法战胜，1h 了还是 0pts，这也太难了。看了眼 T2，我测怎么我连 $O(n^3)$ 都不会，就写了个 $c=1$ 的贪心跑路。T3 直接打 $O(nb\ln(n))$ 暴力 dp，7s 跑不过 $n\le 5\times 10^6，b\le 40$，只拿了 $n\le 10^6，b\le 40$ 的点，回来看 T1，此时 2h。

瞎构造了一番，我好像会 $4n$ 了，直接开写，这时还有 1h30min。

开写后发现这代码难写的跟什么一样，思路是随机选两个点（其实是 1 和 2），找到一个 离这两个点路径深度（距离）为 1 的点，然后利用这两个点找到与 离这两个点路径深度为 1 的点 的相邻的点，再找到离 离这两个点路径深度为 1 的点 和 离这两个点路径深度为 1 的点的相邻的点 的路径最远的点，再找到和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 的相邻的点，再找到离 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点的相邻的点 的最远的点，此时 离离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点和离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点的相邻的点的最远的点 和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 即为所求（？）。

但是还需要特判 $n=1$、$n=2$、两个点相邻的情况、没有深度为 1 的点的情况、最远点深度为 1 的情况、最远点就是初始两点之一的情况等，最后还剩 30min 才把代码主体写好，加上交互库有 300 行。

过了样例一交，WA 0pts。

使用瞪眼法观察发现样例里点 $1$ 和 $2$ 一定相邻，于是手造了一个这个 case。

（这里应该有一张图片）

发现 ansWA 了，原来是没找到深度为 1 的点，原来深度算错了，交一发 WA0，继续手造 hack，又 hack 掉了。

（这里也应该有一张图片）

哦哦，特判深度为 1 的点为初始两点时特判错了，交一发，WA0，此时还剩 13min。

造了几个 hack 都过了，于是开始静态查错，发现最后一次找最远点时，如果恰好是初始两个点就错了，这时只剩 7min 了，只能尝试改成 $6n$ 或更劣的，改改改，改完了还剩 5min，再不过就要 day2t1 爆0了。

我测，还是 WA0，这下真完蛋了。

这下盲猜错在了 1 与 2 相邻上，先来随便造个 hack。

（这里本来有一张图片）

怎么过了，再造一个。

（这里应该还有一张图片）

我测，ansWa 了。我测，我求出来的最远的点有什么作用吗，烧烤一下确实没作用，那路径上的最小值有作用吗，也没用到啊，那我再跑一遍是为啥，我测，原来敲错变量名了，赶紧改，改完了，我看着电脑上的 17:00 陷入了浅浅的沉思。

我电脑时间快 1 分半啊，交一发，怎么评测怎么慢。

最后还是 WA0 了，D2T1 一分没得。

但这是我的想象，最后过了 50+pts，评测完时间是 $ 16 $:$ 59 $:$ 07 $ 左右，我非常激动所以直接不小心把窗口全叉了。

然后我忘记我每题具体得多少分了。

如果有好心人记得的话可以告诉一下。

Day2 最后应该是 56+11+24=91。