ZR2020 提高十联测 day1

Author： RainAir
发布时间：August 30, 2020
1079views
No comments
3045 words
Categories：题解

这场早上 vp 了一下，发现 AB 都是 sb 题。。。但是因为 A 一开始算错了复杂度搞了一个~~吊打 std~~的复杂度花了将近 2h。。考试的时候还很自闭为什么自己提高组 T1 不会做。。导致 C 没有思考时间了。

期望得分 $220$，实际得分 $200$ （因为咕了 T3 的暴力没写）

A

首先看一下这个式子：$3k^2-3k+1$，常数项看起来就很不舒服，加上 Hint 里面的答案 $\leq 8$ 的提示，我们考虑去枚举答案 $x$。所以现在相当于变成了问你 $n-x$ 是否能用 $x$ 个 $3k^2+3k$ 组成。然后提一下系数，变成了问你 $\frac{n-x}{3}$ 是否能用 $x$ 个 $k^2-k$ 组成（显然这里需要满足 $3 | n-x$）。

这样只能把答案大小缩小到三个，虽然用下面的方法也可以通过本题，但是我们不失一般性看看能不能再缩一下：我们发现 $k^2-k$ 一定是个偶数（因为 $k^2$ 和 $k$ 奇偶性相同），所以化一下系数，现在问题变成了 $\frac{n-x}{6}$ 是否能用 $x$ 个 $\binom k 2$ 组成（同样需要满足 $6|n-x$），这样你就只有两个数需要判断了。

$\binom k 2$ 叫做三角形数，比赛的时候我是打表发现如果 $x \geq 3$ 一定可以组成所有的自然数（你就把循环上界不断提高，看看最小的数是否变化就好了，赛后发现这个是费马多边形数定理的一个特例，证明非常难幸亏没有头铁）。如果 $x=0$，显然只有 $n=0$ 满足条件。$x=1$ 可以通过解方程判断根是否是个整数即可。现在我们主要的目标在于 $x=2$。

题解的做法：注意到有用的三角形数只有 $\sqrt n$ 个，直接处理出来然后双指针扫一遍，出题人说双指针常数很小就过了，我是不太懂。虽然我开场就想到了这个做法，但是还是不会算复杂度而暴毙（NOI D1T1 梦幻复刻）。

我的做法：先把不能表示的数字打表，发现一个定理（至今不会证明）

$$ n = \binom x 2 + \binom y 2 \Leftrightarrow \exists a,b \in \mathbb{Z},4n+1 = a^2+b^2 $$

于是现在我们要快速判断一个数能否被两个平方数表示出来。相当于是一个圆上的整点问题，问半径是 $\sqrt {4n+1}$ 的圆上是否有整点。根据复平面和高斯整数的那一套理论可以得到结论：

中间步骤

我们考虑在复平面上研究这个问题。一个数$a+bi$ 所代表的点的距离就是乘上它的共轭$a-bi$，$a,b$ 都是整数这样的数叫做高斯整数
所以现在相当于问对于 $n$ 有多少种方式能分解成两个共轭的乘积。
类比整数我们把高斯整数尝试分解成若干高斯质数的乘积。怎么方便的分解呢？拿25举例，我们首先写出普通的分解：$25 = 5*5$
我们这里给出一个结论：所有形如 $4n+1$ 的质数都可以被分解，而 $4n+3$ 的都不可以被分解。
那么我们发现 $5 = (2+i)(2-i)$ 相当于有 $25 = (2+i)(2-i)(2+i)(2-i)$。
考虑将其任意组合可以得到 $3$ 种情况。但是我们还是要注意对于一个合法的方案 $a+bi$ 那么乘上 $1,-1,i,-i$ 都是合法的，所以方案数乘 $4$。就是 $12$ 种。
同时如果其中有形如 $4n+1$
且出现了奇数次的话就不能被拆分成两个共轭的积。出现了偶数次就没有贡献。
每一个有贡献的数的贡献是指数+1 最后乘起来。最后乘4就好了。
发现虽然 $2=(1-i)(1+i)$ 但是$2$ 放在哪里的贡献在最后的乘4算掉了所以不需要算$2$的贡献。

现在引入一个新函数 $\chi(n)$
如果 $n = 4k+1,k \in \mathbb{N}$ 那么 $\chi(n) = 1$
如果 $n = 4k+3,k \in \mathbb{N}$ 那么 $\chi(n) = -1$
其他情况 $\chi(n) = 0$ 就是按照$\bmod 4$ 的结果分类。
它是一个完全积性函数。
现在结果相当于可以写成质因数分解后 $$4\prod_{i}\sum_{j=0}^{e_i} \chi(p_i^{j})$$。

