2017ICPC北京网络赛 G | hihocoder 1584 Bounce

For Argo, it is very interesting watching a circle bouncing in a rectangle.

As shown in the figure below, the rectangle is divided into N×M grids, and the circle fits exactly one grid.

The bouncing rule is simple:

1. The circle always starts from the left upper corner and moves towards lower right.

2. If the circle touches any edge of the rectangle, it will bounce.

3. If the circle reaches any corner of the rectangle after starting, it will stop there.

Argo wants to know how many grids the circle will go through only once until it first reaches another corner. Can you help him?

输入

The input consists of multiple test cases. (Up to 105)

For each test case:

One line contains two integers N and M, indicating the number of rows and columns of the rectangle. (2 ≤ N, M ≤ 109)

输出

For each test case, output one line containing one integer, the number of grids that the circle will go through exactly once until it stops (the starting grid and the ending grid also count).

样例输入

样例输出

题目大意:在n*m的方格表里,小球从左上角开始弹弹弹直到再次弹到角落,求只经过一次的格子的数量。
思路:总路径长度-经过两次的格子数量*2。

直觉告诉我们这个斜边间隔和gcd有关。
考虑3*6的情况

尝试做镜面反射,注意到反射后共用了一列边界,猜得到相邻斜线距离为\[L=gcd(n-1,m-1)\]路径总长为\[lcm(n-1,m-1)+1\]

n=3,m=6时L=gcd(2,5)=1,n=9,m=15时L=gcd(8,14)=2。

再考虑经过两次的格子数量。
按行把两次点分成两类,如下图红色类和蓝色类。

此图中L=2,红色类从L+1行L+1列开始每隔2L格一行,2L格一列(注意边界不能算),故红色类个数为\[\lceil\frac{n-L-1}{2\times L}\rceil\times\lceil\frac{m-L-1}{2\times L}\rceil\]

蓝色类从2L+1行2L+1列开始每隔2L格一行,2L格一列(注意边界不能算),故蓝色类个数为\[\lfloor\frac{n-2}{2\times L}\rfloor\times\lfloor\frac{m-2}{2\times L}\rfloor\]

于是答案为\[\frac{(n-1)\times(m-1)}{L}+1-2\times(\lceil\frac{n-L-1}{2\times L}\rceil\times\lceil\frac{m-L-1}{2\times L}\rceil+\lfloor\frac{n-2}{2\times L}\rfloor\times\lfloor\frac{m-2}{2\times L}\rfloor)\]

代码:

 

2017ICPC北京网络赛 B | hihocoder 1579 Reverse Suffix Array

描述

There is a strong data structure called “Suffix Array” which can effectively solve string problems.

Let S=s1s2…sn be a string and let S[i,j] denote the substring of S ranging from i to j. The suffix array A of S is now defined to be an array of integers providing the starting positions of suffixes of S in lexicographical order. This means, an entry A[i] is the starting position of the i-th smallest suffix in S and thus for all 1 < i ≤ n:  S[A[i-1], n] < S[A[i], n].

For example: the suffix array of “banana” is [6, 4, 2, 1, 5, 3].

Here comes another problem called “Reverse Suffix Array”.

Given a suffix array, you need to figure out how many lower case strings are there whose suffix array is the same as the given suffix array.

输入

First line contains a positive number T which means the number of test cases.

For each test cases, first line contains a positive number N, the second line contains N integer(s) which indicates the suffix array A.

1 ≤ T ≤ 10, 1 ≤ N ≤ 100,000

1 ≤ A[i] ≤ N (i = 1…N)

输出

For each test case, output one line contains the answer. If no qualified string exists, output 0.

样例输入

样例输出

 

题目大意是给后缀数组求原串有多少种可能性。

sa数组4 3 2 5 1可以画成下面:
④⑤
③④⑤
②③④⑤

①②③④⑤

首先可以得到$$④\le③\le②\le⑤\le①$$
但是其中有一些是小于号,需要从sa数组里判断。
对于sa数组相邻两行,例如④和③,
想要知道是\(④\le③\)还是\(④<③\),只需比较他们的后一段的大小,即⑤和④⑤的大小,这个可以从sa数组里直接查出来。 若\(⑤>④⑤\),那么\(④<③\),否则\(④\le③\)。这是本题的关键。

判断完后我们得到\[④<③\le②<⑤\le①\]
转化为求\(1\le④<③\le②<⑤\le①\le26\)的整数解的问题,这是个经典的插板问题。
做一步映射变为\(1\le④<③<②+1<⑤<①+2\le26\),
设原来中间有k个\(“\le”\),那么解的数量就是\(\binom{26+k}{n}\)。

大数的问题用java或者python搞一下就好了。

 

Andrew-Stankevich-Contest-47 | Codeforces gym 100608 E Elegant Square

题目大意是,构造一个n*n矩阵,由不同的正整数组成,使每行每列的数字积相等,还要求每个数字不能含有平方因子。

看完题目就能够想到这是一个构造题。搞一些质数行列错排一下对应位乘起来最后各个数字不一样就好。但问题是怎么排列能使每个数字不同。对题目给的样例分解一下会得到:

一开始想过按照错排的搜索顺序放置素数但好像素数好像不太够啊,又考虑随机放置素数错排,发现同样的数字就重排某个素数,但是太慢了要随机很久。

最后想到每个格子用两个素数组成,只要所有格子的素数对不同就好。

于是先搞出这样一个矩阵:

然后为了搭配一下再反着搞一下:

接着乘起来:

因为相同的数字都出现在斜线上,两个矩阵斜线方向不同,所以两个方向的斜线最多只能交出一个数,也就是说不同位置的数字应该不一样。看起来似乎做完了,但其实是有bug的。在n奇数时这样是没错的因为如下图,一个素数的两条斜线不会重叠,但是n偶数时会gg。

就是说,n为偶数时,一个数字会在它右下方n/2处重复。

为了解决偶数的问题,我们可以再构造一个类似的矩阵,然后将它的下n/2半行,循环下移,这样不改变题目要求的行列积的性质,但是重复数字不会出现在原来的右下n/2处。

最后把这个矩阵和原先的到的矩阵对应位乘起来,因为两个满足条件的矩阵乘起来还是行列积相同的,两个矩阵数字重复的位置又不同,故乘起来后的矩阵的数字是各不相同的: