「CTS2019 | CTSC2019」氪金手游

降 智 好 题 ...

考场上签到失败了,没想容斥就只打了20分暴力...


考虑一个事情,你抽中一个度为0的点,相当于把这个点删掉了(当然你也只能抽中度为0的点)

删掉就是字面意思,就是剩下的树变成子问题

考虑为什么,在抽中这个\(i\)号点后,抽中其他点的概率为

\[\frac{W-w_i}{W}\sum_{i=0}^{\infty}(\frac{w_i}{W})^i=1
\]

说明这个点已经白给了


然后考虑这个树如果是一颗外向树,就是每个点先父亲再自己

有个比较显然的dp,令\(dp_{i,j}\)表示子树\(i\)的\(\sum w=j\)时的概率,转移的时候合并一下子树就好了


然后考虑到,树上一条边相当于一个限制,如果我们去掉这个限制,会多统计一些东西,但是也可以发现,这个多统计的东西就是把边反向的答案...

还是令\(dp_{i,j}\)代表刚刚那个

如果边正向就正常转移

如果反向,就加上去掉限制的再减掉反向的答案(注意到去掉限制的是独立的,我们不需要改变\(W\),只是给他合并一下)


Code:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using std::min;
const int SIZE=1<<21;
char ibuf[SIZE],*iS,*iT;
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
#define gc() getchar()
template <class T>
void read(T &x)
{
x=0;char c=gc();
while(!isdigit(c)) c=gc();
while(isdigit(c)) x=x*10+c-'0',c=gc();
}
const int mod=998244353;
int inline add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
#define mul(x,y) (1ll*(x)*(y)%mod)
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
const int N=1e3+10;
int n,p[N][4],dp[N][N*3],tmp[N*3],siz[N],inv[N*3];
int head[N],to[N<<1],Next[N<<1],type[N<<1],cnt;
void addedge(int u,int v)
{
to[++cnt]=v,type[cnt]=1,Next[cnt]=head[u],head[u]=cnt;
to[++cnt]=u,type[cnt]=0,Next[cnt]=head[v],head[v]=cnt;
}
void dfs(int now,int fa)
{
dp[now][0]=1;
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=fa)
{
dfs(v,now);
memset(tmp,0,sizeof tmp);
for(int j=0;j<=siz[now];j++)
for(int k=0;k<=siz[v];k++)
{
int aya=mul(dp[now][j],dp[v][k]);
if(type[i])
tmp[j+k]=add(tmp[j+k],aya);
else
{
tmp[j+k]=add(tmp[j+k],mod-aya);
tmp[j]=add(tmp[j],aya);
}
}
siz[now]+=siz[v];
for(int j=0;j<=siz[now];j++) dp[now][j]=tmp[j];
}
memset(tmp,0,sizeof tmp);
for(int i=0;i<=siz[now];i++)
for(int j=1;j<=3;j++)
tmp[i+j]=add(tmp[i+j],mul(dp[now][i],mul(p[now][j],mul(j,inv[i+j]))));
siz[now]+=3;
for(int i=0;i<=siz[now];i++)
dp[now][i]=tmp[i];
}
int main()
{
read(n);
for(int a1,a2,a3,i=1;i<=n;i++)
{
read(a1),read(a2),read(a3);
int sum=qp(a1+a2+a3,mod-2);
p[i][1]=mul(a1,sum);
p[i][2]=mul(a2,sum);
p[i][3]=mul(a3,sum);
}
inv[0]=1;
for(int i=1;i<=n*3;i++) inv[i]=qp(i,mod-2);
for(int u,v,i=1;i<n;i++)
{
read(u),read(v);
addedge(u,v);
}
dfs(1,0);
int ans=0;
for(int i=0;i<=3*n;i++) ans=add(ans,dp[1][i]);
printf("%d\n",ans);
return 0;
}

2019.5.20

最新文章

  1. python 数据类型---列表使用 之一
  2. CSS属性之float学习心得
  3. POJ 2480 (约数+欧拉函数)
  4. WCF服务接口多,客户端在引用时出错!报WCF The maximum nametable character count quota (16384) has been exceeded while reading XML data错误
  5. 【深入浅出jQuery】源码浅析2--使用技巧
  6. UML 顺序图
  7. C语言库函数大全及应用实例十一
  8. C# 加密总结 一些常见的加密方法
  9. CSS样式之连接方式
  10. SQL Server性能优化——等待——SLEEP_BPROOL_FLUSH
  11. GIT版本控制 — GIT与SVN的相互转换 (三)
  12. Java中newInstance()和new()区别
  13. vue--模板语法
  14. 莫烦theano学习自修第五天【定义神经层】
  15. Could not transfer artifact org.springframework
  16. 在Debian系中快速有效的安装oracle-java
  17. 20165315 C语言学习情况与Java学习目标
  18. C#:自定义函数
  19. mysql基础(一)——表、索引、视图
  20. noip2012 P1081 开车旅行

热门文章

  1. ceph学习笔记之十二 Ubuntu安装部署Ceph J版本
  2. 20150127 学军集训 day1
  3. linux IPC socket(3)server简单写法
  4. UVa 11384 (推公式+递归)
  5. configure: error: libXpm.(a|so) not found
  6. mysql完美增量备份脚本
  7. 2019 ICPC Asia Nanchang Regional E Eating Plan 离散化+前缀和
  8. 查看mysql慢日志,进行优化
  9. Java中创建泛型数组
  10. 记录以下mysql5.7在win使用Navicat无法链接的问题