UKBwyx的博客突然想起多项式科技能做个快速求阶乘。
那在 $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$ 种简单求法。
这个用 exlucas 即可，时间复杂度 $O(p\log p)$ 左右，应该不能做到更优了。
考虑 $1$ 到 $m$ 中的质数是否是 $p$ 的因数。
如果是的话，可以考虑记录每种质数在 $m!$ 里的出现次数和在 $\frac{n!}{(n-m)!}$ 的出现次数，这就和 exlucas 有点像了。
然后因为这种质数 $t$ 不超过 $\omega(p)$（？） 个，所以可以直接枚举 $t^k$，计算出现次数。
剩下的因为和 $p$ 互质，所以可以直接全部乘起来 exgcd。
然后这样是 $O(m+\omega(p)\log n)$ 的。
这玩意看起来就不能做。
于是组合数在 $m$ 比较小或 $p$ 比较小的时候都能做。
本文的 lca 仅探讨无修改有根树（？）上的 lca 相关的求法。
有一个有 $n$ 个点的有根树，你要在树上进行 $q$ 次查询，每次查询两点间的 lca。
时间复杂度 $O(nq)$，空间复杂度 $O(n)$，可以在线，非常简单，可以维护一些路径上的信息。
预处理时空复杂度 $O(n\log n)$，查询单次 $O(\log n)$，可以在线，可以维护一些可合并的，具有结合律的信息，好写。
预处理时空 $O(n)$，查询单次 $O(\log n)$，可以在线，可以维护一些可合并的，具有结合律的信息，比较好写，思想稍微比较难。
应该和斜二倍增差不多（？），但需要如果维护信息的话需要额外开线段树（？），这里因为跳链是一个前缀可以预处理，所以也是单次 $O(\log n)$ 的，可拓展性很强，并且查询期望跑得很快。
预处理时空 $O(n\log n)$，可以在线，单次查询 $O(1)$，可以利用树上差分维护一些信息，好写。
如果用跑得比较快的 st 表，如 +-1 st 表，预处理时空均线性，查询 $O(1)$，不太好写，可以在线，瓶颈在于路径信息需要可差分。
如果用通常的并查集的话，时间复杂度 $O(\min(n,q)\alpha(n)+q+n)$（大概？），空间线性，需要离线，可以维护可合并的，具有结合律的信息，挺好写的。
见到了六年级大佬，感觉被单调队列了。通过讲座第一次知道 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$
上午非常好讲座，和在大学听讲座一样（什）。
比赛先开的 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。
noip 去的是南外的考场，考前不太清醒，上场敲了个平常用的头文件和线段树板子就摆了。
下发的密码打不开文件，于是继续摆。
过了一会能打开 pdf 了，开始看题。
T1 看起来是个很显然的贪心啊，大胆假设是从前往后尽可能匹配，20min 左右过了大样例，去写 T2。
看到 T2 的数据范围就想到了考前模拟赛的矩阵光速幂，正着推了一会有点乱，于是容斥一下发现很对，甚至只需要快速幂，在 40+min 时过了 T2 的大样例。
看到 T3 一眼就认定了这道题很可做，直接尝试推正解，推正解的过程中把链和菊花的特殊性质写了，推了 2h（？） 发现不太对，于是去看了眼 T4，把 $O(n^2)$ 暴力写了，回来继续搞 T3，未果，最后只补写了个 $k=1$ 的点。
出考场后发现 T1 难度是蓝，我场上以为 T1 最多黄，很慌，T3、T4 都是紫，那还行。
最后 $100+100+40+32=272$，比大众分还低的大众分，不过至少没挂分。