预处理 $< \sqrt n$ 的数字，质因数分解就可以回答询问了。复杂度 $O(Tn^{0.35})$（看网上说试除每一个素数复杂度是这个）。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 4e5 + 5;

bool p[MAXN];
int prime[MAXN],cnt;

inline void prework(){
    FOR(i,2,MAXN-1){
        if(!p[i]) prime[++cnt] = i;
        for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){
            p[i*prime[j]] = 1;
            if(!(i%prime[j])) break;
        }
    }
}

inline int f(LL x){
    if(x%4 == 1) return 1;
    if(x%4 == 3) return -1;
    return 0;
}

inline bool pd(LL x){
    x = 4*x+1;
    LL q = std::sqrt(1.0*x);
    FOR(i,1,cnt){
        if(prime[i] > x) break;
        if(prime[i] > q) break;
        if(x%prime[i]) continue;
        LL t = 0;
        while(!(x%prime[i])) x /= prime[i],++t;
        LL sm = f(1),tt = 1;
        FOR(xx,1,t) tt *= prime[i],sm += f(tt);
        if(!sm) return 1;
    } 
    return 0;
}

inline bool chk(LL n,int x){
    if(x >= 3) return 1;
    if(x == 2) return !pd(n);
    if(x == 0) return n==0;
    n *= 2;
    LL q = std::sqrt(1ll*4*n+1);
    if(q*q != 4*n+1) return 0;
    if((q-1)%2) return 0;
    return 1;
}

int main(){
    prework();
    int T;scanf("%d",&T);
    while(T--){
        LL n;scanf("%lld",&n);
        FOR(x,1,8){
            if((n-x)%6) continue;
            if(chk((n-x)/6,x)){
                printf("%d\n",x);
                break;
            }
        }
    }
    return 0;
}

B

如果你做过 CF1394E，从

CF1394 题解

A我们把天数分成会被禁言和不会被禁言的两类，首先如果选择了禁言的那些天我们一定会去选择最大的那些。于是我们枚举选前...

中的引理一就可以知道形成 X-Y-X 串所需要的充要条件是什么。

然后我们考虑两个偶回文中心 $x,y(x > y)$，设回文半径是 $r_x,r_y$，这两个回文串能生成一个 X-Y-X 串，当且仅当：

$$ \min\{r_x,r_y\} \geq x-y $$

拆开写也就是：

$$ \begin{aligned} r_x \geq x-y\\ r_y \geq x-y \end{aligned} $$

我们考虑枚举 $x$，于是限制可以进一步写成：

$$ \begin{aligned} x > y \geq x-r_x\\ r_y+y \geq x \end{aligned} $$

相当于平面上有点 $(y,r_y+y)$，每次查询矩形 $[x-r_x,x)\times[x,\infty]$，直接二维数点就好了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 4e6 + 5;
const int MAXM = 2e6 + 5;
char str[MAXN],a[MAXN];
int R[MAXN],n,N,r[MAXN];

inline void manacher(){
    int mx = 0,mid = 0;
    FOR(i,1,N){
        if(mx > i) R[i] = std::min(R[2*mid-i],R[mid]+mid-i);
        else R[i] = 1;
        while(a[i-R[i]] == a[i+R[i]]) ++R[i];
        if(i+R[i] > mx){
            mx = i+R[i];mid = i;
        }
    }
}

struct BIT{
    int tree[MAXM];
    #define lowbit(x) ((x)&(-(x)))

