Acwing 的latex会挂（是真的挂），建议去 我的博客

title: CSP2020联考 Day4
mathjax: true

CSP2020联考 Day4

这场质量挺好。

[HTML_REMOVED]

T1

有效的状态数就 $ \mathcal O(n^2) $ 个，记忆化之类的随便搞。

T2

给一个长度为 $ n $ 的序列 $ A $ ,删掉第 $ i $ 个元素的代价是 $ w_i $ .给一个长度为 $ m $ 的严格递增的序列 $ B $ ,若可以从 $ A $ 中选出一个子序列 $ Q $ ，使 $ \forall i\in [1,m],a_{q_i}=b_i $ ,且对于所有选出的元素，A中其左侧元素都要小于该元素，没有被选出的元素左侧至少有一个元素不小于该元素，则称A是好的。由于可能办不到，因此允许你删掉一些元素使得剩下的序列是好的，最小化代价和.[HTML_REMOVED]

$ m\le n\le 5\times 10^6,a_i,b_i\in [1,n],\forall 1\le i<m,b_i<b_{i+1},|w_i|\le 10^9 $

60pts: $ nm\le 5\times 10^6 $ . [HTML_REMOVED]
这部分非常简单：考虑dp。令 $ f(i,j) $ 表示考虑A的前 $ i $ 个元素，匹配到B的第 $ j $ 个元素的最小代价。

考虑 $ a_i>b_j $ 时只能删掉，否则可以保留， 可得转移:
$$ \begin{equation} \begin{aligned} f(i,j)&=f(i-1,j)+w_i\ (\text{if }a_i>b_j)\\ f(i,j)&=f(i-1,j)+\min(0,w_i)\ (\text{if }a_i\le b_j)\\ f(i,j)&=f(i-1,j-1)\ (\text{if }a_i=b_j) \end{aligned} \end{equation} $$
注意2,3两个转移方程的条件有重叠的部分，即对于 $ a_i=b_j $ 时两个转移都要做。[HTML_REMOVED]
复杂度 $ \mathcal O(nm) $ .

100pts：【树状数组优化dp】

大段的转移都是相同的，只有 $ a_i=b_j $ 时比较特别。对值域建树状数组维护这个dp就行，区间加，单点查询， $ a_i=b_j $ 的就暴力改。[HTML_REMOVED]
令人震惊的是卡卡常这个 $ \mathcal O(n\log n) $ 的算法就过了。。。果然算法的运行效率和复杂度关系不大，关键在于有没有信仰

(然后这个彩笔想到这里之后（当然没想到卡常就能A了）突然想到了每次取最早位置的贪心，然后居然过了所有大样例，最后就只剩53pts了。。。)

线性的正解是有的，但出题人也没给证明什么的，边上用这种方法过了的同学也支支吾吾说不清楚,就没写。

卡过去的 $ \mathcal O(n\log n) $ 代码：Link

T3

给一棵 $ n $ 个点的树，定义从 $ x $ 随机游走到 $ y $ 的期望步数为 $ f(x,y) $ .给一个参数 $ m $ ,求 $ \sum_{x=1}^n\sum_{y=1}^nf^m(x,y)\ (mod\ 998244353) $ [HTML_REMOVED]
$ n\le 3\times 10^4,1\le m\le 500 $

44pts: $ n\le 30,m\le 50 $ .

考虑枚举根 $ R $ 计算贡献。记 $ f(u) $ 表示 $ u $ 走到根的期望步数,则有 $ f(u)=1+\frac{f(v)+\sum_{v\in son(u)}f(v)}{deg} $ [HTML_REMOVED]
( $ deg $ 表示 $ u $ 的度数， $ son(u) $ 表示 $ u $ 的儿子集合，下同。)

那么 $ R $ 的贡献就是 $ \sum_{u}f^m(u) $ .大力高斯消元，复杂度 $ \mathcal O(n^4\log mod) $ .

88pts: $ n\le 3000,m\le 50 $ . 【树上高斯消元】

