HDU 6052 To my boyfriend 询问分块 容斥 单调栈

http://acm.hdu.edu.cn/showproblem.php?pid=6052

To my boyfriend

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)



Problem Description

Dear Liao
I never forget the moment I met with you. You carefully asked me: "I have a very difficult problem. Can you teach me?". I replied with a smile, "of course". You replied:"Given a matrix, I randomly choose a sub-matrix, what is the expectation of the number of **different numbers** it contains?"
Sincerely yours,
Guo

Input

The first line of input contains an integer T(T≤8) indicating the number of test cases.
Each case contains two integers, n and m (1≤n, m≤100), the number of rows and the number of columns in the grid, respectively.
The next n lines each contain m integers. In particular, the j-th integer in the i-th of these rows contains g_i,j (0≤ g_i,j < n*m).

Output

Each case outputs a number that holds 9 decimal places.

Sample Input

1
2 3
1 2 1
2 1 2

Sample Output

1.666666667

Hint

6(size = 1) + 14(size = 2) + 4(size = 3) + 4(size = 4) + 2(size = 6) = 30 / 18 = 6(size = 1) + 7(size = 2) + 2(size = 3) + 2(size = 4) + 1(size = 6)

Source

题意

给定一个$n*m$的矩阵,矩阵内每个点有个颜色。现任选一个子矩阵,问这个子矩阵包含的不同颜色个数的期望。

思路

单独求每种颜色对答案的贡献,对于一种颜色来说,如果点的个数超过了7个,直接使用单调栈来维护不含这个颜色的子矩阵的个数,否则使用容斥来算。对于单调栈维护来说,枚举每一行,算出这一行的每一个点往上多高不会包含这种颜色,分别用单调栈维护以每个点作为右下角的方案即可。容斥的计算总方案数-至少包含一个点的+至少包含两个点的-……

 

 
 

Codeforces749E Inversions After Shuffle 逆序数的期望 树状数组

http://codeforces.com/problemset/problem/749/E

E. Inversions After Shuffle

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation of integers from 1 to n. Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally:

  1. Pick a random segment (continuous subsequence) from l to r. All segments are equiprobable.
  2. Let k = r - l + 1, i.e. the length of the chosen segment. Pick a random permutation of integers from 1 to k, p1, p2, ..., pk. All k! permutation are equiprobable.
  3. This permutation is applied to elements of the chosen segment, i.e. permutation a1, a2, ..., al - 1, al, al + 1, ..., ar - 1, ar, ar + 1, ..., an is transformed to a1, a2, ..., al - 1, al - 1 + p1, al - 1 + p2, ..., al - 1 + pk - 1, al - 1 + pk, ar + 1, ..., an.

Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs (i, j) such that i < j and ai > aj. Find the expected number of inversions after we apply exactly one operation mentioned above.

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.

Output

Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 9.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Input

Output

 

 

HDU 5723 Abandoned country 最小生成树 + 期望计算

http://acm.hdu.edu.cn/showproblem.php?pid=5723

Abandoned country

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
An abandoned country has n(n100000) villages which are numbered from 1 to n . Since abandoned for a long time, the roads need to be re-built. There are m(m1000000) roads to be re-built, the length of each road is wi(wi1000000) . Guaranteed that any two wi are different. The roads made all the villages connected directly or indirectly before destroyed. Every road will cost the same value of its length to rebuild. The king wants to use the minimum cost to make all the villages connected with each other directly or indirectly. After the roads are re-built, the king asks a men as messenger. The king will select any two different points as starting point or the destination with the same probability. Now the king asks you to tell him the minimum cost and the minimum expectations length the messenger will walk.
Input
The first line contains an integer T(T10) which indicates the number of test cases.
For each test case, the first line contains two integers n,m indicate the number of villages and the number of roads to be re-built. Next m lines, each line have three number i,j,wi , the length of a road connecting the village i and the village j is wi .
Output
output the minimum cost and minimum Expectations with two decimal places. They separated by a space.
Sample Input
1
4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6
Sample Output
6 3.33
Author
HIT
Source
题意:给定一个图,每条边边权不同,求问最小生成树的大小,并求出任意两点,在最小生成树上路径长度的期望。
思路:由于每条边权都不同,那么最小生成树是唯一的。求任意两点,在最小生成树上路径长度的期望,可以考虑计算每条边对答案的贡献,经过这条边的次数*这条边的边权就是贡献,次数为这条边两边点的个数的乘积。用第一次dfs求出每个子树的大小,用第二次dfs求出每条边两边点的数目即可。最后将总和除以总的方案数n*(n-1)/2得到最终的答案。