    inline void add(int pos,int x){
        pos += 2;
        while(pos < MAXM){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }

    inline int calc(int pos){
        int res = 0;pos += 2;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }

    inline int query(int l,int r){
        return calc(r)-calc(l-1);
    }
}bit;

std::set<P> S;

inline void add(int x){
    S.insert(MP(x+r[x],x));
    bit.add(x,1);
}

inline void upd(int x){
    while(!S.empty() && (*S.begin()).fi < x){
        bit.add((*S.begin()).se,-1);
        S.erase(S.begin());
    }
}

int main(){
//    freopen("B.in","r",stdin);
//    freopen("B.out","w",stdout);
    scanf("%s",str+1);n = strlen(str+1);
    a[N = 0] = '#';a[N = 1] = '$';
    FOR(i,1,n) a[++N] = str[i],a[++N] = '$';
    manacher();int t = 0;
    FOR(i,1,N) if(a[i] == '$') r[++t] = R[i]/2;
    LL ans = 0;
    FOR(i,1,t){
        upd(i);
        ans += bit.query(i-r[i],i);
        add(i);
    }
    printf("%lld\n",ans);
    return 0;
}

C

首先注意一个细节：随机一棵树的深度的期望是 $O(\sqrt n)$ 的！！！

只有随机保证 $f_i < i$ 的树深度期望才是 $O(\log n)$ 的。

考试的时候想到的地方：首先根据期望的线性性我们拆成对于每一个点 $x$ 计算它最终的值是什么，发现只和它到根的那些点的操作顺序有关系。我们继续拆成枚举它的一个祖先 $y$，$y$ 对应的权值期望在 $x$ 上加了多少次，知道这个就可以做了。

而我们发现这个期望加了多少次显然只和长度有关，所以我们设 $f_i$ 表示 $i$ 期望被 $1$ 加了多少次。

首先我们考虑对于一个确定的排列如何算答案：可以发现答案等价于这个排列以 $1$ 开始的上升序列个数。

证明

首先在 $1$ 前面的数没有任何贡献，所以我们只考虑从 $1$ 开始的情况。

注意到对于每一个上升序列 $1\to a \to \ldots \to b$，我们可以理解成是一个从 $1$ 开始的贡献沿着这条链走走到了 $b$，然后通过在 $b$ 这一次操作全都加给 $i$。很容易证明这能建立双射。其实也可以理解成我们每次只能按照以下两种规则从 $1$ 行动：

往后走
只能走到比当前数大的位置

每一条路径都对应了让某个数 $+1$，在每一条路径的终点都对应着对这个终点的操作导致让 $i$ 加上这个终点的所有贡献，而我们可以把贡献拆成每条路径分开贡献。

所以 $f_i$ 就是所有 $i!$ 种排列上升序列的个数和的期望。

计算上升序列的个数和很简单，只需要枚举一个上升序列的长度 $d$，就有

$$ f_i = \frac{1}{n!}\sum_{d=1}^i \binom {i-1} {d-1} \binom i d (i-d)! $$

第一项是选出值域，第二项是决定放在整个序列的哪个地方，第三项表示剩下的数可以随便排。

然后就可以用 $f_i$ 去计算每个点被期望加了多少次，就可以去计算每个点的期望值了。

注意计算一个长度为 $d$ 的序列的期望值的时候要考虑 $d+1\ldots n$ 的放置关系，相当于再乘上一个排列数。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

int n,a[MAXN];
int fa[MAXN],m;

inline void dfs(int v,int d=1){
    m = std::max(m,d);
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa[v]) continue;
        fa[e[i].to] = v;dfs(e[i].to,d+1);
    }
}