使用树上高斯消元可做到每次复杂度 $ \mathcal O(n\log mod) $ ,总复杂度 $ O(n^2\log mod) $ .[HTML_REMOVED]
我的 这篇博客 介绍了树上高斯消元。

100pts: $ n\le 3\times 10^4,m\le 500 $ . 【树上高斯消元】【猜结论+推式子】【换根dp】【树上差分】【容斥+推式子】【卷积， $ \text{NTT} $ 】

这部分就真的很神了，不知道再过多久能到当场做出这部分的水平。

官方题解各种错搞的我琢磨了很久，因此我尽量写详细些(如果有错请联系我)

由于 $ n $ 较大，不能枚举根了。考虑所有路径的贡献。
$$ ans=\sum_{x=1}^n\sum_{y=1}^n(f(x,\text{LCA}(x,y))+f(\text{LCA}(x,y),y))^m $$
用树上差分把式子拆开，记LCA为 $ a $ .（为方便，令根为1，这不影响答案）
$$ ans=\sum_{x=1}^n\sum_{y=1}^n(f(x,1)+f(1,y)-f(a,1)-f(1,a))^m $$
记 $ s_x=f(x,1),t_x=f(1,x),st_x=f(x,1)+f(1,x) $ , $ sub(a) $ 为 $ a $ 的子树，则
$$
\begin{equation}
\begin{aligned}
ans&=\sum_{x=1}^n\sum_{y=1}^n(s_x+t_y-st_a)^m\
&=\sum_{a=1}^n\sum_{x\in sub(a)}^n\sum_{y\in sub(a)}^n(s_x+t_y-st_a)^m[x,y\text{属于}a\text{的不同子树}]\
&=\sum_{a=1}^n\sum_{x\in sub(a)}^n\sum_{y\in sub(a)}^n\sum_{i=0}^mC_m^i(-st_a)^{m-i}\sum_{j=0}^iC_i^js_x^{i-j}t_y^j[x,y\text{属于}a\text{的不同子树}]\
&=\sum_{a=1}^n\sum_{i=0}^mC_m^i(-st_a)^{m-i}\sum_{j=0}^iC_i^j\sum_{x\in sub(a)}s_x^{i-j}\sum_{y\in sub(a)}t_y^j[x,y\text{属于}a\text{的不同子树}] \

\end{aligned}
\end{equation}
$$ 用容斥搞掉后面那个麻烦的条件： $$
\sum_{a=1}^n\sum_{i=0}^mC_m^i(-st_a)^{m-i}((\sum_{j=0}^iC_i^j\sum_{x\in sub(a)}s_x^{i-j}\sum_{y\in sub(a)}t_y^j)-(\sum_{j=0}^iC_i^j\sum_{b\in son(a)}\sum_{x\in sub(b)}s_x^{i-j}\sum_{y\in sub(b)}t_y^j))
$$
然而官方题解到这里就结束了

记 $ sum(a,x)=\sum_{j=0}^iC_i^j\sum_{x\in sub(a)}s_x^{i-j}\sum_{y\in sub(a)}t_y^j,ff(a,x)=sum(a,x)-\sum_{b\in son(u)}sum(b,x) $

那么最后就是
$$ \sum_{a=1}^n\sum_{i=0}^mC_m^i(-st_a)^{m-1}ff(a) $$
式子推到这里就差不多了，接下来是求 $ sum(a,x),ff(a,x) $ .这之前我们要求 $ s_x,t_x $ .[HTML_REMOVED]
$ s_x $ 之前已经提到了，可以树上高斯消元解决。 $ t_x $ 可以换根dp解决，，，吗？[HTML_REMOVED]
树上高斯消元显然不是个可以换根dp的形式。但是神仙告诉我，树上 $ u $ 随机游走到 $ fa $ 的期望步数就是 $ u $ 的子树内所有点的度数和！！那就很容易换根dp了，然后求链上的前缀和就好（在文末Extend部分，我提供了一种基于归纳法的证明）

