25+0+0=25
7分钟拿到整场拿的所有分然后相当于啥也没干。
今天很开心的换了台电脑，能上$OJ$于是很开心，就开始打比赛了。
然而因为新电脑没有装虚拟机所以要重新适应$Windows$。感觉问题不大，也就是个$DevC++$
看到下发文件于是下载下来。
然后发现这台电脑居然没有能打开压缩文件的软件？？？
于是花了些时间下载安装什么的才终于把文件打开。
然后$T1$看出是虚树肯定是不会写的。
$T2$好像是个基础数学大杂烩。$T3$啥也没看出来于是扔了。
于是面向最简单的$T2$。化式子，应付频率低多了但依旧存在的断网，然后开始码。
码了一阵，终于写完。正当我很开心的打算调试时，我忽然发现按$F11$没反应。
说好的编译运行呢。。？然后我发现$F9$才是。$Ctrl+F9$是编译$Ctrl+F10$是运行。
是我跟不上时代了？于是$F9$。然后疯狂弹窗，然后说您未编译。
？？？
然后花了半小时左右研究这个我已经不认识了的$DevC++$。并且重新安装了一次。啥也没研究出来
于是被迫在弱网条件下用$Online IDE$。一分钟一响应。
最终不知道花了多久终于过了编译。然后答案当然不对。此时$T1/T3$还完全没有动。
于是最后放弃一切为了防爆零赶紧回$T1$写了个弱智$BFS$拿个$25$。
$T3$因为没时间看题匆匆忙忙写完就交，剩两分钟等不了$IDE$编译了于是就直接交了。
果然一个玄青色的$0$在考后浮现在眼前。
忍无可忍。下午花了大概两小时把$DevC++$重新装好，非常开心。
虽说网络断断续续是个问题，但是不能编译更可怕吧。。。
改题的话$T2$考场上思路就差不多了，在修完电脑之后一会就改出来了。
然而$T3$弄得不太明白到处问，慢慢悠悠费了半个晚上。
最后剩下一个小时看着$T1$的虚树毫无脾气，果断放弃回来写反思了。
然而$T1$应该是个好题，很练码力，有空还是应该回来写的。
T1：盗梦空间
大意：树，每次指定$K$个点，求一个点，使这个点离最近的被指定的点最远，输出距离。$n,sum K le 10^5$
一眼虚树。
两眼分类讨论。
三眼不可做。
大概思路就是建出虚树，先跑个多源最短路计算出每个虚树节点的答案。
然后分情况讨论答案点在哪里：
在某个虚树节点的（某一个子树不含虚树节点的儿子）的子树中。这个可以用$STL::multiset$直接维护。每次建虚树时把虚树边对应儿子去除。
在一对虚树父子链（不含端点）的子树中，继续分情况，分类讨论刚刚的多源最短路是否完整包含这条父子边：
如果包含，那么到每个点的距离都是可以计算的，就是你已经知道了最短路来的方向：
如果是从儿子方向来的，那么对于节点$x$的子树中的点$u$距离就是$dep_{son}+dep_u-2dep_x+dis_{son}$。要维护一个点去掉某儿子后最大的$dep_u-2dep_x$
如果是从父亲方向来的，那么大致同理，距离是$dis_{fa}+dep_u-dep_{fa}$这个就好维护多了就是$dep_u$最大值。
如果最短路并未包含整条边那么就可以找到分界点，对上下两部分分别采取上述方法。
困难在于维护去掉一个儿子的那个信息。于是维护一个信息表示去掉这个节点后父亲的权值。然后就可以直接倍增找儿子了。
时间复杂度$O(nlogn)$。代码复杂度$O(+ infty)$。所以先鸽了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 200000 4 multiset<int>d0[S];vector<int>usd; 5 int fir[S],l[S],to[S],v[S],ec,dep[S],mxd[S],n,Q,r[S],dfn[S],tim,tp,sta[S],dt[S],ans; 6 int d1[S][17],d2[S][17],f[S][17]; 7 void link(int a,int b,int w){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=w;} 8 void con(int a,int b,int w=0){link(a,b,w);link(b,a,w);} 9 void dfs(int p,int fa){ 10 f[p][0]=fa;mxd[p]=dep[p]=dep[fa]+1;dfn[p]=++tim;d0[p].insert(dep[p]); 11 for(int i=1;i<=16;++i)f[p][i]=f[f[p][i-1]][i-1]; 12 for(int i=fir[p];i;i=l[i])if(to[i]!=fa)dfs(to[i],p),d0[p].insert(mxd[to[i]]),mxd[p]=max(mxd[p],mxd[to[i]]); 13 } 14 void Dfs(int p,int fa){ 15 if(fa){ 16 d0[fa].erase(d0[fa].find(mxd[p])); 17 d2[p][0]=*(--d0[fa].end()),d1[p][0]=d2[p][0]-dep[fa]*2; 18 for(int i=1;i<=16;++i)d1[p][i]=max(d1[p][i-1],d1[f[p][i-1]][i-1]),d2[p][i]=max(d2[p][i-1],d2[f[p][i-1]][i-1]); 19 d0[fa].insert(mxd[p]); 20 } 21 for(int i=fir[p];i;i=l[i])if(to[i]!=fa)Dfs(to[i],p); 22 } 23 int lca(int x,int y){ 24 int sub=dep[x]-dep[y]; if(sub<0)sub=-sub,swap(x,y); 25 for(int i=16;~i;--i)if(sub&1<<i)x=f[x][i]; 26 if(x==y)return x; 27 for(int i=16;~i;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; 28 return f[x][0]; 29 } 30 int get_son(int p,int anc){ 31 int sub=dep[p]-dep[anc]-1; 32 for(int i=16;~i;--i)if(sub&1<<i)p=f[p][i]; 33 return p; 34 } 35 int upd1(int p,int s,int bs){for(int i=16;~i;--i)if(s&1<<i)ans=max(ans,bs+d1[p][i]),p=f[p][i];return p;} 36 void upd2(int p,int s,int bs){if(s>0)for(int i=16;~i;--i)if(s&1<<i)ans=max(ans,bs+d2[p][i]),p=f[p][i];} 37 priority_queue<pair<int,int>>q; 38 void DFS(int p,int fa){ 39 for(int i=fir[p],x;i;i=l[i])if(to[i]!=fa){ 40 DFS(to[i],p),d0[p].erase(d0[p].find(mxd[get_son(to[i],p)])); 41 if(dep[to[i]]-dep[p]>1) 42 if(dt[to[i]]==dt[p]+v[i])upd2(to[i],v[i]-1,dt[p]-dep[p]); 43 else if(dt[p]==dt[to[i]]+v[i])upd1(to[i],v[i]-1,dt[to[i]]+dep[to[i]]); 44 else x=upd1(to[i],dt[p]-dt[to[i]]+v[i]>>1,dt[to[i]]+dep[to[i]]),upd2(x,dep[x]-dep[p]-1,dt[p]-dep[p]); 45 } 46 ans=max(ans,dt[p]+*d0[p].rbegin()-dep[p]); 47 for(int i=fir[p];i;i=l[i])if(to[i]!=fa)d0[p].insert(mxd[get_son(to[i],p)]); 48 } 49 int main(){ 50 scanf("%d%d",&n,&Q); 51 for(int i=1,a,b;i<n;++i)scanf("%d%d",&a,&b),con(a,b); 52 dfs(1,0);Dfs(1,0); 53 for(int i=1;i<=n;++i)fir[i]=0; 54 while(Q--){ 55 int K;scanf("%d",&K); ans=tp=ec=0; 56 for(int i=1;i<=K;++i)scanf("%d",&r[i]),usd.push_back(r[i]); 57 sort(r+1,r+1+K,[](int x,int y){return dfn[x]<dfn[y];}); 58 for(int i=1,l;i<=K;++i){ 59 if(!tp)goto E; 60 l=lca(sta[tp],r[i]); 61 if(l==sta[tp])goto E; 62 while(tp>1&&dfn[l]<=dfn[sta[tp-1]])con(sta[tp-1],sta[tp],dep[sta[tp]]-dep[sta[tp-1]]),tp--; 63 if(sta[tp]!=l)con(sta[tp],l,dep[sta[tp]]-dep[l]),sta[tp]=l,dt[l]=n,usd.push_back(l); 64 E:sta[++tp]=r[i];dt[r[i]]=0; 65 } 66 while(tp>1)con(sta[tp-1],sta[tp],dep[sta[tp]]-dep[sta[tp-1]]),tp--; 67 if(sta[tp]!=1)con(1,sta[tp],dep[sta[tp]]-1),dt[1]=n,usd.push_back(1); 68 for(int i=1;i<=K;++i)q.push(make_pair(0,r[i])); 69 while(!q.empty()){ 70 int d=-q.top().first,p=q.top().second;q.pop(); 71 if(d!=dt[p])continue; 72 for(int i=fir[p];i;i=l[i])if(dt[to[i]]>d+v[i])q.push(make_pair(-(dt[to[i]]=d+v[i]),to[i])); 73 } 74 DFS(1,0); printf("%d ",ans); 75 for(auto x:usd)fir[x]=0; usd.clear(); 76 } 77 }
T2：爱乐之城
大概是$dy$讲过的原题然而忘了怎么做。从头想不难，然而丢了两小步导致复杂度爆炸了且答案统计差了。
https://www.cnblogs.com/hzoi-DeepinC/protected/p/12311014.html。题号18。题解差不多。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 #define S 400005 5 int n,m,op,f[S],g[S],pc,mu[S],p[S],np[S],la,sum[S],h[S],tot[S],phi[S],s[S]; 6 vector<int>dv[S]; 7 int cal(int x){return x*(x+1ll)/2%mod;} 8 int x2(int x){return 1ll*x*x%mod;} 9 int main(){ 10 cin>>n>>m>>op; 11 mu[1]=phi[1]=1; 12 for(int i=2;i<=m;++i){ 13 if(!np[i])p[++pc]=i,mu[i]=-1,phi[i]=i-1; 14 for(int j=1;i*p[j]<=m;++j) 15 if(i%p[j])np[i*p[j]]=1,mu[i*p[j]]=-mu[i],phi[i*p[j]]=phi[i]*phi[p[j]]; 16 else {np[i*p[j]]=1;phi[i*p[j]]=phi[i]*p[j];break;} 17 } 18 for(int i=1;i<=m;++i)sum[i]=(sum[i-1]+1ll*i*i*mu[i]%mod+mod)%mod; 19 for(int i=1;i<=m;++i)f[i]=(f[i-1]+1ll*x2(i)*phi[i])%mod; 20 for(int i=1;i<=m;++i)sum[i]=(sum[i-1]+mu[i]+mod)%mod; 21 for(int i=1;i<=m;++i)for(int j=i;j<=m;j+=i)dv[j].push_back(i); 22 for(int i=1;i<=m;++i){ 23 g[i]=g[i-1]; 24 for(int j=0,r;j<dv[i].size();++j)r=s[dv[i][j]],s[dv[i][j]]+=mu[i], 25 g[i]=(g[i]+(x2(s[dv[i][j]])-x2(r)+0ll+mod)*mu[dv[i][j]]+0ll+mod)%mod; 26 } 27 for(int i=1;i<=m;++i)for(int j=i;j<=m;j+=i)h[j]=(h[j]+0ll+mod+mu[j/i]*g[i])%mod; 28 for(int i=1;i<=m;++i)tot[i]=1; 29 while(n-->0){ 30 int a;scanf("%d",&a); if(op)a=(19891989ll*la+a)%m+1; 31 for(int i=0;i<dv[a].size();++i)la=(la+1ll*tot[dv[a][i]]*f[a]%mod*h[dv[a][i]])%mod,tot[dv[a][i]]=(f[a]+1ll)*tot[dv[a][i]]%mod; 32 if(op)printf("%d ",la); 33 }if(!op)printf("%d ",la); 34 }
T3：星际穿越
大意：$r imes n$矩阵。每行是个排列。每列若满足每行的$A_i < A_{i+1}$为稳定。求对于$K$的倍数列不稳定其他列稳定的矩阵数。$n le 10^6$
是个$dp$题啊。。。
先考虑$r=1$
我们枚举最后在$K$倍数位置上的点稳定的至少有几个点稳定，其余$K$倍位置均不稳定，非$K$倍位置均稳定的方案数。
如果能求出这个，那么就可以容斥得到答案。
发现这样的话整个序列就是若干上升序列相接而成。因为最后方案肯定极长上升序列的长度是$K$的倍数。
于是我们枚举长度是$K$的几倍就好。因为限制是至少而不是恰好所以不用考虑两端之间的大小关系。
设最后段数是$m=frac{n-1}{K}$
唯一需要考虑的就是段内部的顺序已经确定，于是是个多重集排列，也就是$frac{n!}{prod a_i !}$
所以枚举长度转移。设$i$段总长是$jK$的方案数是$dp_{i,j}$那么有
$dp_{i,j} = sumlimits_{x<j} frac{dp_{i-1,x}}{(jK-xK)!}$。最后除的那个就是把多重集排列考虑在内了。$n!$放在最外面乘。
最终的答案是枚举最后一段的长度得到是$n! sumlimits_{i=0}^{m} sumlimits_{j=0}^{m} dp_{j,i} frac{(-1)^{m-i}}{(n-jK)!}$
其中的$-1$就是容斥系数。
然而我们发现$i$这一维并无卵用，只不过在最后容斥时根据奇偶性乘正负$1$罢了。
所以我们在转移的时候直接乘上$-1$就好了。也就是说
$dp_j = - sumlimits_{x<j} frac{dp_x}{(jK-xK)!}$
最后答案就是$n! sumlimits_{i=0}^{m} dp_i frac{(-1)^{m-i}}{(n-iK)!} (-1)^i = n! (-1)^m sum limits_{i=0}^{m} frac{dp_i}{(n-iK)!} $
前面那两个$-1$大概就是一个是最终答案的容斥系数，另一个是强行凑成$m$段方便处理。（因为你转移过程中有负的了你需要给它抹平）
（我大概也只能这么理解了）
然后问题就在于$dp$的求解了。明显的卷积形式，但是自我依赖。
于是可以分治$NTT$然而$O(nlog^2n)$显然是不可接受的。
分治$NTT$好像不少时候可以生成函数然后转化成别的东西。根据定义我们设计：
$F(x)=sumlimits_{i=1} dp_i x^i$,$G(x) = sumlimits_{i=1} frac{1}{(iK)!}x^i$
要注意毒瘤题解没有$0$次项于是要多一些特判，于是我们根据转移列出原始式子：
$F+1=(F+1)G+1$
于是也就有$F=frac{-G}{G+1}$。然后一个多项式求逆也就没了，、最后统计答案也要注意$0$次项。
至于$r eq 1$的情况，大同小异，也就是转移系数由阶乘变成了阶乘的若干次幂，剩下就一样了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 #define S 1<<21 5 int len,rev[S],iG[S],G[S],g[S],n,m,r,K,fac[S],inv[S],f[S],ans; 6 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;} 7 int add(int x,int y){x+=y;return x>=mod?x-mod:x;} 8 int dec(int x,int y){x-=y;return x<0?x+mod:x;} 9 int mul(int x,int y){return 1ll*x*y%mod;} 10 int set_len(int x){len=1;while(len<x)len<<=1;for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);} 11 void NTT(int*a,int op=1){ 12 for(int i=0;i<len;++i)if(rev[i]>i)swap(a[rev[i]],a[i]); 13 for(int i=1;i<len;i<<=1)for(int j=0,t=qp(3,(mod-1)/i/2*op+mod-1);j<len;j+=i<<1) 14 for(int x,y,w=1,k=j;k<j+i;++k,w=mul(w,t)) 15 x=a[k],y=mul(w,a[k+i]),a[k]=add(x,y),a[k+i]=dec(x,y); 16 if(op==-1)for(int i=0,iv=qp(len,mod-2);i<len;++i)a[i]=mul(a[i],iv); 17 } 18 void Inv(int*a,int*b,int n){ 19 if(n==1)return void(b[0]=qp(a[0],mod-2)); 20 Inv(a,b,n+1>>1); set_len(n<<1); 21 int A[len],B[len]; 22 for(int i=0;i<len;++i)A[i]=a[i]*(i<n),B[i]=(i<n+1>>1)*b[i]; 23 NTT(A);NTT(B); for(int i=0;i<len;++i)A[i]=mul(A[i],mul(B[i],B[i])); NTT(A,-1); 24 for(int i=0;i<n;++i)b[i]=dec(add(b[i],b[i]),A[i]); 25 } 26 int main(){ 27 cin>>n>>r>>K;m=(n-1)/K; 28 for(int i=fac[0]=1;i<=n;++i)fac[i]=mul(fac[i-1],i); 29 inv[n]=qp(fac[n],mod-2); for(int i=n-1;~i;--i)inv[i]=mul(inv[i+1],i+1); 30 for(int i=0;i<=m;++i)G[i]=g[i]=qp(inv[i*K],r); 31 Inv(G,iG,m+1); g[0]=0; set_len(m+1<<1); 32 NTT(g); NTT(iG); for(int i=0;i<len;++i)f[i]=mul(g[i],iG[i]); NTT(f,-1); 33 for(int i=0;i<=m;++i)ans=add(ans,mul(f[i],qp(inv[n-i*K],r))); 34 cout<<mul(m&1?qp(fac[n],r):mod-qp(fac[n],r),ans)+(m&1?-1:1)<<endl; 35 }