int f[MAXN],fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int main(){
    prework();
    scanf("%d",&n);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    FOR(i,1,n) scanf("%d",a+i);
    dfs(1);
    f[0] = 1;
    FOR(i,1,m){
        FOR(j,1,i){
            (f[i] += 1ll*C(i-1,j-1)*C(i,j)%ha*fac[i-j]%ha) %= ha;
        }
    }
    int ans = 0;
    FOR(i,1,n) (ans += 1ll*fac[n]*a[i]%ha)%=ha;
    FOR(i,1,n){
        int x = i,d = 1;
        while(x){
            (ans += 1ll*f[d]*a[x]%ha*C(n,n-d)%ha*fac[n-d]%ha) %= ha;
            x = fa[x];d++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Bonus：不随机怎么做

首先我们要先解决如何快速算

$$ f_i = \frac{1}{n!}\sum_{d=1}^i \binom {i-1} {d-1} \binom i d (i-d)! $$

拆一下式子可以得到：

$$ \begin{aligned} f_i &= \frac{1}{n!}\sum_{d=1}^i \frac{(i-1)!}{(d-1)!(i-d)!}\frac{i!}{d!(i-d)!}(i-d)!\\ &= \frac{1}{n!}i!(i-1)!\sum_{d=1}^i \frac{1}{(d-1)!d!}\frac{1}{(i-d)!} \end{aligned} $$

直接 NTT 即可。

然后考虑如何算每个点的贡献。我们考虑点分治。点分治的时候这个点分成的若干连通块中我们找到连向 $1$ 号点的那个（是所有点的父亲），然后发现一对点 $(u,v)(d_u < d_v)$ 对答案的贡献实际上是：

$$ f_{d_v-d_u} a_u \binom n {d_v-d_u} (n-(d_v-d_u))! $$

我们只考虑经过分治点的所有点对的答案，相当于两个多项式做个卷积，第 $i$ 项表示 $d_v-d_u= i$，就可以直接算答案了。复杂度应该是 $O(n \log^2 n)$ 的？

如果上面有错误请在评论区指出，都是我口胡的。

总结：还是自己不会算时间复杂度，不过没有挂题很开心~~（如果拍了 1000 组还挂的话那我就真的菜成狗了）~~

Last modification：September 13th, 2020 at 08:59 pm

如果觉得我的文章对你有用，请随意赞赏

ZR2020 提高十联测 day1

RainAir • 2020 年 08 月 30 日

期望得分 $220$，实际得分 $200$ （因为咕了 T3 的暴力没写）

A

我的做法：先把不能表示的数字打表，发现一个定理（至今不会证明）

$$ n = \binom x 2 + \binom y 2 \Leftrightarrow \exists a,b \in \mathbb{Z},4n+1 = a^2+b^2 $$

中间步骤

预处理 $< \sqrt n$ 的数字，质因数分解就可以回答询问了。复杂度 $O(Tn^{0.35})$（看网上说试除每一个素数复杂度是这个）。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 4e5 + 5;

bool p[MAXN];
int prime[MAXN],cnt;

inline void prework(){
    FOR(i,2,MAXN-1){
        if(!p[i]) prime[++cnt] = i;
        for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){
            p[i*prime[j]] = 1;
            if(!(i%prime[j])) break;
        }
    }
}

inline int f(LL x){
    if(x%4 == 1) return 1;
    if(x%4 == 3) return -1;
    return 0;
}

inline bool pd(LL x){
    x = 4*x+1;
    LL q = std::sqrt(1.0*x);
    FOR(i,1,cnt){
        if(prime[i] > x) break;
        if(prime[i] > q) break;
        if(x%prime[i]) continue;
        LL t = 0;
        while(!(x%prime[i])) x /= prime[i],++t;
        LL sm = f(1),tt = 1;
        FOR(xx,1,t) tt *= prime[i],sm += f(tt);
        if(!sm) return 1;
    } 
    return 0;
}

inline bool chk(LL n,int x){
    if(x >= 3) return 1;
    if(x == 2) return !pd(n);
    if(x == 0) return n==0;
    n *= 2;
    LL q = std::sqrt(1ll*4*n+1);
    if(q*q != 4*n+1) return 0;
    if((q-1)%2) return 0;
    return 1;
}

int main(){
    prework();
    int T;scanf("%d",&T);
    while(T--){
        LL n;scanf("%lld",&n);
        FOR(x,1,8){
            if((n-x)%6) continue;
            if(chk((n-x)/6,x)){
                printf("%d\n",x);
                break;
            }
        }
    }
    return 0;
}

B

如果你做过 CF1394E，从

CF1394 题解

A我们把天数分成会被禁言和不会被禁言的两类，首先如果选择了禁言的那些天我们一定会去选择最大的那些。于是我们枚举选前...

中的引理一就可以知道形成 X-Y-X 串所需要的充要条件是什么。

然后我们考虑两个偶回文中心 $x,y(x > y)$，设回文半径是 $r_x,r_y$，这两个回文串能生成一个 X-Y-X 串，当且仅当：

$$ \min\{r_x,r_y\} \geq x-y $$

拆开写也就是：

$$ \begin{aligned} r_x \geq x-y\\ r_y \geq x-y \end{aligned} $$

我们考虑枚举 $x$，于是限制可以进一步写成：

$$ \begin{aligned} x > y \geq x-r_x\\ r_y+y \geq x \end{aligned} $$

相当于平面上有点 $(y,r_y+y)$，每次查询矩形 $[x-r_x,x)\times[x,\infty]$，直接二维数点就好了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 4e6 + 5;
const int MAXM = 2e6 + 5;
char str[MAXN],a[MAXN];
int R[MAXN],n,N,r[MAXN];

inline void manacher(){
    int mx = 0,mid = 0;
    FOR(i,1,N){
        if(mx > i) R[i] = std::min(R[2*mid-i],R[mid]+mid-i);
        else R[i] = 1;
        while(a[i-R[i]] == a[i+R[i]]) ++R[i];
        if(i+R[i] > mx){
            mx = i+R[i];mid = i;
        }
    }
}

struct BIT{
    int tree[MAXM];
    #define lowbit(x) ((x)&(-(x)))

    inline void add(int pos,int x){
        pos += 2;
        while(pos < MAXM){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }

    inline int calc(int pos){
        int res = 0;pos += 2;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }

    inline int query(int l,int r){
        return calc(r)-calc(l-1);
    }
}bit;

std::set<P> S;

inline void add(int x){
    S.insert(MP(x+r[x],x));
    bit.add(x,1);
}

inline void upd(int x){
    while(!S.empty() && (*S.begin()).fi < x){
        bit.add((*S.begin()).se,-1);
        S.erase(S.begin());
    }
}

int main(){
//    freopen("B.in","r",stdin);
//    freopen("B.out","w",stdout);
    scanf("%s",str+1);n = strlen(str+1);
    a[N = 0] = '#';a[N = 1] = '$';
    FOR(i,1,n) a[++N] = str[i],a[++N] = '$';
    manacher();int t = 0;
    FOR(i,1,N) if(a[i] == '$') r[++t] = R[i]/2;
    LL ans = 0;
    FOR(i,1,t){
        upd(i);
        ans += bit.query(i-r[i],i);
        add(i);
    }
    printf("%lld\n",ans);
    return 0;
}

C

首先注意一个细节：随机一棵树的深度的期望是 $O(\sqrt n)$ 的！！！

只有随机保证 $f_i < i$ 的树深度期望才是 $O(\log n)$ 的。

而我们发现这个期望加了多少次显然只和长度有关，所以我们设 $f_i$ 表示 $i$ 期望被 $1$ 加了多少次。

首先我们考虑对于一个确定的排列如何算答案：可以发现答案等价于这个排列以 $1$ 开始的上升序列个数。

证明

首先在 $1$ 前面的数没有任何贡献，所以我们只考虑从 $1$ 开始的情况。

往后走
只能走到比当前数大的位置

所以 $f_i$ 就是所有 $i!$ 种排列上升序列的个数和的期望。

计算上升序列的个数和很简单，只需要枚举一个上升序列的长度 $d$，就有

$$ f_i = \frac{1}{n!}\sum_{d=1}^i \binom {i-1} {d-1} \binom i d (i-d)! $$

第一项是选出值域，第二项是决定放在整个序列的哪个地方，第三项表示剩下的数可以随便排。

然后就可以用 $f_i$ 去计算每个点被期望加了多少次，就可以去计算每个点的期望值了。

注意计算一个长度为 $d$ 的序列的期望值的时候要考虑 $d+1\ldots n$ 的放置关系，相当于再乘上一个排列数。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

int n,a[MAXN];
int fa[MAXN],m;

inline void dfs(int v,int d=1){
    m = std::max(m,d);
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa[v]) continue;
        fa[e[i].to] = v;dfs(e[i].to,d+1);
    }
}

int f[MAXN],fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int main(){
    prework();
    scanf("%d",&n);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    FOR(i,1,n) scanf("%d",a+i);
    dfs(1);
    f[0] = 1;
    FOR(i,1,m){
        FOR(j,1,i){
            (f[i] += 1ll*C(i-1,j-1)*C(i,j)%ha*fac[i-j]%ha) %= ha;
        }
    }
    int ans = 0;
    FOR(i,1,n) (ans += 1ll*fac[n]*a[i]%ha)%=ha;
    FOR(i,1,n){
        int x = i,d = 1;
        while(x){
            (ans += 1ll*f[d]*a[x]%ha*C(n,n-d)%ha*fac[n-d]%ha) %= ha;
            x = fa[x];d++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Bonus：不随机怎么做

首先我们要先解决如何快速算

$$ f_i = \frac{1}{n!}\sum_{d=1}^i \binom {i-1} {d-1} \binom i d (i-d)! $$

拆一下式子可以得到：

$$ \begin{aligned} f_i &= \frac{1}{n!}\sum_{d=1}^i \frac{(i-1)!}{(d-1)!(i-d)!}\frac{i!}{d!(i-d)!}(i-d)!\\ &= \frac{1}{n!}i!(i-1)!\sum_{d=1}^i \frac{1}{(d-1)!d!}\frac{1}{(i-d)!} \end{aligned} $$

直接 NTT 即可。

$$ f_{d_v-d_u} a_u \binom n {d_v-d_u} (n-(d_v-d_u))! $$

如果上面有错误请在评论区指出，都是我口胡的。

总结：还是自己不会算时间复杂度，不过没有挂题很开心~~（如果拍了 1000 组还挂的话那我就真的菜成狗了）~~

ZR2020 提高十联测 day1

A

B

C

Leave a Comment Cancel reply

I'm back

NOI2021 退役记

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「CF833B」The Bakery

20联赛集训day5 题解

20联赛集训day6 题解

次小生成树

「ZROI851」exexBSBSGSGS

ZR2020 提高十联测 day1

A

B

C