知道 $ s_x,t_x $ 之后可以暴力 $ \mathcal O(n^2m^2) $ 求所有 $ sum(a,x) $ .考虑把组合数拆开，是
$$ sum(a,x)=i!\sum_{j=0}^i\frac{\sum_{x\in sub(a)}s_x^{i-j}}{(i-j)!}*\sum_{j=0}^i\dfrac{\sum_{y\in sub(a)}t_y^j}{j!} $$

$ {\sum_{y\in sub(a)}t_y^j} $ 是个子树和的形式。枚举指数 $ j $ ，对所有点都求出来（顺便除掉 $ j! $ ，前面的 $ s_x^{i-j} $ 也同理），记为 $ vals(u,x),valt(u,x) $ .这部分复杂度是 $ \mathcal O(nm) $ . 那就变成 $ i!\sum_{j=0}^i vals(u,i-j)*valt(u,j) $ .[HTML_REMOVED]
直接做已经可以 $ \mathcal O(nm^2) $ .注意到模数是998244353.上 $ \text{NTT} $ 就好。复杂度 $ \mathcal O(nm\log m) $ .

最后的答案 $ \sum_{a=1}^n\sum_{i=0}^mC_m^i(-st_a)^{m-1}ff(a) $ 直接暴力。总复杂度 $ \mathcal O(nm\log m) $ .瓶颈在 $ \text{NTT} $ .

/**********/
const ll mod=998244353;
ll Qpow(ll a,ll p)
{
    ll res=1;
    while(p)
    {
        if(p&1)res=res*a%mod;
        a=a*a%mod,p>>=1;
    }
    return res;
}
ll Inv(ll x){return Qpow(x,mod-2);}
ll upd(ll x){return (x%mod+mod)%mod;}
void Add(ll& a,ll b){a=(a+b>=mod?a+b-mod:a+b);}
void Add(int& a,int b){a=(a+b>=mod?a+b-mod:a+b);}
int reduce(int x){return x>=mod?x-mod:x;}
namespace Conv
{
    #define MAXM 2011
    int status[MAXM],len;
    ll RT[MAXM],IRT[MAXM];
    void init(int n)
    {
        len=1;
        while(len<=n+n)len<<=1;
        for(int i=0;i<len;++i)
            status[i]=((status[i>>1]>>1)+((i&1)*(len>>1)));
        for(int i=1;i<len;i<<=1)
        {
            ll R=Qpow(3,(mod-1)/(i<<1));
            RT[i]=1;
            for(int j=1;j<i;++j)RT[i+j]=RT[i+j-1]*R%mod;
            R=Inv(R);
            IRT[i]=1;
            for(int j=1;j<i;++j)IRT[i+j]=IRT[i+j-1]*R%mod;
        }
    }
    void DFT(int* a,int type)
    {
        for(int i=0;i<len;++i)
            if(status[i]>i)std::swap(a[i],a[status[i]]);
        for(int cur=1;cur<len;cur<<=1)
            for(int j=0;j<len;j+=cur<<1)
                for(int k=0;k<cur;++k)
                {
                    ll x=a[j+k],y=a[j+cur+k]*(type==1?RT[cur+k]:IRT[cur+k])%mod;
                    a[j+k]=reduce(x+y),a[j+cur+k]=reduce(x-y+mod);
                }
        if(type==-1)
        {
            ll inv_len=Inv(len);
            for(int i=0;i<len;++i)a[i]=a[i]*inv_len%mod;
        }
    }
    void Mul(int* a,int* b,int* res)
    {
        DFT(a,1),DFT(b,1);
        for(int i=0;i<len;++i)res[i]=1ll*a[i]*b[i]%mod;
        DFT(res,-1);
    }
    #undef MAXM
}
#define MAXN 30011
#define MAXM 511
struct edge{int v,nxt;}e[MAXN<<1|1];
int cnt=0,last[MAXN],deg[MAXN];
void adde(int u,int v){++deg[v], e[++cnt].v=v,e[cnt].nxt=last[u],last[u]=cnt;}

ll A[MAXN],B[MAXN],f[MAXN],g[MAXN],fg[MAXN];
void dfs1(int u,int fa=0)
{
    f[u]=deg[u];
    for(int i=last[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs1(v,u),f[u]+=f[v];
    }
    if(!fa)f[u]=0;
}
void dfs2(int u,int fa=0)
{
    ll sum=0;
    for(int i=last[u];i;i=e[i].nxt)
        if(e[i].v!=fa)Add(sum,f[e[i].v]);
    for(int i=last[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        g[v]=upd(sum-f[v]+g[u]+deg[u]);
        dfs2(v,u);
    }
}
void dfs3(int u,int fa=0)
{
    fg[u]=reduce(f[u]+g[u]);
    for(int i=last[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        Add(f[v],f[u]),Add(g[v],g[u]);
        dfs3(v,u);
    }
}
ll ans=0;
ll fac[MAXN],fac_inv[MAXN];
int valS[MAXN][MAXM],valT[MAXN][MAXM],ff[MAXN][MAXM], n,m;
void prework()
{
    fac[0]=fac_inv[0]=1;
    for(int i=1;i<=m;++i)fac[i]=fac[i-1]*i%mod,fac_inv[i]=Inv(fac[i]);
}
void dfs4(int u,int fa=0)
{
    for(int i=last[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs4(v,u);
        for(int x=0;x<=m;++x)Add(valS[u][x],valS[v][x]),Add(valT[u][x],valT[v][x]);
    }
}
void dfs5(int u,int fa=0)
{
    for(int i=last[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        for(int x=0;x<=m;++x)ff[u][x]=(ff[u][x]-ff[v][x])%mod;
        dfs5(v,u);
    }
}
int main()
{
    n=read(),m=read();
    Conv::init(m);
    for(int i=1;i<n;++i){int u=read(),v=read();adde(u,v),adde(v,u);}
    dfs1(1),dfs2(1),dfs3(1);
    prework();
    for(int u=1;u<=n;++u)
    {
        ll cur=1;
        for(int x=0;x<=m;++x)valS[u][x]=cur*fac_inv[x]%mod,cur=cur*f[u]%mod;
        cur=1;
        for(int x=0;x<=m;++x)valT[u][x]=cur*fac_inv[x]%mod,cur=cur*g[u]%mod;
    }
    // puts("----");
    dfs4(1);
    for(int u=1;u<=n;++u)
    {
        Conv::Mul(valS[u],valT[u],ff[u]);
        for(int x=0;x<=m;++x)ff[u][x]=ff[u][x]*fac[x]%mod;
    }
    dfs5(1);
    ll ans=0;
    for(int u=1;u<=n;++u)
    {
        ll cur=1;
        for(int x=m;x>=0;--x)Add(ans,upd(cur*fac_inv[m-x]%mod*ff[u][x]%mod*fac_inv[x])),cur=cur*(-fg[u])%mod;
    }
    printf("%lld\n",upd(ans*fac[m]));
    return 0;
}

Extend:

$ \text{Lemma :} f(x,fa(x))=\sum_{y\in sub(x)} deg(y) $

$ \text{Proof:} $ 归纳。

$ x $ 是叶子显然成立。

已知对 $ x $ 的子树成立，证明对 $ (x,fa(x)) $ 也成立：边 $ (x,fa(x)) $ 的贡献为1.边 $ (x,v)\ (v\in son(x)) $ 被经过的期望次数为 $ \frac{1}{deg(x)-1}(\sum_{i=0}(\frac{deg-2}{deg-1})^i)=1 $ .又已知对 $ v $ 及其子树成立，故 $ v $ 的子树的贡献为 $ 1+\sum_{k\in sub(v)}deg(v) $

故
$$ \begin{equation} \begin{aligned} f(x,fa(x))&=1+\sum_{v\in son(y)}(1+\sum_{k\in sub(v)}deg(v))\\ &=deg(x)+\sum_{v\in son(x)}\sum_{k\in sub(v)}deg(k)=\sum_{y\in sub(x)} deg(y) \end{aligned} \end{equation} $$

Q.E.D.