#1925. 小 Bo 的数列
小 Bo 的数列
小 Bo 的数列
题目描述
标题: 小 Bo 的数列 - Problem - QOJ.ac
#10360. 小 Bo 的数列
The problem was used in the following contests:
Warning: 附加文件中的 trans.cpp 不可用,因此本题暂时无法解决。
小 Bo 特别喜欢数列。有一天他偶尔得到了一个序列,这个序列是无限长的,但特殊的是这个序列中只有 N 个位置有值。 小 Bo 将这个序列存在了自己的笔记本中。不幸的是,有一天他忘记锁屏了。一个熊孩子看到了他的数列,决定做一些恶作剧。
熊孩子先将这个序列 A 复制到一个新的序列 B 里,然后做了 t 次操作,每次将 B 赋值为 A 与 B 的 狄里克雷卷积 结果。 最后,熊孩子又新建了一个序列 C,并将 B 中的第 i 项加到了 C 中的第 trans(i,M) 项,并输出了序列 C。
这时,小 Bo 突然回来了,熊孩子落荒而逃,匆忙之中落下了记录着 M 的纸片。小 Bo 发现桌面上多了一个根本打不开的文件。 通过各种渠道,小 Bo 又得到了 trans(i, M) 的具体代码。
现在小 Bo 想要知道这个序列 C 是什么样子的,但是 C 太长了,所以他只想知道 ∑i≥1Ci⋅i,请你帮助他得到这个结果。
在附件中给出了 trans.cpp,用来描述 trans 函数。
输入格式
第一行三个整数 N,m,t,分别描述序列中有值的位置数量、M 中不同质因子个数和操作次数。
接下来 m 行,每行两个正整数 pi,ci,其中 M=∏i=1mpici。
接下来 N 行,每行两个正整数 ai,bi,表示 Aai=bi。
输出格式
一行,输出答案模 1163962801 的值。
样例
样例输入一
3 1 1
3 1
2 5
5 3
6 1
样例输出一
729
样例说明
原序列 A 中,有 A2=5,A5=3,A6=1。
操作过后得到的序列 B 为 B4=25,B10=30,B12=10,B25=9,B30=6,B36=1。
M=3,M 中可用的约数仅有 3。
4,10,25 经过 trans 后数值不变,trans(12,M)=4,trans(30,M)=10,trans(36,M)=4。
于是最后的序列 C 为 C4=36,C10=36,C25=9。
答案为 36×4+36×10+9×25=729。
数据规模与约定
本题一共 10 个测试数据,每个测试数据的分值为 10 分。
每个数据的特殊性质请参见下表:
ID N m t 特殊约定 1 5 / ≤3 M≤20,ai≤M 2 ≤1000 / ≤1000 M≤109, ai 是 M 的约数 3 ≤1000 / / M≤109, ai 是 M 的约数 4 / ≤200 / ai 是 M 的约数 5 / / / ai 是 M 的约数 6 / ≤200 / ci≤2 7 / / / ci≤2 8 / ≤200 / / 9 / / / / 10 / / / /
保证 100% 的数据满足:
- 1≤N,m≤100000
- 0≤t≤109
- 1≤ai,bi≤109
- 2≤pi≤109,数据保证 pi,ai 互不相同,且 pi 是质数
- 1≤ci≤20,∏i=1mci≤105
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 1 1
3 1
2 5
5 3
6 1
729