70801202-AGC005

D

求数列 $A$ 的合法排列数满足 $\forall i\in(1,n) |p_i-i|\not =k$

考虑到 $\not =$ 并不容易计算，使用容斥转化为 $=$

设 $\Gamma_c$ 表示包含已知的 $c对=$ 的排列数量(其他位置任意)，而其他位置任意本质上就是全排列，即，对 $\Gamma_c$ 的贡献是 $(N-c)!$ 。由此，根据广义容斥，最终答案为 $\displaystyle{\sum_{c=0}^N (-1)^c \times \Gamma_c}$

转化问题为能选出多少对 $(i,a_i)$ 使 $|a_i-i|=K$ 且所有的 $i,a_i$ 分别互不相同 ，设选出 $\gamma_c$ ，则 $\Gamma_c=\gamma_c \times (N-c)!$

则最终答案是

$\sum_{c=0}^N (-1)^c\times (N-c)! \times \gamma_c$

注意这里下标与键值的对应关系，像匹配的定义，且可以将其转化成二分图模型：$G=(V_1,V_2 ; E)$，其中 $V_1={L_1,L_2,…,L_N} \ ,\ V_2={R_1,R_2,…,R_N} \ ,\ E={(L_i,R_j)\mid \ |i-j|=k}$ ，求 $E$ 有多少个 $K$ 的匹配

再考虑图 $G$ 的性质：

每个顶点度数不超过 $2$ ——因为 $L_i$ 至多与 $R_{i-k},R_{i+k}$ 相连，对 $R_i$ 同理
$G$ 为若干个链的并——证明没有圈：若有圈，则设最小者 $\min$ , 顶点式 $L_{\min}$ ，与之相连的节点 $L_{\min-k}$ 则不能在圈中，则度数不超过 $1$ ,与性质 $1$ 矛盾

所以求一个全由链组成的图 $G$ ，其大小为 $k$ 的匹配个数

考虑将这些链首尾相连，而连边则为强制不能加入匹配的坏边

问题转化到了链，$f_{i,j}$ 表示前 $i$ 条边，当前匹配大小为 $j$ ，且最后一条边没有匹配的方案数； $g_{i,j}$ 表示最后一条边匹配的方案数，转移时注意坏边以及相邻的边不能同时出现在匹配中

const int N=4e3+100;
const int mod=924844033;
int n,k,len;
int sp[N],fac[N],f[N][N],g[N][N];
ll ans;

inline void add(int &x,const int y){ x+=y-mod; x+=x>>31&mod;}

int main(){
    scanf("%d%d",&n,&k); fac[0]=1;
    for(rei i=1;i<=n;++i) fac[i]=(ll) fac[i-1]*i%mod;
    for(rei i=0;i<k;++i){
        sp[++len]=1,len+=(n-i-1)/k;
        sp[++len]=1,len+=(n-i-1)/k;
    }
    f[0][0]=1;
    for(rei i=1;i<=len;++i){
        f[i][0]=1;
        for(rei j=1;j<=(i+1)/2;++j){
            add(f[i][j]=f[i-1][j],g[i-1][j]);
            g[i][j]=sp[i] ? 0 : f[i-1][j-1];
        }
    }
    for(rei c=0;c<=n;++c){
        rei tmp=(ll) (f[len][c]+g[len][c])%mod*fac[n-c]%mod;
        c&1 ? ans-=tmp : ans+=tmp;
    }
    ans%=mod;
    printf("%d\n",ans+(ans>>63&mod));
    getchar(),getchar();
    return 0;
}

E

给定红蓝两棵树和起点，两人分别在两棵树上交替移动，相遇后（所在节点编号相同）游戏结束，现在 $A（红）$ 想最大化游戏轮数，$B（蓝）$ 想最小化游戏轮数，求游戏轮数

~~对抗搜索！（雾~~

首先考虑无解情况，即后手永远抓不到先手

如果存在一条红边 $(u,v)$ 且满足 $u,v$ 两点在蓝树上的距离 $\geq 3$ ，且先手能跑到 $u,v$ 点中任意一个且该回合内没有被抓到，则无解

先假设有解情况，即，先手可以走的红边的两端点在蓝树上距离 $\leq 2$ ，那么对于点 $u$ ，其与根的距离分别为 $len_红,len_蓝$ ，若 $len_红\leq len_蓝$ 那么红方一定不会走到 $u$ ，即红方每一次移动都要保证 $len_红>len_蓝$

$\therefore$ $\text{dfs}$ 一次找无解与满足 $len_红>len_蓝$ 的点，答案就是 $2\times \max len_红$ ，即最优决策是走到 $\max len_红$ 并原地等待

const int N=2e5+5;
struct Edge{
    int next,to;
    Edge(int next=0,int to=0):next(next),to(to){};
}edge[N<<2];
int ha[N],hb[N],tot;
int fa[N],hson[N],Size[N],top[N],depth[N];
int ans,cir,n,a,b;

inline void _add(int *head,int x,int y){ edge[++tot]=Edge(head[x],y);head[x]=tot;}
inline void add(int *head,int x,int y){ _add(head,x,y); _add(head,y,x);}

void dfs1(int x){
    Size[x]=1;
    for(rei i=hb[x];i;i=edge[i].next){
        rei y=edge[i].to; if(y==fa[x]) continue;
        depth[y]=depth[x]+1,fa[y]=x; dfs1(y),
        Size[x]+=Size[y],hson[x]=Size[ hson[x] ]>Size[y] ? hson[x] : y;
    }
}

inline int lca(int x,int y){
    while(top[x]!=top[y]){
        if(depth[ top[x] ]<depth[ top[y] ]) x^=y,y^=x,x^=y;
        x=fa[ top[x] ];
    }
    return depth[x]<depth[y] ? x : y;
}

