2019 Multi-University Training Contest 2
补题链接：2019 Multi-University Training Contest 2
给出一个整数 $N$，在 $[1,N]$ 中随机生成一个 $n$。然后生成长度为 $n$ 的全排列 $[1, n]$。
对该排列运行一个程序，程序先求当前排列的逆序对对数，然后随机从全排列中选出一个子序列。对该子序列继续进行本程序递归，直到子序列长度为 $0$ 则退出，程序返回逆序对数的总数。求程序产生的答案的期望。
2019 Multi-University Training Contest 1
补题链接：2019 Multi-University Training Contest 1
给定包含 $n$ 个数的序列，$m$ 个询问。询问有两种操作，操作 $0$ 表示在数组最后添加一个新元素，操作 $1$ 表示查询区间 [l,r] 的子集的异或最大值。
询问强制在线。
题目链接：HDU 3949
XOR is a kind of bit operator, we define that as follow: for two binary base number A and B, let C=A XOR B, then for each bit of C, we can get its value by check the digit of corresponding position in A and B. And for each digit, 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0. And we simply write this operator as ^, like 3 ^ 1 = 2,4 ^ 3 = 7. XOR is an amazing operator and this is a question about XOR. We can choose several numbers and do XOR operatorion to them one by one, then we get another number. For example, if we choose 2,3 and 4, we can get 2^3^4=5. Now, you are given N numbers, and you can choose some of them(even a single number) to do XOR on them, and you can get many different numbers. Now I want you tell me which number is the K-th smallest number among them.
题目链接：#113. 最大异或和
这是一道模板题。
给由 $n$ 个数组成的一个可重集 $S$，每次给定一个数 $k$，求一个集合 $T \subseteq S$，使得集合 $T$ 在 $S$ 的所有非空子集的不同的异或和中，其异或和 $T_1 xor T_2 xor … xor T_{|T|}$ 是第 $k$ 小的。
Codeforces Round #113 (Div. 2)
题目链接：Polygons
You’ve got another geometrical task. You are given two non-degenerate polygons $A$ and $B$ as vertex coordinates. Polygon $A$ is strictly convex. Polygon $B$ is an arbitrary polygon without any self-intersections and self-touches. The vertices of both polygons are given in the clockwise order. For each polygon no three consecutively following vertices are located on the same straight line.
Your task is to check whether polygon $B$ is positioned strictly inside polygon $A$. It means that any point of polygon $B$ should be strictly inside polygon $A$. “Strictly” means that the vertex of polygon $B$ cannot lie on the side of the polygon $A$.
题目链接：公式题 (2)
令f(n)=2f(n-1)+3f(n-2)+n,f(1)=1,f(2)=2
令g(n)=g(n-1)+f(n)+n*n,g(1)=2
告诉你n，输出g(n)的结果，结果对1e9+7取模
题目链接：POJ 3070
In the Fibonacci integer sequence, $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n − 1} + F_{n − 2}$ for $n \ge 2$. For example, the first ten terms of the Fibonacci sequence are:
An alternative formula for the Fibonacci sequence is
.
Given an integer $n$, your goal is to compute the last $4$ digits of $F_n$.
题目链接：POJ 1269
We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.
Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.
题目链接：POJ 3304
Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.