#P10390. [2021年联测]冰与火之舞

    ID: 9508 传统题 4000ms 256MiB 尝试: 9 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-原根0/1 背包树状数组双哈希哈希+二分求 LCP复制数组处理环势能分析增量维护

[2021年联测]冰与火之舞

题目描述

有一个初值为 11 的整数 val\mathrm{val}。给定 nn 个操作,第 ii 个操作由 opti,ai\mathrm{opt}_i,a_i 描述。

  • 若 opti=0\mathrm{opt}_i=0,将 val\mathrm{val} 改为 aia_i。
  • 若 opti=1\mathrm{opt}_i=1,将 val\mathrm{val} 改为 (val×ai) mod p(\mathrm{val}\times a_i)\bmod p。

可以选择任意一部分操作,并按任意顺序执行,每个操作至多用一次。也可以不执行任何操作。求最终 val\mathrm{val} 有多少种不同的取值。保证 pp 是质数。

输入格式

第一行两个整数 p,np,n。接下来 nn 行,每行两个整数 opti,ai\mathrm{opt}_i,a_i。

输出格式

一行一个整数,表示可能的不同取值的个数。

样例

19 3
0 5
1 7
1 17
7

原赛样例 2、3 见下发文件。

数据范围

0≤ai<p0\le a_i<p,opti∈{0,1}\mathrm{opt}_i\in\{0,1\}。原赛采用子任务捆绑测试。

原赛子任务 特殊限制 原赛分值
1 p,n≤3000p,n\le3000 20
2 p,n≤50000p,n\le50000 40
3 p≤200000p\le200000,n≤1000000n\le1000000

原 PDF 题面