2023NOIP A层联测32 T3 sakuya
虚伪的期望,彬彬赛时都能 A 的数学题。
思路
考虑算出来总的花费,再除以 \(m!\) 求期望。
对于某个排列的花费为:\(\sum\limits_{i=2}^m dis(a_{i-1},a_i)\)。
但考虑一下,这个式子重要吗?
我们的目的是求出所有排列的花费的和,不能局限于某一个排列去求。
其实,如果我们知道每一种相邻两个数出现的次数,乘上这两个点间的距离,也可以算出答案。
那么我们考虑 \(u,v\) 相邻的情况(不论先后)在 \(m!\) 种方案中会出现多少次?
赛时通过打表得知,\(u,v\) 相邻的情况有 \(2(m-1)!\) 种,现在来证明一下。
先在这 \(m\) 个数中去掉 \(v\),那么有 \((m-1)!\) 种排列,将 \(v\) 放在每一种排列的 \(u\) 的后一个位置,这样子贡献了 \((m-1)!\) 种情况。
将 \(u,v\) 互换,也能得到 \((m-1)!\) 种情况。
所以说,对于一对数 \(u,v\) 他们在 \(m!\) 种方案中,相邻的次数为 \(2(m-1)!\) 次。
也就是说,每一个 \(dis(u,v) \ (u<v)\) 在 \(m!\) 种方案中计算 \(2(m-1)!\) 次。
答案为:
化简为:
现在求出 \(\sum\limits_{i\in A}\sum\limits_{i\in A,i<j} dis(i,j)\) 即可。
先没有修改操作,这个式子可以统计一条边两边的有效点(在集合 \(A\) 中的点的个数),来计算有多少条经过这条边多少次,乘以边权即可。
如果加上修改,那么每次会影响到和这个点相连的边,但我们不可以遍历这个点的所有边重新算贡献,这样菊花图会 TLE。
所以考虑将与一个点相连的边经过的总次数存在点上,修改时直接将总次数乘以 \(k\) 加上上次的答案即可。
时间复杂度 \(O(n+m)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
const int maxn=5e5+5;
struct node
{
int to,nxt;
ll w;
}edge[maxn*2];
int n,tot,m;
int head[maxn];
ll ans,inv;
ll sz[maxn],c[maxn],fac[maxn];
ll ksm(ll x,ll y)
{
ll sum=1;
for(;y;y/=2,x=x*x%mod) if(y&1) sum=sum*x%mod;
return sum;
}
void add(int x,int y,int z)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
edge[tot].w=z;
head[x]=tot;
}
void dfs(int u,int f)
{
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v==f) continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
void dfs_ans(int u,int f)
{
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v==f) continue;
ans=(ans+sz[v]*(sz[1]-sz[v])%mod*edge[i].w)%mod;
dfs_ans(v,u);
}
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v!=f) c[u]=(c[u]+sz[v]*(sz[1]-sz[v])%mod)%mod;
else c[u]=(c[u]+sz[u]*(sz[1]-sz[u])%mod)%mod;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
sz[x]=1;
}
dfs(1,0);
dfs_ans(1,0);
fac[0]=1;
for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mod;
inv=ksm(fac[m],mod-2);
int _;
scanf("%d",&_);
while(_--)
{
int x;
ll k;
scanf("%d%lld",&x,&k);
ans=(ans+c[x]*k)%mod;
printf("%lld\n",ans*inv%mod*2*fac[m-1]%mod);
}
}
第一次赛时切期望( ̄▽ ̄)~*