# POJ 2279. Mr. Young's Picture Permutations (线性DP)

## 题面

### Description

Mr. Young wishes to take a picture of his class. The students will stand in rows with each row no longer than the row behind it and the left ends of the rows aligned. For instance, 12 students could be arranged in rows (from back to front) of 5, 3, 3 and 1 students.

In addition, Mr. Young wants the students in each row arranged so that heights decrease from left to right. Also, student heights should decrease from the back to the front. Thinking about it, Mr. Young sees that for the 12-student example, there are at least two ways to arrange the students (with 1 as the tallest etc.):

Mr. Young wonders how many different arrangements of the students there might be for a given arrangement of rows. He tries counting by hand starting with rows of 3, 2 and 1 and counts 16 arrangements:

Mr. Young sees that counting by hand is not going to be very effective for any reasonable number of students so he asks you to help out by writing a computer program to determine the number of different arrangements of students for a given set of rows.

### Input

The input for each problem instance will consist of two lines. The first line gives the number of rows, k, as a decimal integer. The second line contains the lengths of the rows from back to front (n1, n2,…, nk) as decimal integers separated by a single space. The problem set ends with a line with a row count of 0. There will never be more than 5 rows and the total number of students, N, (sum of the row lengths) will be at most 30.

### Output

The output for each problem instance shall be the number of arrangements of the N students into the given rows so that the heights decrease along each row from left to right and along each column from back to front as a decimal integer. (Assume all heights are distinct.) The result of each problem instance should be on a separate line. The input data will be chosen so that the result will always fit in an unsigned 32 bit integer.

## 题目大意

$N$个学生（ 身高为 $1$~ $N$ ）排成$k$ 行拍照，从后到前每行分别有$N_{1}, N_{2}, \cdots, N_{k}$ 个学生。现在要求每行学生从左到右的身高和每列学生从后到前的身高必须按降序排列，求排列这些学生站位的方法总数。

## 题解

### 分析

$f(x_1,x_2,x_3,x_4,x_5)=f(x_1-1,x_2,x_3,x_4,x_5)+\\ [x_1>x_2] \cdot f(x_1,x_2-1,x_3,x_4,x_5)+\\ [x_2>x_3] \cdot f(x_1,x_2,x_3-1,x_4,x_5)+\\ [x_3>x_4] \cdot f(x_1,x_2,x_3,x_4-1,x_5)+\\ [x_4>x_5] \cdot f(x_1,x_2,x_3,x_4,x_5-1)$

# A. 解方程 (暴力) [Comet OJ Contest #0]

## 题面

### Description

$\sqrt{x-\sqrt{n}} + \sqrt{y} - \sqrt{z}=0$ 的解。

### Hint

$n=12$时，方程唯一的解为$x=4,y=1,z=3$

$n=24$时，方程的两组解为 $x=5,y=2,z=3$$x=7,y=1,z=6$

## 题解

$\sqrt{x-\sqrt{n}}=\sqrt{z}-\sqrt{y}$

$x-\sqrt{n}=y+z-2\sqrt{yz}$

$x-(y+z)=\sqrt{n}-2\sqrt{yz}$

• 方程左右两边均为 $0$

