文档章节

题解-CTS2019氪金手游

o
 osc_ogi0qclx
发布于 2019/08/23 10:46
字数 1268
阅读 9
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

Problem

$\mathtt {loj-3124}$

题意概要:给定 $n$ 个点,$w_i$ 分别有 $p_{i,1},p_{i,2},p_{i,3}$ 的概率取 $1,2,3$。

**在确定了所有的 $w_i$ 后再开始游戏:**不断抽点,点 $i$ 被抽中的概率为 $\frac {w_i}{\sum_{j=1}^nw_j}$,直到所有点都被抽中过。

给定 $n-1$ 个二元组 $(u,v)$ 表示第一次抽中 $u$ 的时间需要比第一次抽中 $v$ 的时间早,且若将这 $n-1$ 个二元组中的两个元素连无向边,则这张图是一棵树。

问满足所有二元组限制的概率。

$n\leq 1000$

Solution

(话说考场上看错了题,以为是确定好每个点抽中的概率后再进行游戏,打了正解加仨暴力,跑出来都是一样的就是和大样例不一样,导致心态崩了 而且题面里并没有提到这个区别)

这题的解题突破口在于这个题的限制是一棵树,但边的方向不唯一(没法找到根使得这棵树变成内向树或外向树)

为了解题方便,不妨设这棵树是以 $1$ 号节点为根的外向树(对于每条边而言,方向都是从靠近 $1$ 的一端指向远离 $1$ 的一端)

那么可以发现,$1$ 号节点必须是最后一个抽到的,概率为 $\frac {w_1}{\sum_{i=1}^nw_i}$,而且只要满足这个条件后,这个点就没有用了,问题分解成 $1$ 的每棵子树满足自身拓扑序的概率之积,这又是一个子问题

设 $sz_i$ 表示 $i$ 的子树中概率系数的和($\sum_{v\in subtree(x)}w_v$)

即设 $f[x]$ 表示 $x$ 的子树内满足拓扑序的概率,则 $f[x]=\frac {w_x}{sz_x}\prod_{x\rightarrow v}f[v]$,不难得到 $Ans=f[1]=\prod_{x=1}^n\frac {w_x}{sz_x}$

那么可以用一个Dp解决这个问题:设 $f[x][i]$ 表示在 $i$ 的子树中、概率系数和为 $j$ 且满足拓扑序的概率,$O(n^2)$

毒瘤出题人居然不给这档部分分?


考虑到这棵树不是外向树,存在若干条内向边。

直接处理内向边不好处理,现在存在一种方法,即用 “不考虑这条边”的方案数 减去 “考虑这条边为外向边”的方案数

(用图来表达即:$o\rightarrow o\leftarrow o$ 等于 $o\rightarrow o\quad o$ 减去 $o\rightarrow o\rightarrow o$)

然后在树上Dp时,遇到此类内向边就将权值用上面这种方法计算一下即可。


听说这题还有另一种做法,代码实现上是一样的,但思想不大一样:

考虑设 $g[i]$ 表示这若干条内向边中,至少有 $i$ 条内向边的条件不满足,则容斥可知答案为:$\sum_i(-1)^ig[i]$

而 “至少 $i$ 条内向边不满足”,也即 “$i$ 条内向边变为外向边,而其他内向边断开”

这样在Dp的时候加入一个容斥系数即可:一开始设所有内向边断开,然后给其加上一个负的 “内向边变外向边” 的权值

Code

//loj-3124
#include <cstdio>
typedef long long ll;

const int N = 1013, p = 998244353;
struct Edge {int v, w, nxt;} a[N<<1];
int head[N], sz[N];
int a1[N], a2[N], a3[N];
int F[N][N*3], arr[N*3];
int inv[N*3], n, _;

inline int qpow(int A, int B) {
	int res = 1; while(B) {
		if(B&1) res = (ll)res * A%p;
		A = (ll)A * A%p, B >>= 1;
	} return res;
}