inline int dis(int x,int y){ return depth[x]+depth[y]-2*depth[ lca(x,y) ];}

void dfs2(int x,int anc){
    top[x]=anc;
    if(hson[x]) dfs2(hson[x],anc);
    for(rei i=hb[x];i;i=edge[i].next){
        rei y=edge[i].to; if(y!=fa[x] && y!=hson[x]) dfs2(y,y);
    }
}

void escape(int x,int fa,int dep){
    ans=max(ans,depth[x]<<1);
    for(rei i=ha[x];i;i=edge[i].next){
        rei y=edge[i].to;
        if(dis(x,y)>2) cir=1;
        if(y==fa || dep+1>=depth[y]) continue;
        escape(y,x,dep+1);
    }
}

int main(){
    scanf("%d%d%d",&n,&a,&b);
    for(rei i=1,x,y;i<n;++i)
        scanf("%d%d",&x,&y),add(ha,x,y);
    for(rei i=1,x,y;i<n;++i)
        scanf("%d%d",&x,&y),add(hb,x,y);
    dfs1(b);dfs2(b,b);
    escape(a,0,0);
    printf("%d\n",cir ? -1 : ans);
    getchar(),getchar();
    return 0;
}

F

对于一颗树 $T=(V,E)$ ，对于非空子集 $S\subseteq V$ ，定义 $f(S)$ 表示包含 $S$ 中所有点的连通块大小的最小值，即，$f(S)=min{|U| \ \mid s\subseteq U\subseteq V,T |U|是连通图}$ ，对 $K:1\rightarrow n$ 分别求出 $\sum_{S\subseteq V,|S|=K} f(S)$ 的值

考虑每个点 $x$ 对答案的贡献，即总方案数减去不合法方案数

$\begin{aligned} f_i&=\sum_{x=1}^n\left(\binom{n}{i}-\sum_{\exists e(x,y)}\binom{size_y}{i} \right) \\ &=n\times \binom{n}{i} - \sum_{x=1}^m\times \sum_{\exists e(x,y)} \binom{size_y}{i} \\ \end{aligned}$

设 $cnt_i$ 为子树大小为 $i$ 的子树个数

$\begin{aligned} f_i&=n\times \binom{n}{i}-\sum_{j=i}^n cnt_j\times \binom{j}{i} \\ &=n\times \binom{n}{i}-\sum_{j=i}^n cnt_j\times \frac{j!}{i!\times (j-i)!} \\ &=n\times \binom{n}{i}-\frac{1}{i!}\sum_{j=i}^n\frac{cnt_j\times j!}{(j-i)!} \\ &=n\times \binom{n}{i}-\frac{1}{i!} \sum_{j=0}^{n-i}\frac{cnt_{i+j}\times (i+j)!}{j!} \\ \end{aligned}$

发现第二项是减法卷积，考虑 $NTT$

const int N=8e5+100;
const int mod=924844033,G=5;
ll n;
ll rev[N],f[N],g[N],fac[N],ifac[N],Size[N],cnt[N];
int head[N],tot,Next[N<<1],ver[N<<1];

inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}
inline ll qpow(ll x,ll y){ ll v=1; while(y){ if(y&1) v=v*x%mod; x=x*x%mod,y>>=1;} return v;}
inline int calc(int n){
    rei lim=1;
    while(lim<=n) lim<<=1;
    for(rei i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1) | ((i&1) ? lim>>1 : 0);
    return lim;
}

inline void NTT(ll *a,int lim,int type){
    for(rei i=0;i<lim;++i) if(i<rev[i]) swap(a[i],a[ rev[i] ]);
    for(rei len=1;len<lim;len<<=1){
        ll wn=qpow(G,(mod-1)/(len<<1));
        for(rei i=0;i<lim;i+=len<<1){
            ll w=1;
            for(rei j=i;j<i+len;++j,w=w*wn%mod){
                ll x=a[j],y=w*a[j+len]%mod;
                a[j]=(x+y)%mod,a[j+len]=(x-y+mod)%mod;
            }
        }
    }
    if(type==1) return;
    ll inv=qpow(lim,mod-2);
    for(rei i=0;i<lim;++i) a[i]=a[i]*inv%mod;
    reverse(a+1,a+lim);
}

inline void mul(ll *f,ll *g){
    rei lim=calc(n<<1);
    NTT(f,lim,1),NTT(g,lim,1);
    for(rei i=0;i<lim;++i) f[i]=f[i]*g[i]%mod;
    NTT(f,lim,-1);
}

void dfs(int x,int fa){
    Size[x]=1;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i];
        if(y==fa) continue;
        dfs(y,x),Size[x]+=Size[y];
    }
    ++cnt[ Size[x] ],++cnt[ n-Size[x] ];
}

inline ll get_C(ll n,ll m){ return fac[n]*ifac[m]%mod *ifac[n-m]%mod;}

inline void init(){
    fac[0]=ifac[0]=1;
    for(rei i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for(rei i=n-1;i;--i) ifac[i]=ifac[i+1]*(i+1)%mod;
}

int main(){
    scanf("%d",&n);
    init();
    for(rei i=1,x,y;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1,0);
    g[0]=1;
    for(rei i=1;i<=n;++i) f[i]=cnt[n-i]*fac[n-i]%mod,g[i]=ifac[i];
    mul(f,g),reverse(f,f+n+1);
    for(rei i=1;i<=n;++i) printf("%lld\n",(n*get_C(n,i)%mod-ifac[i]*f[i]%mod+mod)%mod);
    getchar(),getchar();
    return 0;
}