$\left \{ \begin{matrix} x=y+z \\ n = 4yz \end{matrix} \right.$

• 方程左右两边均不为 $0$

# HDU 6050. Funny Function (快速幂，逆元)

## 题面

### Description

Function $F_{x,y}$ satisfies:

$F_{1, 1} = F_{1, 2} = 1 \\ F_{1, i} = F_{1, i - 1} + 2 * F_{1, i - 2} \; (i \geq 3) \\ F_{i, j} = \sum_{k = j}^{j + N - 1}F_{i - 1, k} \; (i \geq 2, j \geq 1)$

For given integers $N$and $M$,calculate $F_{m, 1}$ modulo$10^{9} + 7$.

### Input

There is one integer T in the first line.

The next T lines,each line includes two integers N and M .

1<=T<=10000,1<=N,M<2^63.

### Output

For each given N and M,print the answer in a single line.

## 题解

$F_{1, i}$$a_{i}$ ，则

$a_{i} = a_{i - 1} + 2a_{i - 2} \; (i \geq 3)$

$p \neq 0, q \in \mathbb{R}$ 使得

$a_{i} + ka_{i - 1} = p(a_{i - 1} + ka_{i - 2})$

• $\left \{ \begin{matrix} p = -1 \\ k = -2 \end{matrix} \right.$ 成立

$b_{i} = (-1)^{i}$

$a_{i} - 2a_{i - 1} = (-1)^{i - 1}$ . 此时有

$\frac{a_{i}}{(-1)^{i}}+2\frac{a_{i - 1}}{(-1)^{i - 1}} = -1$

$c_{i} = \dfrac{a_{i}}{(-1) ^ {i}}$ ，易得

$c_{i} = \frac{1}{3}(-2)^{i} - \frac{1}{3}$

$a_{i} = （-1)^{i}c_{i} = \frac{2^{i}}{3} + \frac{(-1)^{i - 1}}{3}$

• $\left \{ \begin{matrix} p = 2 \\ k = 1 \end{matrix} \right.$ 成立

$F_{1, i} = \frac{1}{3} \cdot (-1)^{i - 1} + \frac{1}{3} \cdot 2^{i} \tag{1}$

$F_{2, i} = \sum_{k=i}^{i+N-1}F_{1,k}=\sum_{k=1}^{i+N-1}F_{1,k}-\sum_{k=1}^{i-1}F_{1,k} \tag{2}$

$\sum_{i=1}^{n}F_{1,i} = \frac{1}{3}\sum_{i=1}^{n}(-1)^{i-1}+\frac{1}{3}\sum_{i=1}^{n}2^{i} \\ =\frac{1}{6}\cdot(1+(-1)^{n+1})+\frac{2}{3}\cdot(2^{n}-1)$

$F_{2, i} = \frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)\cdot2^{i} \tag{3}$

$F_{3,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{2}\cdot2^{i} \tag{4}$

$F_{m,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{m-1}\cdot2^{i} \tag{5}$

$F_{m,1}=\frac{1}{3}[(m\;\mathbf{mod}\;2)+2\cdot(2^{N}-1)^{m-1}] \tag{6}$

## 代码

$k$ 乘法千万不能忘了逆元。。。这次居然很脑抽地居然把逆元忘了导致赛中自闭orz = =

# Codeforces 1133D. Zero Quantity Maximization (map, 精度)

## 题面

### Description

You are given two arrays $a$and $b$, each contains$n$ integers.

You want to create a new array $c$as follows: choose some real (i.e. not necessarily integer) number $d$, and then for every $i \in [1, n]$ let$c_i := d \cdot a_i + b_i$.

Your goal is to maximize the number of zeroes in array $c$. What is the largest possible answer, if you choose $d$ optimally?

### Input

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in both arrays.

The second line contains $n$integers $a_1$, $a_2$, …,$a_n$ ($-10^9 \le a_i \le 10^9$).

The third line contains $n$integers $b_1$, $b_2$, …,$b_n$ ($-10^9 \le b_i \le 10^9$).

### Output

Print one integer — the maximum number of zeroes in array $c$, if you choose $d$ optimally.

### Note

In the first example, we may choose $d = -2$.

In the second example, we may choose $d = -\dfrac{1}{13}$.

In the third example, we cannot obtain any zero in array $c$, no matter which $d$ we choose.

In the fourth example, we may choose $d = 6$.

## 题目大意

$c[i] = d \cdot a[i] + b[i]$

## 题解

### 分析

$d \cdot a[i] + b[i] = 0$，则有 $d = -\dfrac{b[i]}{a[i]}$。但 $d$会爆 double 精度，此时用 pair 维护 <-b[i] / gcd, a[i] / gcd> 即可。但此时要注意处理 b[i]a[i] 的正负号关系（e.g. $\dfrac{1}{1} = \dfrac{-1}{-1}$ ，但在直接按此存储则会导致被认作为不同的值）。也可用 long double 维护$d$ 。之后用 map 统计出现次数最多的 d 即可。

# Codeforces 1030A. In Search of an Easy Problem(Codebait) [Codeforces Round

## 题面

### Description

When preparing a tournament, Codeforces coordinators try treir best to make the first problem as easy as possible. This time the coordinator had chosen some problem and asked $n$ people about their opinions. Each person answered whether this problem is easy or hard.

If at least one of these $n$ people has answered that the problem is hard, the coordinator decides to change the problem. For the given responses, check if the problem is easy enough.

### Input

The first line contains a single integer $n$ ($1 \le n \le 100$) — the number of people who were asked to give their opinions.

The second line contains $n$integers, each integer is either $0$or $1$. If $i$-th integer is $0$, then $i$-th person thinks that the problem is easy; if it is$1$, then$i$-th person thinks that the problem is hard.

### Output

Print one word: “EASY” if the problem is easy according to all responses, or “HARD” if there is at least one person who thinks the problem is hard.

You may print every letter in any register: “EASY”, “easy”, “EaSY” and “eAsY” all will be processed correctly.

# A. Magic Mirror(新手题，字符串处理) [2018 ACM-ICPC Jiaozuo Online Contest]

## 题面

### Description

Jessie has a magic mirror.

Every morning she will ask the mirror: ‘Mirror mirror tell me, who is the most beautiful girl in the world?’ If the mirror says her name, she will praise the mirror: ‘Good guy!’, but if the mirror says the name of another person, she will assail the mirror: ‘Dare you say that again?’

Today Jessie asks the mirror the same question above, and you are given a series of mirror’s answers. For each answer, please output Jessie’s response. You can assume that the uppercase or lowercase letters appearing anywhere in the name will have no influence on the answer. For example, ‘Jessie’ and ‘jessie’ represent the same person.

### Input

The first line contains an integer $T(1 \le T \le 100)$, which is the number of test cases.

Each test case contains one line with a single-word name, which contains only English letters. The length of each name is no more than $15$.

### Output

For each test case, output one line containing the answer.

# F. Sorting (排序，浮点数精度) [2017 CCPC China-Hunan Invitional]

## Description

Bobo has $n$tuples$(a_1, b_1, c_1), (a_2, b_2, c_2), \dots, (a_n, b_n, c_n)$ .
He would like to find the lexicographically smallest permutation $p_1, p_2, \dots, p_n$of$1, 2, \dots, n$ such that for$i \in \{2, 3, \dots, n\}$ it holds that

$\frac{a_{p_{i - 1}} + b_{p_{i - 1}}}{a_{p_{i - 1}} + b_{p_{i - 1}} + c_{p_{i - 1}}} \leq \frac{a_{p_i} + b_{p_i}}{a_{p_i} + b_{p_i} + c_{p_i}}$

### Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer $n$.

The $i$-th of the following $n$lines contains $3$integers $a_i$,$b_i$ and$c_i$.

### Output

For each test case, print $n$integers$p_1, p_2, \dots, p_n$ seperated by spaces.
DO NOT print trailing spaces.

#### Constraint

• $1 \leq n \leq 10^3$
• $1 \leq a_i, b_i, c_i \leq 2 \times 10^9$
• The sum of $n$does not exceed$10^4$.

## 题解

### 分析

$(a_{p_{i-1}}+b_{p_{i-1}})(a_{p_{i}}+b_{p_{i}}+c_{p_{i}}) \leq (a_{p_{i}} + b_{p_{i}})(a_{p_{i-1}}+b_{p_{i-1}}+c_{p_{i-1}}))$

$(a_{p_{i-1}} + b_{p_{i-1}})c_{p_{i}} \leq (a_{p_{i}} + b_{p_{i}})c_{p_{i-1}}$

# POJ.2559 Largest Rectangle in a Histogram (单调栈)

## 题面

### Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

### Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,…,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

### Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

### Hint

Huge input, scanf is recommended.

## 分析

• 应从哪个位置开始选取所需的矩形并集？
• 当确定了开始位置时，应向左/右哪个方向延伸，延伸多少？

• 如果当前矩形的高度大于等于栈顶矩形，则直接将当前矩形压入栈顶，宽度为1。
• 如果当前矩形的高度小于栈顶矩形，则持续将栈顶矩形出栈，直至当前矩形高度大于等于栈顶矩形为止。同时，在这一过程中，累积记录所有出栈矩形的宽度；当出栈完毕后，再将以累积值为宽度、当前矩形高度为高的新矩形压入栈顶。

# A. An Olympian Math Problem (数论) [2018 ACM-ICPC Nanjing Online Contest]

## Description

Alice, a student of grade $6$, is thinking about an Olympian Math problem, but she feels so despair that she cries. And her classmate, Bob, has no idea about the problem. Thus he wants you to help him. The problem is:

We denote $k!$:

$k! = 1 \times 2 \times \cdots \times (k - 1) \times k$

We denote $S$:

$S = 1 \times 1! + 2 \times 2! + \cdots +$
$(n - 1) \times (n-1)!$

Then $S$module$n$ is ____________

You are given an integer $n$.

You have to calculate $S$modulo$n$.

### Input

The first line contains an integer $T(T \le 1000)$, denoting the number of test cases.

For each test case, there is a line which has an integer $n$.

It is guaranteed that $2 \le n\le 10^{18}$.

### Output

For each test case, print an integer $S$modulo$n$.

### Hint

The first test is: $S = 1\times 1!= 1$, and $1$modulo $2$ is$1$.

The second test is: $S = 1\times 1!+2 \times 2!= 5$, and $5$modulo$3$ is$2$.

## 题解

$S \; \mathrm{mod} \; n$

$= (n! - 1) \; \mathrm{mod} \; n$

$= (n! + n - 1) ; \mathrm{mod} ; n$

$= n! ; \mathrm{mod} ; n + (n - 1) ; \mathrm{mod} ; n$

$= n - 1$.

# A.队列Q - WannyFly挑战赛19

## 题目

64bit IO Format: %lld

### 题目描述

ZZT 创造了一个队列 Q。这个队列包含了 N 个元素，队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素，QN 表示队尾元素。队列中的元素是 N 的一个全排列。
ZZT 需要在这个队列上执行 P 次操作，操作分两种：
FIRST X: 将元素 X 移到队头。
LAST X: 将元素 X 移到队尾。