NIRVANA

Problem

Number Challenge

$\mathrm{Time\;Limit\;per\;test:\;3\;seconds}$
$\mathrm{Memory\;Limit\;per\;test:\;512\;megabytes}$
$\mathrm{Input:\;standard\;input}$
$\mathrm{Output:\;standard\;output}$

Description

Let’s denote $d(n)$ as the number of divisors of a positive integer $n$. You are given three integers $a$, $b$ and $c$. Your task is to calculate the following sum:
$\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}d(i·j·k)$
Find the sum modulo $1073741824 (2^{30})$.

Input

The first line contains three space-separated integers $a$, $b$ and $c$ $(1\le a,b,c\le 2000)$.

Output

Print a single integer — the required sum modulo $1073741824 (2^{30})$.

Problem

棋盘

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

给定一个$n\times n$的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置$(x,y),(u,v)$能互相攻击当前仅当满足以下两个条件：

1. $x=u$或$y=v$
2. 对于$(x,y)$与$(u,v)$之间的所有位置，均不是障碍。

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

Input

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

Output

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

Problem

【SDOI2010】星际竞速

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

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

Input

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

Output

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

$\;$

Problem

快速傅立叶之二

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

请计算$c[k]=\sum_{i=1}^{n}a[i]\cdot b[i-k]$其中$k\le i<n$，并且有$n\le10^5$。
$a,b$中的元素均为小于等于$100$的非负整数。

Input

第一行一个整数$N$，接下来$N$行，每行两个数，依次表示$a[i],b[i]\;(0\le i<N)$。

Output

输出$N$行，每行一个整数，第$i$行输出$c[i-1]$。

Problem

陌上花开

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

有$n$朵花，每朵花有三个属性：花形($s$)、颜色($c$)、气味($m$)，用三个整数表示。
现在要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花$a$比另一朵花$b$要美丽，当且仅$s_a\ge s_b,c_a\ge c_b,m_a\ge m_b$。
显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为$N,K\;(1\le N\le10^5,1\le K\le2\times10^5)$，分别表示花的数量和最大属性值。
以下$N$行，每行三个整数$s_i,c_i,m_i\;(1\le s_i,c_i,m_i\le K)$，表示第$i$朵花的属性。

Output

包含$N$行，分别表示评级为$0\sim N-1$的每级花的数量。

Problem

【CQOI2011】动态逆序对

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

对于序列$A$，它的逆序对数定义为满足$i<j$，且$A_i>A_j$的数对$(i,j)$的个数。
给$1$到$n$的一个排列，按照某种顺序依次删除$m$个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

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

Output

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

Problem

Polycomp

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

你有三个系数为$0,1$的多项式$f(x),g(x),h(x)$
求$f(g(x))\mod{h(x)}$
为方便起见，将答案多项式所有系数对$2$取模输出即可
如果$f(x)=\sum_{k=1}^{n} a_k\cdot x^k$，则$f(g(x))=\sum_{k=1}^{n}a_k\cdot g(x)^k$

Input

一共三行，每行一个多项式，分别为$f,g,h$
对于一个多项式$P$，描述为$n$个整数$P_0,P_1,\cdots,P_n$，其中$P_i$为$0$或$1$，$P(x)=P_0+P_1\cdot x+\cdots+P_n\cdot x_n$

Output

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

Problem

Play with sequence

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

1. 给出参数$U,V,C$，将$a[U],a[U+1],...,a[V-1],a[V]$都赋值为$C$。
2. 给出参数$U,V,C$，对于区间$[U,V]$里的每个数$i$，将$a[i]$赋值为$\max(a[i]+C,0)$。
3. 给出参数$U,V$，输出$a[U],a[U+1],...,a[V-1],a[V]$里值为$0$的数字个数。

Input

第一行包含两个正整数$N,M\;(1\le N,M\le3\times10^5)$，分别表示序列长度和操作个数。
第二行包含$N$个整数，其中第$i$个数表示$a[i]\;(0\le a[i]\le10^9)$，描述序列的初始状态。
接下来$M$行描述$M$个操作，保证$1\le U\le V\le N$，对于操作$1$，$0\le C\le10^9$，对于操作$2$，$|C|\le10^9$。

Output

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

Problem

Willem, Chtholly and Seniorious

$\mathrm{Time\;Limit\;per\;test:\;2\;seconds}$
$\mathrm{Memory\;Limit\;per\;test:\;256\;megabytes}$
$\mathrm{input:\;standard\;input}$
\mathrm{output:\;standard\;output

Description

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

$\mathrm{Seniorious}$ is made by linking special talismans in particular order.
After over $500$ years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
$\mathrm{Seniorious}$ has $n$ pieces of talisman. Willem puts them in a line, the $i^{th}$ of which is an integer $a_i$.
In order to maintain it, Willem needs to perform $m$ operations.
There are four types of operations:

1. $l\;r\;x$: For each $i$ such that $l\le i\le r$, assign $a_i+x$ to $a_i$.
2. $l\;r\;x$: For each $i$ such that $l\le i\le r$, assign $x$ to $a_i$.
3. $l\;r\;x$: Print the $x^{th}$ smallest number in the index range $[l,r]$, i.e. the element at the $x^{th}$ position if all the elements $a_i$ such that $l≤i≤r$ are taken and sorted into an array of non-decreasing integers. It’s guaranteed that $1\le x\le r-l+1$.
4. $l\;r\;x\;y$: Print the sum of the $x^{th}$ power of $a_i$ such that $l\le i\le r$, modulo $y$, i.e. $(\sum_{i=l}^{r}{a_i^x})\mod{y}$.

Input

The only line contains four integers $n,m,seed,vmax$ ($1\le n,m\le10^5$,$0\le seed<10^9+7$,$1\le vmax\le10^9)$.
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 $op$ is the type of the operation mentioned in the legend.

Output

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