专栏文章

南京夜无电波讯号·题解

LLucyna_Kushinada
题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min48ii4
此快照首次捕获于
2025/12/01 20:18
3 个月前
此快照最后确认于
2025/12/01 20:18
3 个月前
查看原文
存在比较直接的组合意义优化做法，不过应喜欢的人的要求，但是这里也介绍一下期望做法。
先定义一些东西，
V(Tn)=∑i=1nsizei2\displaystyle V(T_n)=\sum_{i=1}^n size_i^2
fn=∑Tn∈UnV(Tn)\displaystyle f_n=\sum_{T_n\in U_n} V(T_n)
S(Tn)=∑i=1nsizei\displaystyle S(T_n)=\sum_{i=1}^n size_i
gn=∑Tn∈UnS(Tn)\displaystyle g_n=\sum_{T_n\in U_n} S(T_n)
组合做法的基本思路是拆贡献，分别对每个节点计算它取到某个 sizesize 时的方案数，然后再累加起来。
本题考察的核心在于 size2size^2 的那个指数，而在组合做法中变为了无足轻重、画蛇添足的败笔，出题人需要好好反思，但这并不意味着期望做法没有思维启发性。
在期望做法的视角下，size2size^2 的那个指数就变得比较难以处理，于是想到求解整体的变化量 fn−fn−1f_n-f_{n-1}，再递推求出答案，于是就有了 gng_n 与 S(Tn)S(T_n)。
sizeisize_i 会受到后面加入的节点的影响而变化，故考虑将 S(Tn)=∑i=1nsizei=∑i=1ndi\displaystyle S(T_n)=\sum_{i=1}^n size_i=\sum_{i=1}^n d_i，其中 did_i 表示 ii 号节点的深度（根节点深度为 11），原因显然，只不过是换了一种统计的方式。
那么 gn=∑Tn∈UnS(Tn)=∑Tn∈Un∑i=1ndi\displaystyle g_n=\sum_{T_n\in U_n} S(T_n)=\sum_{T_n\in U_n}\sum_{i=1}^n d_i，还是不太好做，考虑平均贡献，也就是期望，转化为 gn=(n−1)!∑i=1nE(di)\displaystyle g_n=(n-1)!\sum_{i=1}^n E(d_i)。
那么只需要求出 E(di)E(d_i)，有转移：
E(di)=∑j=1i−1E(dj)i−1+1\displaystyle E(d_i)=\frac{\sum_{j=1}^{i-1} E(d_j)}{i-1}+1
记 sn=∑i=1nE(di)\displaystyle s_n=\sum_{i=1}^n E(d_i)，则 gn=(n−1)!sng_n=(n-1)!s_n。
接下来考虑 fn−1→fnf_{n-1}\to f_n 的变化量，拆为 (n−1)fn−1(n-1)f_{n-1}（每棵 (n−1)(n-1) 个节点树都有 (n−1)(n-1) 种加点方法变为 nn 个节点的树），和节点 nn 带来的新变化：其到根的路径上的每个节点的 sizesize 都会加 11，同时它自己会有 11 的 sizesize。
考虑推一推后者的式子：
Δ=\Delta=
∑Tn−1∑i=1n−1[∑u∈path(i,1)[(sizeu+1)2−sizeu2]+1]\displaystyle \sum_{T_{n-1}}\sum_{i=1}^{n-1}[\sum_{u\in path(i,1)} [(size_u+1)^2-size_u^2]+1]
∑Tn−1∑i=1n−1[∑u∈path(i,1)(2sizeu+1)+1]\displaystyle \sum_{T_{n-1}}\sum_{i=1}^{n-1}[\sum_{u\in path(i,1)} (2size_u+1)+1]
∑Tn−1∑i=1n−1[2×∑u∈path(i,1)sizeu+di+1]\displaystyle \sum_{T_{n-1}}\sum_{i=1}^{n-1}[2\times\sum_{u\in path(i,1)} size_u+d_i+1]
2∑Tn−1∑i=1n−1∑u∈path(i,1)sizeu+∑Tn−1∑i=1n−1di+∑Tn−1∑i=1n−11\displaystyle 2\sum_{T_{n-1}}\sum_{i=1}^{n-1}\sum_{u\in path(i,1)}size_u+ \sum_{T_{n-1}}\sum_{i=1}^{n-1}d_i+\sum_{T_{n-1}}\sum_{i=1}^{n-1}1
考虑 sizeusize_u 那部分的实质，得到：
2∑Tn−1∑i=1n−1sizei2+gn−1+(n−2)!×(n−1)\displaystyle 2\sum_{T_{n-1}}\sum_{i=1}^{n-1}size_i^2+ g_{n-1}+(n-2)!\times (n-1)
2fn−1+gn−1+(n−1)!\displaystyle 2f_{n-1}+ g_{n-1}+(n-1)!
于是得到最终的递推式，
fn=f_n=
(n−1)fn−1+Δ(n-1)f_{n-1}+\Delta
(n+1)fn−1+gn−1+(n−1)!(n+1)f_{n-1}+g_{n-1}+(n-1)!
~完结撒花~。
CPP
#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()

#define N 1000010
#define int long long

const int mod=1e9+7;

inline int qpow(int a,int b=mod-2){
    int ans=1;

    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }

    return ans;
}

int n,fac[N],iv[N],s[N],g[N],f[N];

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;

    fac[0]=1;
    rep(i,1,n){
        fac[i]=fac[i-1]*i%mod;
    }

    iv[n]=qpow(fac[n]);
    per(i,0,n-1){
        iv[i]=iv[i+1]*(i+1)%mod;
    }
    rep(i,0,n){
        iv[i]=iv[i]*fac[i-1]%mod;
    }

    rep(i,1,n){
        s[i]=s[i-1]*iv[i-1]%mod+1;
        s[i]=(s[i-1]+s[i])%mod;

        g[i]=s[i]*fac[i-1]%mod;
    }

    f[1]=1;
    rep(i,2,n){
        f[i]=(i+1)*f[i-1]%mod+g[i-1]+fac[i-1];
        f[i]%=mod;
    }

    cout<<f[n]<<'\n';

    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...