70801202-AGC005

D

求数列 $A$ 的合法排列数满足 $\forall i \in (1, n) | p_{i} - i | \neq k$

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

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

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

则最终答案是

\sum_{c = 0}^{N} (- 1)^{c} \times (N - c)! \times γ_{c}

注意这里下标与键值的对应关系，像匹配的定义，且可以将其转化成二分图模型： $G = (V_{1}, V_{2}; E)$ ，其中 $V_{1} = L_{1}, L_{2}, \dots, L_{N}, V_{2} = R_{1}, R_{2}, \dots, R_{N}, E = (L_{i}, R_{j}) ∣ | 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$ ，其与根的距离分别为 $l e n_{红}, l e n_{蓝}$ ，若 $l e n_{红} \leq l e n_{蓝}$ 那么红方一定不会走到 $u$ ，即红方每一次移动都要保证 $l e n_{红} > l e n_{蓝}$

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

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) = m i n | U | ∣ s \subseteq U \subseteq V, T | U | 是连通图$ ，对 $K : 1 \to n$ 分别求出 $\sum_{S \subseteq V, | S | = K} f (S)$ 的值

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

\begin{aligned} f_{i} & = \sum_{x = 1}^{n} ((\binom{n}{i}) - \sum_{\exists e (x, y)} (\binom{s i z e_{y}}{i})) \\ = n \times (\binom{n}{i}) - \sum_{x = 1}^{m} \times \sum_{\exists e (x, y)} (\binom{s i z e_{y}}{i}) \end{aligned}

设 $c n t_{i}$ 为子树大小为 $i$ 的子树个数

\begin{aligned} f_{i} & = n \times (\binom{n}{i}) - \sum_{j = i}^{n} c n t_{j} \times (\binom{j}{i}) \\ = n \times (\binom{n}{i}) - \sum_{j = i}^{n} c n t_{j} \times \frac{j!}{i! \times (j - i)!} \\ = n \times (\binom{n}{i}) - \frac{1}{i!} \sum_{j = i}^{n} \frac{c n t_{j} \times j!}{(j - i)!} \\ = n \times (\binom{n}{i}) - \frac{1}{i!} \sum_{j = 0}^{n - i} \frac{c n t_{i + j} \times (i + j)!}{j!} \end{aligned}

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

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;
}