Problem

Number Challenge

Description

Let’s denote as the number of divisors of a positive integer . You are given three integers , and . Your task is to calculate the following sum:

Find the sum modulo .

Input

The first line contains three space-separated integers , and .

Output

Print a single integer — the required sum modulo .

Problem

棋盘

Description

给定一个的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置能互相攻击当前仅当满足以下两个条件：

1. 或
2. 对于与之间的所有位置，均不是障碍。

现在有个询问，每个询问给定，要求从棋盘中选出个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？

Input

第一行一个整数。
接下来输入一个的字符矩阵，一个位置若为.，则表示这是一个空位置；若为#，则为障碍。
第行输入一个整数代表询问个数。
接下来行，每行一个整数，代表要放的棋子个数。

Output

输出共行，每行代表对应询问的最少的互相能攻击到的棋子对数。

Problem

【SDOI2010】星际竞速

Description

十年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座星的悠悠也是其中之一。
赛车大赛的赛场由颗行星和条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这颗行星之间没有任何航路的天体出发，访问这颗行星每颗恰好一次，首先完成这一目标的人获得胜利。
由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃――在经过一段时间的定位之后，它能瞬间移动到任意一个行星。
天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者――你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。

Input

第一行是两个正整数。
第二行个数，其中表示使用能力爆发模式到达行星所需的定位时间。
接下来行，每行个正整数，表示在编号为和的行星之间存在一条需要航行时间的星际航路。
输入数据已经按引力值排序，也就是编号小的行星引力值一定小，且不会有两颗行星引力值相同。

Output

仅包含一个正整数，表示完成比赛所需的最少时间。

Problem

快速傅立叶之二

Description

请计算其中，并且有。
中的元素均为小于等于的非负整数。

Input

第一行一个整数，接下来行，每行两个数，依次表示。

Output

输出行，每行一个整数，第行输出。

Problem

【CQOI2011】动态逆序对

Description

对于序列，它的逆序对数定义为满足，且的数对的个数。
给到的一个排列，按照某种顺序依次删除个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数和，即初始元素的个数和删除的元素个数。
以下行每行包含一个到之间的正整数，即初始排列。
以下行每行一个正整数，依次为每次删除的元素。

Output

输出包含行，依次为删除每个元素之前，逆序对的个数。

Problem

陌上花开

Description

有朵花，每朵花有三个属性：花形()、颜色()、气味()，用三个整数表示。
现在要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花比另一朵花要美丽，当且仅。
显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为，分别表示花的数量和最大属性值。
以下行，每行三个整数，表示第朵花的属性。

Output

包含行，分别表示评级为的每级花的数量。

Problem

Polycomp

Description

你有三个系数为的多项式
求
为方便起见，将答案多项式所有系数对取模输出即可
如果，则

Input

一共三行，每行一个多项式，分别为
对于一个多项式，描述为个整数，其中为或，

Output

用同样的格式输出答案多项式
如果答案为，输出0 0

Problem

Play with sequence

Description

维护一个长度为的序列，现在有三种操作：

1. 给出参数，将都赋值为。
2. 给出参数，对于区间里的每个数，将赋值为。
3. 给出参数，输出里值为的数字个数。

Input

第一行包含两个正整数，分别表示序列长度和操作个数。
第二行包含个整数，其中第个数表示，描述序列的初始状态。
接下来行描述个操作，保证，对于操作，，对于操作，。

Output

输出若干行，每行一个整数，依次回答每个操作的问题。

Problem

Willem, Chtholly and Seniorious

Description

— Willem…
— What’s the matter?
— It seems that there’s something wrong with Seniorious…
— I’ll have a look…

is made by linking special talismans in particular order.
After over years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
has pieces of talisman. Willem puts them in a line, the of which is an integer .
In order to maintain it, Willem needs to perform operations.
There are four types of operations:

1. : For each such that , assign to .
2. : For each such that , assign to .
3. : Print the smallest number in the index range , i.e. the element at the position if all the elements such that are taken and sorted into an array of non-decreasing integers. It’s guaranteed that .
4. : Print the sum of the power of such that , modulo , i.e. .

Input

The only line contains four integers (,,.
The initial values and operations are generated using following pseudo code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def rnd():
    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret

for i = 1 to n:
    a[i] = (rnd() mod vmax) + 1

for i = 1 to m:
    op = (rnd() mod 4) + 1
    l = (rnd() mod n) + 1
    r = (rnd() mod n) + 1
    if (l > r): 
         swap(l, r)
    if (op == 3):
        x = (rnd() mod (r - l + 1)) + 1
    else:
        x = (rnd() mod vmax) + 1
    if (op == 4):
        y = (rnd() mod vmax) + 1

Here is the type of the operation mentioned in the legend.

Output

For each operation of types or , output a line containing the answer.