void dfs(int x, int las) {
	int*f = F[x];
	f[0] = 1;
	for(int ii=head[x],v;ii;ii=a[ii].nxt)
		if((v=a[ii].v) != las) {
			dfs(v, x);
			int*g = F[v];
			const int sx = sz[x] * 3, sv = sz[v] * 3;
			for(int i=0;i<=sx+sv;++i) arr[i] = 0;
			if(!a[ii].w)
				for(int i=0;i<=sx;++i)
				for(int j=0;j<=sv;++j)
					arr[i+j] = (arr[i+j] + (ll)f[i] * g[j])%p;
			else {
				ll sm = 0;
				for(int i=0;i<=sv;++i) sm += g[i];
				sm %= p;
				for(int i=0;i<=sx;++i) arr[i] = sm * f[i]%p;
				
				for(int i=0;i<=sx;++i)
				for(int j=0;j<=sv;++j)
					arr[i+j] = (arr[i+j] - (ll)f[i] * g[j] + (ll)p*p)%p;
			}
			for(int i=0;i<=sx+sv;++i) f[i] = arr[i];
			sz[x] += sz[v];
		}
	const int sx = sz[x] * 3;
	for(int i=0;i<=sx+3;++i) arr[i] = 0;
	for(int i=0;i<=sx;++i) {
		arr[i+1] = (arr[i+1] + (ll)f[i] * a1[x]%p * inv[i+1])%p;
		arr[i+2] = (arr[i+2] + (ll)f[i] * a2[x]%p * inv[i+2] * 2)%p;
		arr[i+3] = (arr[i+3] + (ll)f[i] * a3[x]%p * inv[i+3] * 3)%p;
	}
	for(int i=0;i<=sx+3;++i) f[i] = arr[i];
	++sz[x];
}

int main() {
	scanf("%d",&n);
	inv[0] = inv[1] = 1;
	for(int i=2;i<=n*3;++i) inv[i] = (ll)(p-p/i) * inv[p%i]%p;
	for(int i=1;i<=n;++i) {
		scanf("%d%d%d",a1+i,a2+i,a3+i);
		ll v = qpow(a1[i] + a2[i] + a3[i], p-2);
		a1[i] = v * a1[i]%p;
		a2[i] = v * a2[i]%p;
		a3[i] = v * a3[i]%p;
	}
	for(int i=1,x,y;i<n;++i) {
		scanf("%d%d",&x,&y);
		a[++_].v = y, a[_].w = 0, a[_].nxt = head[x], head[x] = _;
		a[++_].v = x, a[_].w = 1, a[_].nxt = head[y], head[y] = _;
	}
	dfs(1, 0);
	
	ll Ans = 0;
	for(int i=sz[1]*3;~i;--i)
		Ans += F[1][i];
	printf("%lld\n", Ans%p);
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
mvc框架--Razor

Razor 是一个轻巧而优雅的servlet mvc框架 # 又一个轮子? no,写就她是为了证实我个人的某些想法,并在这个过程中练练手,这两种冲动碰撞在一起,自然而然地产生了Razor # Razor的现在和未来...

dtubest
2013/01/25
2.9K
0
灵活的反向代理和静态资源代理--Goproxy

Goproxy使用代理的方式来加强hosts文件的配置,对hosts文件的修改实时生效(不需要使用firefox上的dns flusher插件),对hosts文件里正常的配置没有任何影响。 通过配置hosts文件中的dns映射,...

weager
2013/06/16
5.6K
0
phpcmsDroid

基于phpcms建站系统的android客户端,本软件是以南京金地自在城网站为示例做的demo,只包含基本的文章列表,评论查看、发表,用户登录、注销等功能。actionbar使用actionbarsherlock开源实现...

lkiarest
2013/07/06
697
0
手游开发工具集CocoStudio v0.1.1版抢先免费试用

手机游戏开发的高手们,对Cocos2D-X一定不会陌生吧,甚至非常熟悉。 Cocos2D-X是手机游戏开发使用者最多的引擎之一。这不仅因为其简单易用,而且还有强大的工具集来辅助开发者轻松、快速开发...

丹尼迪恩
2013/05/04
1.6K
6
iOS开发----Xcode7升级之后插件无法使用与不小心点击Skipbundle的解决办法

小伙伴们在升级了 Xcode7 之后有些插件不能使用了.现在提供如下解决办法: 1. 首先查看 Xcode 的 UUID,在终端执行 defaults read /Applications/Xcode.app/Contents/Info DVTPlugInCompatibi...

周绪刚
2015/10/13
1.5K
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
18分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
48分钟前
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0
马化腾每天刷 Leetcode?代码你打算写到几岁?

本文作者:o****0 前几天,一张未证真伪的截图流传,图中显示马化腾几乎每天都会在 Leetcode 上提交代码。 截图还贴出一个 Leetcode 账户地址。该地址的头像已从马化腾的照片换成腾讯 logo,...

百度开发者中心
前天
13
0
滴滴 3000+ Kylin Cube 背后的实践经验揭秘

本次分享主要有三个部分:Kylin 在滴滴的整体应用、架构的实践经验、滴滴全局字典最新版本的实现以及 Kylin 最新实时 OLAP 探索经验分享。 Kylin 在滴滴的应用&架构 Kylin 在滴滴的三类应用场...

浪尖聊大数据
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部