A. 盗梦空间
分析
每次查询时进行一次 \(bfs\) 可以做到 \(nq\) 的复杂度，结合链可以得到 \(30\) 分
正解是给询问点建立虚树
计算时前先求一次多源最短路
可以得到虚树上每一个点的答案，设为 \(dis\)
那么答案就由两部分组成
\(1\) 、虚树上节点在原树上的子树内的答案
这个答案要把当前点所有在虚树上连出去的儿子的答案去掉
设这个点为 \(x\)，子树内的点为 \(son\)
那么 \(dis[son]=dis[x]+dep[son]-dep[x]\)
只要维护一个子树内 \(dep\) 的最大值就可以了
\(2\)、被虚树边覆盖的节点在原树上的子树内的答案
这个答案要把当前点在虚树边方向的一个儿子的答案去掉
设虚树边的父亲节点为 \(fa\) ，儿子节点为 \(son\)，被该虚树边覆盖的某个节点为 \(x\)，\(x\) 的一个合法的儿子节点为 \(u\)
如果 \(dis[fa]=dis[son]+dep[son]-dep[fa]\)
说明最短路是从儿子方向来的
那么 \(dis[u]=dis[son]+dep[son]+dep[u]-2dep[x]\)
也就是对于这条边上的所有被覆盖的节点 \(x\)，查询 \(x\) 子树内最大的 \(dep[u]-2dep[x]\)
如果 \(dis[son]=dis[fa]+dep[son]-dep[fa]\)
说明最短路是从父亲方向来的
那么 \(dis[u]=dis[fa]+dep[u]-dep[fa]\)
也就是对于这条边上的所有被覆盖的节点 \(x\)，查询 \(x\) 子树内最大的 \(dep[u]\)
如果两种情况都不满足，就算一下那个分界点是什么
分界点上面的肯定由父亲贡献答案，下面的肯定由儿子贡献答案
考虑如果去除某个节点的贡献
一个很巧妙的方法是把倍增数组的定义改为去掉当前节点后，当前节点到 \(2^k\) 级祖先的答案
然后就可以直接做了
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<set>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e5+5;
int h[maxn],tot=1,n,m;
struct asd{
int to,nxt;
}b[maxn];
std::set<int> usd;
#define sit std::set<int>::iterator
void ad(rg int aa,rg int bb){
usd.insert(aa),usd.insert(bb);
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
std::multiset<int> ans0[maxn];
int fa[maxn][22],ans1[maxn][22],ans2[maxn][22],dep[maxn],maxdep[maxn],dfn[maxn],dfnc,ans;
void dfs1(rg int now,rg int lat){
maxdep[now]=dep[now]=dep[lat]+1;
dfn[now]=++dfnc;
fa[now][0]=lat;
ans0[now].insert(dep[now]);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
dfs1(u,now);
ans0[now].insert(maxdep[u]);
maxdep[now]=std::max(maxdep[now],maxdep[u]);
}
}
void dfs2(rg int now){
if(fa[now][0]){
ans0[fa[now][0]].erase(ans0[fa[now][0]].find(maxdep[now]));
ans1[now][0]=*ans0[fa[now][0]].rbegin();
ans2[now][0]=ans1[now][0]-2*dep[fa[now][0]];
ans0[fa[now][0]].insert(maxdep[now]);
for(rg int i=1;(1<<i)<=dep[now];i++){
fa[now][i]=fa[fa[now][i-1]][i-1];
ans1[now][i]=std::max(ans1[now][i-1],ans1[fa[now][i-1]][i-1]);
ans2[now][i]=std::max(ans2[now][i-1],ans2[fa[now][i-1]][i-1]);
}
}
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa[now][0]) continue;
dfs2(u);
}
}
int getlca(rg int xx,rg int yy){
if(dep[xx]<dep[yy]) std::swap(xx,yy);
rg int len=dep[xx]-dep[yy],bit=0;
while(len){
if(len&1) xx=fa[xx][bit];
bit++,len>>=1;
}
if(xx==yy) return xx;
for(rg int i=18;i>=0;i--){
if(fa[xx][i]!=fa[yy][i]){
xx=fa[xx][i],yy=fa[yy][i];
}
}
return fa[xx][0];
}
int a[maxn],k,sta[maxn],tp;
bool cmp(rg int aa,rg int bb){
return dfn[aa]<dfn[bb];
}
void insert(rg int now){
rg int lc=getlca(now,sta[tp]);
while(1){
if(dfn[lc]>=dfn[sta[tp-1]]){
if(lc!=sta[tp]){
ad(sta[tp],lc),ad(lc,sta[tp]);
if(lc!=sta[tp-1]) sta[tp]=lc;
else tp--;
}
break;
} else {
ad(sta[tp],sta[tp-1]),ad(sta[tp-1],sta[tp]);
tp--;
}
}
sta[++tp]=now;
}
void buildtree(){
std::sort(a+1,a+1+k,cmp);
sta[tp=1]=1,usd.clear();
if(a[1]!=1) sta[++tp]=a[1];
for(rg int i=2;i<=k;i++) insert(a[i]);
while(tp>1){
ad(sta[tp],sta[tp-1]),ad(sta[tp-1],sta[tp]);
tp--;
}
}
int dis[maxn],vis[maxn],tim;
void cls(){
for(rg sit it=usd.begin();it!=usd.end();++it){
rg int now=*it;
h[now]=-1,dis[now]=0x3f3f3f3f;
}
tot=1;
}
struct jie{
int num,jl;
jie(){}
jie(rg int aa,rg int bb){
num=aa,jl=bb;
}
friend bool operator <(const jie& A,const jie& B){
return A.jl>B.jl;
}
};
std::priority_queue<jie> q;
void dij(){
tim++;
for(rg int i=1;i<=k;i++) q.push(jie(a[i],0)),dis[a[i]]=0;
while(!q.empty()){
rg int now=q.top().num;
q.pop();
if(vis[now]==tim) continue;
vis[now]=tim;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(dis[u]>dis[now]+std::abs(dep[u]-dep[now])){
dis[u]=dis[now]+std::abs(dep[u]-dep[now]);
q.push(jie(u,dis[u]));
}
}
}
}
void getans1(rg int now,rg int len,rg int val){
if(len<0) return;
rg int bit=0;
while(len){
if(len&1){
ans=std::max(ans,ans1[now][bit]+val);
now=fa[now][bit];
}
len>>=1,bit++;
}
}
int getans2(rg int now,rg int len,rg int val){
if(len<0) return now;
rg int bit=0;
while(len){
if(len&1){
ans=std::max(ans,ans2[now][bit]+val);
now=fa[now][bit];
}
len>>=1,bit++;
}
return now;
}
int getson(rg int now,rg int u){
rg int len=dep[u]-dep[now]-1,bit=0;
while(len){
if(len&1) u=fa[u][bit];
len>>=1,bit++;
}
return u;
}
void dfs(rg int now,rg int lat){
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
ans0[now].erase(ans0[now].find(maxdep[getson(now,u)]));
dfs(u,now);
if(dep[u]-dep[now]>1){
if(dis[u]==dis[now]+dep[u]-dep[now]){
getans1(u,dep[u]-dep[now]-1,dis[now]-dep[now]);
} else if(dis[now]==dis[u]+dep[u]-dep[now]){
getans2(u,dep[u]-dep[now]-1,dis[u]+dep[u]);
} else {
rg int tmp=getans2(u,((dep[u]-dep[now])-(dis[u]-dis[now]))/2,dis[u]+dep[u]);
getans1(tmp,dep[tmp]-dep[now]-1,dis[now]-dep[now]);
}
}
}
ans=std::max(ans,dis[now]+*ans0[now].rbegin()-dep[now]);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
ans0[now].insert(maxdep[getson(now,u)]);
}
}
void solve(){
buildtree();
dij();
ans=0;
dfs(1,0);
printf("%d\n",ans);
cls();
}
int main(){
memset(h,-1,sizeof(h));
n=read(),m=read();
rg int aa,bb;
for(rg int i=1;i<n;i++){
aa=read(),bb=read();
ad(aa,bb),ad(bb,aa);
}
dfs1(1,0);
dfs2(1);
memset(h,-1,sizeof(h));
memset(dis,0x3f,sizeof(dis));
tot=1;
for(rg int i=1;i<=m;i++){
k=read();
for(rg int j=1;j<=k;j++) a[j]=read();
solve();
}
return 0;
}
B. 爱乐之城
分析
设 \(f[n]=\sum_{i=1}^ni\sum_{j=1}^n[gcd(i,j)=1]j,g[n]=\sum_{i=1}^n\sum_{j=1}^n\mu(ij)\)
那么
\(\begin{aligned}f[n]&=2\sum_{i=2}^ni\sum_{j=1}^i[gcd(i,j)=1]+1\\&=2\sum_{i=2}^n\frac{\phi(i)i^2}{2}+1\\&=\sum_{i=1}^n \phi(i)i^2 \end{aligned}\)
化成 \(phi\) 的那一步可以考虑对于每一个数 \(n\)
如果 \(gcd(i,n)=1\) ，那么必定存在 \(gcd(i,n-i)=1\)
每一对数的和都是 \(n\)，一共有 \(\frac{phi(n)}{2}\) 对
\(\begin{aligned}g[n]&=\sum_{i=1}^n\sum_{j=1}^n\mu(i)\mu(j)[gcd(i,j)=1]\\&=\sum_{i=1}^n\sum_{j=1}^n\mu(i)\mu(j)\sum_{d|gcg(i,j)}\mu(d)\\&=\sum_{d=1}^n\mu(d)(\sum_{d|i}^n \mu(i))^2 \end{aligned}\)
\(f\) 可以线性筛，\(g\) 可以枚举因数预处理
暴力枚举集合就可以拿到 \(25\) 分
设 \(sum=\sum_{T\in S}g(gcd(T))\prod_{a\in T}f[a]\)
枚举 \(gcd(T)=d\)，则
则 \(sum=\sum_dg(d)\sum_{T\in S}g[gcd(T)=d]\prod_{a\in T}f[a]\)
令 \(ans[d]=\sum_{T\in S}g[gcd(T)=d]\prod_{a\in T}f[a]\)
问题转化为求 \(ans[d]\)
构造 \(r[d]=\prod_{d|a_i}(f[a_i+1])-1\)
有点类似于生成函数
那么 \(r[d]=\sum_{d|i}ans[i]\)
莫比乌斯反演即可 \(ans[d]=\sum_{d|i}r[i]\mu[i/d]\)
\(sum=\sum_dg(d)\sum_{d|k}\mu(k/d)(\prod_{k|a_i}(f(a_i)+1)-1)\)
\(op=0\) 的可以直接去做
\(op=1\) 的考虑每次改变一个 \(k\)，只会增加 \(\sum_{d|k}f(d)\mu(k/d)\)
把这个东西预处理一下就可以通过枚举因数来算了
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<vector>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5,mod=998244353,inv2=499122177;
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int n,m,op,a[maxn],sum,pri[maxn],mu[maxn],phi[maxn],f[maxn],g[maxn],s[maxn],pre[maxn];
bool not_pri[maxn];
std::vector<int> vec[maxn];
void xxs(){
not_pri[0]=not_pri[1]=1;
mu[1]=phi[1]=f[1]=1;
for(rg int i=2;i<=m;i++){
if(!not_pri[i]){
pri[++pri[0]]=i;
mu[i]=mod-1;
phi[i]=i-1;
}
for(rg int j=1;j<=pri[0] && i*pri[j]<=m;j++){
not_pri[i*pri[j]]=1;
if(i%pri[j]==0){
phi[i*pri[j]]=mulmod(phi[i],pri[j]);
break;
}
mu[i*pri[j]]=mod-mu[i];
phi[i*pri[j]]=mulmod(phi[i],pri[j]-1);
}
}
for(rg int i=2;i<=m;i++) f[i]=mulmod(phi[i],mulmod(i,i));
for(rg int i=1;i<=m;i++) f[i]=addmod(f[i],f[i-1]);
for(rg int i=1;i<=m;i++){
for(rg int j=i;j<=m;j+=i){
vec[j].push_back(i);
}
}
for(rg int i=1;i<=m;i++){
g[i]=g[i-1];
for(rg int j=0;j<vec[i].size();j++){
rg int u=vec[i][j];
g[i]=delmod(g[i],mulmod(s[u],mulmod(s[u],mu[u])));
s[u]=addmod(s[u],mu[i]);
g[i]=addmod(g[i],mulmod(s[u],mulmod(s[u],mu[u])));
}
}
for(rg int i=1;i<=m;i++){
for(rg int j=i;j<=m;j+=i){
pre[j]=addmod(pre[j],mulmod(g[i],mu[j/i]));
}
}
}
int ans[maxn],d[maxn];
int main(){
n=read(),m=read(),op=read();
xxs();
for(rg int i=1;i<=n;i++) a[i]=read();
for(rg int i=1;i<=m;i++) d[i]=1;
for(rg int i=1;i<=n;i++){
if(op) a[i]=(1LL*19891989*sum%m+a[i])%m+1;
rg int tmp=a[i];
for(rg int j=0;j<vec[tmp].size();j++){
rg int u=vec[tmp][j];
sum=delmod(sum,mulmod(d[u]-1,pre[u]));
d[u]=mulmod(d[u],addmod(f[tmp],1));
sum=addmod(sum,mulmod(d[u]-1,pre[u]));
}
if(op) printf("%d\n",sum);
}
if(!op) printf("%d\n",sum);
return 0;
}
星际穿越
分析
对于 \(r=1,n \leq 17\) 的，状压随便打打就行了
对于 \(r=1,n\leq 2000\) 的
设 \(f[i][j]\) 为第 \(i\) 个数在前 \(i\) 个数的排名为 \(j\) 的方案数
枚举第 \(i+1\) 个数的排名即可
如果加上前缀和优化复杂度就是 \(n^2\)
考虑问题本质是什么
令 \(m=\frac{n-1}{k}\)
实际上就是恰好选择 \(m\) 段上升的子序列
恰好满足不是很好求，但是可以求出至少有多少个不满足的
答案就是至少有 \(0\) 个不满足的-至少有 \(1\) 个不满足的+至少有\(2\) 个不满足的 \(\cdots\)
设 \(f[i][j]\) 为当前考虑到 \(ik\) 这个位置，至多有 \(j\) 段上升子序列的方案数
因为我们没有去考虑两个上升子序列的交点处是什么样的，所以是至多
转移为 \(f[i][j]=\sum_{o=0}^{i-1}f[o][j-1]\frac{1}{(k(i-o))!}\)
阶乘那一部分就是一个可重排列，最后还要乘上一个 \(n!\)
那么最终的答案就是 \(n!\sum_{i=0}^m\sum_{j=0}^if[i][j](-1)^{i-j}\frac{(-1)^{m-i}}{(n-ki)!}\)
复杂度是 \(n^3\) 的
其实对于 \(r\) 不等于 \(1\) 的情况，任意两行之间选出上升子序列是互不影响的，所以转移的时候给阶乘来个 \(r\) 次方就行了
但是这不等价于给 \(r=1\) 时的答案求一个 \(r\) 次方
因为稳定每一行是都稳定
不稳定只要有一行不稳定就不稳定
所以不是简单的 \(r\)次方的关系
考虑如何化简这个 \(n^2\) 的 $dp $
可以发现第二维在转移的时候并没有用，只是在计算答案的时候乘了一个 \((-1)^{i-j}\)
我们可以把这个 \((-1)^j\) 提出来，转移的时候乘上一个 \(-1\)，就能压掉一维
\(f[i]=-\sum_{j=0}^{i-1}\frac{f[j]}{(k(i-j))!}\)
答案为 \(n!\sum_{i=0}^mf[i](-1)^i\frac{(-1)^{m-i}}{(n-ki)!}=n!(-1)^m\frac{f[i]}{(n-ki)!}\)
这样复杂度就是 \(n^2\) 的
发现这个东西是一个卷积的形式，但是有依赖关系
分治 \(fft\) 的复杂度太高，所以考虑生成函数
设 \(F=\sum_{i=0}^{n}f[i]x,G=-\sum_{i=1}^m(n-ki)!\)
那么 \(F=F \times G+1\)
即 \(F=\frac{1}{1-G}\)
多项式求逆即可
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define rg register
const int maxn=3e6+5,mod=998244353,G=3;
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int n,r,k,f[maxn],ans=0,m,jc[maxn],jcc[maxn],ny[maxn];
int ksm(rg int ds,rg int zs){
rg int nans=1;
while(zs){
if(zs&1) nans=mulmod(nans,ds);
ds=mulmod(ds,ds);
zs>>=1;
}
return nans;
}
void pre(){
ny[1]=1;
for(rg int i=2;i<=n;i++) ny[i]=mulmod(mod-mod/i,ny[mod%i]);
jc[0]=jcc[0]=1;
for(rg int i=1;i<=n;i++) jc[i]=mulmod(jc[i-1],i),jcc[i]=mulmod(jcc[i-1],ny[i]);
for(rg int i=0;i<=n;i++) jc[i]=ksm(jc[i],r),jcc[i]=ksm(jcc[i],r);
}
int wz[maxn];
void ntt(rg int A[],rg int lim,rg int typ){
for(rg int i=0;i<lim;i++) if(i<wz[i]) std::swap(A[i],A[wz[i]]);
for(rg int len=1,t0=0;len<lim;len<<=1,t0++){
rg int w0=ksm(G,(mod-1)/(len<<1));
for(rg int j=0,now=len<<1;j<lim;j+=now){
for(rg int k=0,w=1;k<len;k++,w=mulmod(w,w0)){
rg int x=A[j+k],y=mulmod(A[j+k+len],w);
A[j+k]=addmod(x,y),A[j+k+len]=delmod(x,y);
}
}
}
if(typ==-1){
std::reverse(A+1,A+lim);
rg int ny=ksm(lim,mod-2);
for(rg int i=0;i<lim;i++) A[i]=mulmod(A[i],ny);
}
}
int finv[maxn];
void getinv(rg int A[],rg int B[],rg int deg){
if(deg==1){
B[0]=ksm(A[0],mod-2);
return;
}
getinv(A,B,(deg+1)>>1);
rg int lim=1,bit=0;
for(;lim<deg+deg;lim<<=1) bit++;
for(rg int i=0;i<lim;i++) wz[i]=(wz[i>>1]>>1)|((i&1)<<(bit-1));
for(rg int i=0;i<deg;i++) finv[i]=A[i];
for(rg int i=deg;i<lim;i++) finv[i]=0;
ntt(B,lim,1),ntt(finv,lim,1);
for(rg int i=0;i<lim;i++) B[i]=mulmod(B[i],delmod(2,mulmod(B[i],finv[i])));
ntt(B,lim,-1);
for(rg int i=deg;i<lim;i++) B[i]=0;
}
int a[maxn];
int main(){
scanf("%d%d%d",&n,&r,&k);
pre();
m=(n-1)/k;
for(rg int i=1;i<=m;i++) a[i]=jcc[k*i];
a[0]=1;
getinv(a,f,m+1);
for(rg int i=0;i<=m;i++) ans=addmod(ans,mulmod(f[i],jcc[n-k*i]));
ans=mulmod(ans,jc[n]);
ans=mulmod(ans,m&1?mod-1:1);
printf("%d\n",ans);
return 0;
}