UOJ Logo Universal Online Judge

UOJ

#574. 【ULR #1】多线程计算

附件下载 统计

众所周知,搜索引擎需要强有力的硬件支持,在进行“跳找”的开发之前,你计划先调查一下跳蚤王国的硬件技术储备。

在取得跳蚤国王的许可后,你在硬件科技中心把档案翻了个遍,偶然发现了一款非常神奇的处理器“Jumptel D233”。

这款处理器有着较低的热功比,在通常使用时,大量处理器集成在同一个主板上,且分布为 $n$ 行 $m$ 列。

若给处理器分配多线程并行计算任务,由于夸张的频率波动,各个处理器完成任务所需时间不尽相同。

具体的,对于每个处理器,其会在 $[0, 1)$ 中独立均匀随机的某个实数时刻 $p$ 完成计算。处理器之间互不影响。在完成计算之后,处理器会持续亮灯。你可以认为灯亮灭的切换不需要时间。

你经过观察发现,整行(或列)处理器的亮灭情况会对主板供电产生微妙影响。

具体地,存在 $h$ 组数对,令第 $i$ 组为 $(x_i,y_i)$;对于某种亮灭状态,若存在一个 $i$,满足恰好分别有 $x_i$ 行和 $y_i$ 列的处理器全部亮灯(可以存在其它行或列的处理器有亮灯,但不能存在另外的行或列处理器全部亮灯),则称该状态为节能态

在节能态触发时,假如当前已经有 $k$ 个处理器亮起,那么每单位时间会节省 $F_k$ 单位电量。其中数列 $\left\{F_n\right\}_{n \ge 0}$ 被以下递推式确定:$F_0=F_1=1;\ F_n=F_{n-1}+F_{n-2}\ (n>1)$

为了评估节电效果,请你求出节省电量数的期望对 $998244353$ 取模的结果。

输入格式

第一行三个整数,分别表示 $n, m, h$,意义如题目所述。

下面 $h$ 行,第 $i$ 行为两个整数 $(x_i,y_i)$,是题中所述的与节能态相关的参数。(保证各个 $(x_i,y_i)$ 作为有序对互不相同)

输出格式

一行一个整数,表示节省电量数的期望对 $998244353$ 取模的结果。即如果答案的最简分数表示为 $\frac{x}{y}(x \geq 0, y \geq 1, \gcd(x,y) = 1)$,你需要输出满足 $ay \equiv x \pmod{998244353}$ 的那个唯一的整数 $a$ 满足 $0 \le a < 998244353$。

样例一

input

1 1 1
0 0

output

499122177

explanation

唯一的一个处理器亮灯之前为节能态。

节能态的持续时间是一在 $[0,1)$ 内均匀随机的变量,其期望为 $\frac{1}{2}=499122177\pmod{998244353}$,对节省电量数的贡献系数是 $F_0=1$。

样例二

input

2 2 1
1 1

output

798595483

explanation

$\rm O$ 表示亮灯, $-$ 表示未亮灯, 以下四种情况为节能态:

$\begin{bmatrix}\rm O&\rm O\\\rm O&-\end{bmatrix}$ $\begin{bmatrix}\rm O&-\\\rm O&\rm O\end{bmatrix}$ $\begin{bmatrix}-&\rm O\\\rm O&\rm O\end{bmatrix}$ $\begin{bmatrix}\rm O&\rm O\\-&\rm O\end{bmatrix}$

样例三

input

3 3 3
0 0
1 1
2 2

output

720162004

explanation

$\begin{bmatrix}\rm O&\rm O&-\\ \rm O&\rm O&\rm O\\-&\rm O&\rm O\end{bmatrix}$ 是一种满足数对 $(1,1)$ 的可能的节能态。

限制与约定

对于所有测试点,$0\leq x_i< n$,$0\leq y_i< m$,$1\leq n\times m\leq 5\times 10^5\ ,1\leq h\leq n\times m$。

子任务编号$n \times m\leq$$n,m\leq$$h\leq$分值
$1$ $10$ $10$ $n\times m$ $25$
$2$ $3000$ $500$ $1$ $10$
$3$ $n\times m$ $10$
$4$ $5\times 10^5$ $1$ $5$
$5$ $50$ $10$
$6$ $n\times m$ $20$
$7$ $5\times 10^5$ $20$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载