HDU 6053 TrickGCD 容斥 DFS 分段快速查询

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

TrickGCD

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

You are given an array $A$ , and Zhu wants to know there are how many different array $B$ satisfy the following conditions?
* $1\leq B_{i} \leq A_{i}$
* For each pair( l , r ) ($1 \leq l \leq r \leq n$) , $gcd( b_{l} , b_{l+1} ... b_{r} )\ge 2$

Input

The first line is an integer T($1 \leq T \leq 10$) describe the number of test cases.
Each test case begins with an integer number n describe the size of array $A$.
Then a line contains $n$ numbers describe each element of $A$
You can assume that $1 \leq n , A_{i} \leq 10^5$

Output

For the $k$th test case , first output "Case #k: " , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer $mod$ $10^9+7$

Sample Input

1
4
4 4 4 4

Sample Output

Case #1: 17

Source

题意

给定一个$A_i$数组,构造一个$B_i$数组,满足 $1\leq B_{i} \leq A_{i}$,且$B_i$数组的最大公约数不为1

思路

先将$A_i$排序,使用dfs枚举是否使用每一个质因子,容斥计算$B_i$数组的每一个数是dfs枚举的数的积的倍数。对于每次询问枚举出的数,不能暴力计算方案数,计算每个结果出现的次数即可。

详细题解

先将A数组排序,方便后续处理
枚举gcd是[一些质数的积的倍数],假设这个积为now, 那么要求B数组中每个数都是now的倍数,才能满足B数组的gcd是now的倍数。

对于一个给定的now值,如何求B数组中每个数都是now的倍数的方案呢?
由于1<=B[i]<=A[i],要求B[i]是now的倍数,那么B[i]就有A[i]/now向下取整种可能性,每个B[i]相互独立,将A[i]/now求积即可,但是这样做很容易就超时了。
令t = A[i]/now。发现t的范围是A[1]/now到A[n]/now,如果now比较大的话,这个范围会非常的小。考虑枚举这个t值,求有多少个A[i]满足A[i]/now=t就好了。
由于A数组已经排好序了,对于一个t,那么最小的一个数x使得x/now = t的就是x = now * t,最大的一个y是y=(t+1)*now-1,
在A数组中查找第一个大于等于x的数,查找第一个大于y的数,这两个位置相减,就是满足A[i]/now=t的i的个数len。
最后用快速幂powMod(t,len)来表示A[i]/now = t这len个数除以now向下取整之后的积,再将不同的t得到的乘起来,得到[B数组中每个数都是now的倍数的方案数]。

枚举这个now值的时候会发现,如果枚举了now1和now2,就会造成now1*now2这个值的方案数会算重,需要用容斥减去。
枚举是否选每一个质数,如果选了奇数个质数,那么答案+上这奇数个数造成的方案数,否则ans-去这偶数个数造成的方案数。
如何进行枚举?
用dfs枚举是否选择每一个质数,用k记录已经选的质数的积,用一个变量f,值为1或-1来记录已经选取的质数的个数的奇偶性, now代表正在枚举是否选这个数的下标。
首先,如果now超过了质数的个数,可以return了。
先要明确以点,如果k已经大于了A[1],那么就没用方案了,A[1]怎么可能是一个比他自己还大的数的倍数嘛……
所以假设选取质数p[now],如果p[now] * k > A[1]了,也可以return了
接下来就是算 p[now] *k造成的方案数了,ans += f*造成的方案数。
最后继续进行dfs,枚举是否选这个数,如果选了这个数,k变为k*p[now],f=-f。

 

 

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

 

 
 

SPOJ TSUM FFT求方案数

http://www.spoj.com/problems/TSUM/

 

TSUM - Triple Sums

 

You're given a sequence s of N distinct integers.
Consider all the possible sums of three integers from the sequence at three different indicies.
For each obtainable sum output the number of different triples of indicies that generate it.

Constraints:

N <= 40000, |si| <= 20000

Input

The first line of input contains a single integer N.
Each of the next N lines contain an element of s.

Output

Print the solution for each possible sum in the following format:
sum_value : number_of_triples

Smaller sum values should be printed first.

Example

Explanation:
4 can be obtained using triples ( 0, 1, 2 ) and ( 0, 3, 4 ).
7 can be obtained using triples ( 0, 2, 4 ) and ( 1, 3, 4 ).

Note: a triple is considered the same as any of its permutations.

题意

$n$个整数$s_i$,对于所有的$s$,求满足$s_i+s_j+s_k=s$且$i<j<k$的$(i,j,k)$数量。$n \leq 40000$,$|s_i| \leq 20000$。

思路

构造多项式$A(x) = \sum_{1\leq i \leq n}x^{s_i}$,$x^{s_i}$的系数表示$s_i$这个数出现的次数。则$A^3(x)$中$x^s$的系数即为所求结果。

考虑容斥原理:

1、用$(\sum x)^3$表示任意取三个数,可以用$A(x)$自乘3次得到。

$$ (\sum x)^3 = \sum x^3 + 3 \sum x^2y + 6 \sum xyz$$

其中$\sum x^3$表示取到三个相同的,$\sum x^2y$表示最多两个相同,$\sum xyz$表示三个都不同,也就是我们的最终答案。

2、用$(\sum x^2)(\sum x)$表示至少两个相同,将$A(x)$每一个位置的系数移动到$x^2$的位置即可表示$(\sum x^2)$。

$$(\sum x^2)(\sum x)= \sum x^3+\sum x^2y $$

3、$\sum x^3$即是将$A(x)$的系数移动到$x^3$的位置即可。

联立上面的公式,可得到。

$$\sum xyz = \frac{(\sum x)^3 - 3(\sum x^2)(\sum x)+2(\sum x^3)}{6}$$

根据公式,构造数值进行多项式乘法,用FFT就行优化即可。

考虑到负数的存在,可以加偏移量进行偏移,最后输出答案的时候,减去三倍偏移量即可。

代码