#2033. Numbers

    ID: 2033 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest760来源:qoj.ac数据:公开样例线性代数

Numbers

Numbers

题目描述

标题: Numbers - Problem - QOJ.ac

#4910. Numbers

Statistics

The problem was used in the following contests:

题目背景

小 Z 是一个非常菜的 OIer。

小 Z 完全不会出题,距离交题的期限还剩一天时,他还是没有任何想法。

因此,他选了一道非常简单的题,他希望参加比赛的所有人都能在这道题上获得 100 分的好成绩。

题目描述

小 Z 喜欢数字。小 Z 想到了这样一个游戏:

小 Z 有 n 个数字 x1,...,xn。在游戏开始前(即时刻 0),这些数字的值都是 0。

小 Z 有一个生成 [1,n] 间整数的随机数生成器。这个随机数生成器有 n 个正整数参数 v1,...,vn。记 pi=vi∑j=1nvj,它生成一个随机数时,生成 1 的概率为 p1,...,生成 x 的概率为 px,...,生成 n 的概率为 pn。

小 Z 还有 n 个大于 1 的正整数 l1,...,ln,其中第 i 个数 li 的意义是所有对 xi 的操作在 modli 意义下进行。

在游戏中,小 Z 在每个时刻会依次进行如下操作:

  1. 使用随机数生成器生成一个整数。设生成的整数为 k,小 Z 会将第 k 个数字加一,并进行取模。即令 xk←(xk+1)modlk。
  2. 将当前所有数字按顺序构成的序列 (x1,x2,...,xn) 记录在纸上。可以认为纸的长度是无限的。

当某个时刻小 Z 记录了全零的序列 (0,0,...,0) 时,小 Z 会意识到所有数字都回到了最开始的状态,此时他会结束这次游戏。

小 Z 不关心游戏持续的时间,他更想知道纸上会出现多少种不同的序列 (x1,x2,...,xn)。因此他希望求出在游戏结束时,纸上不同的序列 (x1,x2,...,xn) 的种类数的期望值。

小 Z 完全不会这个问题,因此小 Z 请求您帮助他解决这个问题。

为了简便,小 Z 给出了一个质数 mod,你只需要回答期望值对 mod 取模的结果。

同时,小 Z 还给出了 n 个正整数 d1,d2,...,dn 。这些正整数满足如下限制:

  1. 对于任意一个 di,满足 dili≡1(modmod),且对于所有小于 li 的正整数 t,dit≢1(modmod)。
  2. 对于任意一组满足 ∀1≤i≤n,0≤xi≤li−1 的整数序列 (x1,...,xn),满足 ∑i=1npidixi≡1(modmod) 当且仅当所有 xi=0。

最后,小 Z 保证所有 vi 随机生成,且答案在模 mod 下有意义。在满足题目所述条件的情况下,运算中出现值在模 mod 意义下无法表示的概率足够小,可以认为不用考虑出现值在模 mod 意义下无法表示的情况。

输入格式

输入第一行包含三个正整数 n,mod,id。其中 id 表示这个测试点满足 id 号子任务的限制。在测试数据中,第 i 个子任务中的所有测试点满足 id=i。

接下来 n 行,第 i 行包含三个正整数 li,vi,di,含义见题目描述。

输出格式

输出一行一个整数,表示期望值对 mod 取模的结果。

样例

样例输入 #1

2 1000000007 2
2 1 1000000006
2 1 1000000006

样例输出 #1

833333342

样例解释

x1,x2 的性质完全相同。因此第一次操作后 (1,0) 和 (0,1) 两种状态可以看做等价。只考虑为 (1,0) 的状态。

如果下一步仍然给第一个整数加一,则状态变为 (0,0),游戏结束。这种情况出现的概率为 12,纸上不同的序列数为 2。

如果下一步给第二个整数加一,此时状态变为 (1,1)。此时记录的状态为 (1,1),(1,0),考虑下一次给第一个数加一时:

如果在到达状态 (1,1) 后又经过了偶数次给第二个数加一,则这次给第一个数加一后状态为 (0,1)。因此这种情况中游戏结束时四种可能的序列都会出现在纸上。不同的序列数为 4,概率为 12∗(12+18+132+...)=13

如果经过了奇数次后下一次给第一个数加一,则状态变为 (0,0),游戏结束。此时不同的序列数为 3,概率为 12∗(14+116+...)=16

因此答案为 2∗12+3∗16+4∗13=176。因为 6∗166666668≡1(mod109+7),因此输出的值为 17∗166666668mod(109+7)=833333342。

样例 #2~#7

见下发文件

数据范围与限制

记 m=∏i=1nli。

对于所有数据,保证 1≤n,m≤5×105,2≤li,1≤vi≤106,1≤di≤mod−1,9×108≤mod≤1.05×109。数据满足题目描述中给出的所有性质。

本题使用捆绑测试,对于部分子任务有子任务依赖。你需要通过一个子任务中的所有测试点以及这个子任务依赖的所有子任务才能通过这个子任务。

子任务编号 子任务分值 特殊限制 子任务依赖 1 2 n=1 2 8 m≤8 3 10 m≤100 2 4 8 n=2,mod=998244353,m≤210 5 10 li=2,m≤210 6 12 m≤210 3,4,5 7 8 m≤213 6 8 6 n=2,mod=998244353 4 9 8 mod=998244353 8 10 10 li=2 5 11 12 li≤50 10 12 6 无特殊限制 7,9,11

时间限制:4s

空间限制:1024MB

小Z在这里立了一个flag:id以D,M和T开头的选手可以在30min之内切掉这道题。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 1000000007 2
2 1 1000000006
2 1 1000000006
833333342

样例 2

3 1000000007 2
2 1 1000000006
2 1 1000000006
2 2 1000000006
460164255