← 返回题目列表

Codeforces · 1495/E

E. 青山和丹尼尔

中文机器翻译题面 查看原题

青山和大牛要去玩纸牌游戏。但如果只有两个人玩的话就太无聊了。所以他们总共会制造$$$n$$$个机器人来自动玩这个游戏。青山制作的机器人属于$$$1$$$战队,丹尼尔制作的机器人属于$$$2$$$战队。机器人 $$$i$$$ 属于团队 $$$t_i$$$。游戏开始前,会为机器人 $$$i$$$ 发放 $$$a_i$$$ 卡。

这个纸牌游戏的规则很简单:

- 开始前,机器人按照顺序或索引排列成圆圈。机器人将按某种顺序丢弃牌,在每一步中,一个机器人丢弃一张牌。游戏开始时,机器人 $$$1$$$ 将丢弃其中一张牌。之后,机器人将遵循以下规则:
- 如果机器人 $$$i$$$ 最后弃牌,则与 $$$i$$$ 队伍相对的最近的机器人将接下来弃牌。换句话说,$$$j$$$ 将在 $$$i$$$ 之后立即弃牌,当且仅当在满足 $$$t_i\ne t_j$$$ 的所有 $$$j$$$ 中,$$$dist(i,j)$$$(定义如下)最小。
- 没有牌的机器人应立即退出游戏。后续步骤中不会考虑该机器人。
- 当接下来没有机器人可以弃牌时,游戏结束。

我们定义从机器人$$$x$$$到机器人$$$y$$$的距离为$$$dist(x,y)=(y-x+n)\bmod n$$$。它类似于圆上的定向距离。

例如,当$$$n=5$$$时,从$$$1$$$到$$$3$$$的距离为$$$dist(1,3)=(3-1+5)\bmod 5=2$$$,从$$$3$$$到$$$1$$$的距离为$$$dist(3,1)=(1-3+5)\bmod 5 =3$$$。

后来,青山发现要花这么多时间才能看到机器人怎么玩。她想尽快知道结果。作为青山的粉丝,你被要求计算一个数组 $$$[ans_1,ans_2,\ldots,ans_n]$$$ - $$$ans_i$$$ 等于第 $$$i$$$ 机器人在游戏中将丢弃的牌数。你需要快点!

为了避免输入过大,每个机器人的队伍和牌数将在您的代码中生成,并带有一些辅助数组。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5\cdot 10^6$$$) — 玩这个游戏的机器人数量。

第二行包含一个整数 $$$m$$$ ($$$1 \le m \le \min(n,200\,000)$$$)。

接下来的 $$$m$$$ 行包含四个整数 $$$p_i$$$, $$$k_i$$$, $$$b_i$$$, $$$w_i$$$ ($$$1 \le p_i \le n$$$, $$$1 \le k_i \le 10^9+7$$$, $$$0 \le b_i ,w_i< k_i$$$)。保证 $$$p_m=n$$$ 且 $$$p_{j-1}<p_{j}$$$ ($$$2 \le j \le m$$$)。

数组 $$$a_j$$$ 和 $$$t_j$$$ 应由以下伪代码生成:

输出

打印单个整数 $$$\left( \prod_{i=1}^{n} ((ans_i \oplus i^2)+1)\right) \bmod 10^9+7$$$,其中 $$$\oplus$$$ 表示按位异或运算。

示例

输入 #1

3
3
1 5 2 3
2 7 1 2
3 2 1 1

输出 #1

100

输入 #2

5000000
2
1919810 998244353 114514 19260817
5000000 233333333 623532 7175

输出 #2

800210675

输入 #3

1
1
1 1 0 0

输出 #3

1

注意

在第一个测试用例 $$$a=[5,5,1]$$$ 和 $$$t=[1,2,2]$$$ 中。

机器人$$$1$$$首先丢弃该卡。

然后机器人 $$$2$$$ 接下来丢弃该牌。机器人 $$$3$$$ 接下来不会弃牌,因为 $$$dist(1,2)<dist(1,3)$$$。

然后机器人 $$$1$$$ 接下来丢弃该牌。机器人$$$3$$$接下来不会弃牌,因为$$$t_2=t_3$$$。

如果我们按时间顺序记下出牌机器人的索引,则序列为$$$[1,2,1,2,1,2,1,2]$$$。因此,机器人 $$$1$$$、$$$2$$$ 和 $$$3$$$ 分别丢弃 $$$5$$$、$$$5$$$ 和 $$$0$$$ 牌。答案是 $$$(((5 \oplus 1^2)+1)\times((5 \oplus 2^2)+1)\times((0 \oplus 3^2)+1)) \bmod 10^9+7=(5\times 2 \times 10)\bmod 10^9+7=100$$$。