Problem

Number Challenge

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

Description

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

Input

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

Output

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

Read more »

Problem

棋盘

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

Description

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

  1. x=ux=uy=vy=v
  2. 对于(x,y)(x,y)(u,v)(u,v)之间的所有位置,均不是障碍。

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

Input

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

Output

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

Read more »

Problem

【SDOI2010】星际竞速

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

Description

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

Input

第一行是两个正整数N,MN,M
第二行NN个数A1ANA_1\sim A_N,其中AiA_i表示使用能力爆发模式到达行星ii所需的定位时间。
接下来MM行,每行33个正整数ui,vi,wiu_i,v_i,w_i,表示在编号为uiu_iviv_i的行星之间存在一条需要航行wiw_i时间的星际航路。
输入数据已经按引力值排序,也就是编号小的行星引力值一定小,且不会有两颗行星引力值相同。

Output

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

Read more »

Problem

快速傅立叶之二

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

Description

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

Input

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

Output

输出NN行,每行一个整数,第ii行输出c[i1]c[i-1]

Read more »

Problem

陌上花开

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

Description

nn朵花,每朵花有三个属性:花形(ss)、颜色(cc)、气味(mm),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花aa比另一朵花bb要美丽,当且仅sasb,cacb,mambs_a\ge s_b,c_a\ge c_b,m_a\ge m_b
显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K  (1N105,1K2×105)N,K\;(1\le N\le10^5,1\le K\le2\times10^5),分别表示花的数量和最大属性值。
以下NN行,每行三个整数si,ci,mi  (1si,ci,miK)s_i,c_i,m_i\;(1\le s_i,c_i,m_i\le K),表示第ii朵花的属性。

Output

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

Read more »

Problem

【CQOI2011】动态逆序对

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

Description

对于序列AA,它的逆序对数定义为满足i<ji<j,且Ai>AjA_i>A_j的数对(i,j)(i,j)的个数。
11nn的一个排列,按照某种顺序依次删除mm个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

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

Output

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

Read more »

Problem

Polycomp

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

Description

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

Input

一共三行,每行一个多项式,分别为f,g,hf,g,h
对于一个多项式PP,描述为nn个整数P0,P1,,PnP_0,P_1,\cdots,P_n,其中PiP_i0011P(x)=P0+P1x++PnxnP(x)=P_0+P_1\cdot x+\cdots+P_n\cdot x_n

Output

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

Read more »

Problem

Play with sequence

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

Description

维护一个长度为NN的序列aa,现在有三种操作:

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

Input

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

Output

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

Read more »

Problem

Willem, Chtholly and Seniorious

Time  Limit  per  test:  2  seconds\mathrm{Time\;Limit\;per\;test:\;2\;seconds}
Memory  Limit  per  test:  256  megabytes\mathrm{Memory\;Limit\;per\;test:\;256\;megabytes}
input:  standard  input\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…

![](http://codeforces.com/predownloaded/b1/f8/b1f8c486967b50eedc6972dc2ecef18cdfd7d52d.png)

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

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

Input

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

Output

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

Read more »