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)$。所以先鸽了。
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\n",la); 33 }if(!op)printf("%d\n",la); 34 }
T3：星际穿越
大意：$r \times 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} = \sum\limits_{x<j} \frac{dp_{i-1,x}}{(jK-xK)!}$。最后除的那个就是把多重集排列考虑在内了。$n!$放在最外面乘。
最终的答案是枚举最后一段的长度得到是$n! \sum\limits_{i=0}^{m} \sum\limits_{j=0}^{m} dp_{j,i} \frac{(-1)^{m-i}}{(n-jK)!}$
其中的$-1$就是容斥系数。
然而我们发现$i$这一维并无卵用，只不过在最后容斥时根据奇偶性乘正负$1$罢了。
所以我们在转移的时候直接乘上$-1$就好了。也就是说
$dp_j = - \sum\limits_{x<j} \frac{dp_x}{(jK-xK)!}$
最后答案就是$n! \sum\limits_{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)=\sum\limits_{i=1} dp_i x^i,G(x) = \limits_{i=1} \frac{1}{(iK)!}x^i$
要注意毒瘤题解没有$0$次项于是要多一些特判，于是我们根据转移列出原始式子：
$F+1=(F+1)G+1$
于是也就有$F=\frac{-G}{G+1}$。然后一个多项式求逆也就没了，、最后统计答案也要注意$0$次项。
至于$r \neq 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 }
原文：https://www.cnblogs.com/hzoi-DeepinC/p/12380938.html
