HDU 6155 Subsequence Count 线段树维护矩阵DP转移

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

给一个01序列,有区间反转操作,询问区间内本质不同的子序列的个数 $%10^9+7$

写出dp转移方程,用$dp[i][j]$表从起点到第$i$个点,最后一位是$j$的方案数。

当第$i$位是$0$的时候:

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1] $$

当第$i$位是$1$的时候:

$$dp[i][0] = dp[i-1][0] $$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

写成矩阵的形式进行转移

如果这一位是$0$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

如果这一位是$1$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

可以用线段树维护任意区间内的转移方程。

考虑反转,会发现把$0$矩阵交换$r_1,r_2$和$c_1,c_2$就能变成$1$矩阵,反之亦然。令$T=\begin{bmatrix} 0 & 1& 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}$,可知$TT=E$

交换行,可以在矩阵前乘以个 $T$,交换列,可以在矩阵后乘以一个$T$。假设$C=AB$ ,那么$TCT = TABT = TATTBT$。意味着,进行区间反转的时候,将维护的转移矩阵进行交换行列就好了,并打上延时标记。

 

HDU 6153 A Secret KMP计数

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

给定两个串$s_1$,$s_2$,求$s_2$的每一个后缀在$s_1$中出现的次数$\times$长度的和。

将$s_1$,$s_2$进行反转,就变成了求$s_2$的每一个前缀在$s_1$中出现的次数$\times$长度的和。处理出$s_2$的next数组,用$s_2$对$s_1$进行匹配,假设$s_2[j]$和$s_1[i]$匹配上了,那么新出现的前缀就有$s_2[j],s_2[next[j]],s_2[next[next[j]],……$。但是并不能在匹配的过程中进行next跳转计数,会超时的。可以记录每个匹配长度值出现的次数,那么如果前缀$j$出现过,那么前缀$next[j]$也一定出现过。匹配完后,cnt[next[j]] += cnt[j]即可算出每个前缀出现的次数。

HDU6158 The Designer 笛卡尔定理 递推

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

 

一个大圆$O_1$和三个小圆$O_2、O_3、O_4$内切,三个小圆相互外切,他们的半径满足如下等式:
$$(\frac{1}{r_2} + \frac{1}{r_3} + \frac{1}{r_4} - \frac{1}{r_1})^2 = 2(\frac{1}{r^2_1}+\frac{1}{r^2_2}+\frac{1}{r^2_3}+\frac{1}{r^2_4})$$

计算有标号圆的面积。
设大圆半径为$r_a$,左边的圆半径为$r_b$。则$r_1 = r_a - r_b$
只看上半部分的圆,对圆重新编号为1、2、3、……
$r_1 = r_a - r_b$
设第$k$个圆的半径为$r_k$,根据笛卡尔定理有如下等式
$$(\frac{1}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_b}-\frac{1}{r_a})^2= 2(\frac{1}{r^2_k}+\frac{1}{r^2_{k+1}}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$
同时也有
$$(\frac{1}{r_k}+\frac{1}{r_{k-1}}+\frac{1}{r_b}-\frac{1}{r_a})^2= 2(\frac{1}{r^2_k}+\frac{1}{r^2_{k-1}}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$
上下两式相减,得到
$$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a})=
2(\frac{1}{r^2_{k+1}} - \frac{1}{r^2_{k-1}})
$$
将右边展开,得到
$$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a})=
2(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}})
$$
两边同时消去$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})$,得到
$$
\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a}=
\frac{2}{r_{k+1}}+\frac{2}{r_{k-1}}
$$
合并同类项,得到
$$\frac{2}{r_k}+\frac{2}{r_b}-\frac{2}{r_a}=\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}$$
移项得到
$$
\frac{1}{r_{k+1}}=\frac{2}{r_k}+\frac{2}{r_b}-\frac{2}{r_a}-\frac{1}{r_{k-1}}
$$
这是一个关于$r_k$的递推式,知道前两项就能递推出后一项。
但是现在只知道$r_1、r_a、r_b$,还不知道$r_2$,无法进行递推。
根据笛卡尔定理有
$$(\frac{1}{r_1} + \frac{1}{r_2} + \frac{1}{r_b} - \frac{1}{r_a})^2 = 2(\frac{1}{r^2_1}+\frac{1}{r^2_2}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$
将其左右展开有
$$
\frac{1}{r^2_2} + 2 \times \frac{1}{r_2}(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a}) =
2 \times \frac{1}{r^2_2} + 2(\frac{1}{r^2_1}+\frac{1}{r^2_b}+\frac{1}{r^2_a})
$$
移项合并同类型,得到如下
$$
\frac{1}{r^2_2} - 2(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a})\frac{1}{r_2} +2(\frac{1}{r^2_1}+\frac{1}{r^2_b}+\frac{1}{r^2_a}) = 0
$$
将$\frac{1}{r_2}$看作未知量,根据实际情况,方程的两个根应该相同,所以根据韦达定理有
$$
\frac{1}{r_2} + \frac{1}{r_2} = 2(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a})
$$

$$
\frac{1}{r_2} = \frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a}
$$
已经求得$r_1$和$r_2$,可以进行递推

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

 

 
 

HDU 6050 Funny Function 矩阵快速幂 矩阵变化

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

Funny Function

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

Problem Description

Function $F_{x,y}$satisfies:

For given integers N and M,calculate $F_{m,1}$ modulo 1e9+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.

Sample Input

2
2 2
3 3

Sample Output

2
33

Source

题意

给定上图公式和$n,m$,求$F_{m,1}$

思路

可以发现,$F_{i,j} = F_{i,j-1}+2*F_{i,j-2}$,对于每行,维护出$F_j, F_{j-1},Sum_j,F_1$,用矩阵快速幂计算即可。转移到下一行,
$$F_j = Sum_{n+1} - F_1$$
$$F_{j-1} = Sum_{n+1} - F_n$$
$$Sum_j = 2* Sum_{n+1} -  F_1 - F_n$$
$$F_1 = Sum_{n+1} - F_n$$
上述变化是线性的,前面乘以一个矩阵即可表示。最后将所得的矩阵快速幂$m-1$次后,乘上维护的信息,就是最后的答案。

 

 

HDU 6044 Limited Permutation DFS计算方案数

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

Limited Permutation

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

As to a permutation $p_1, p_2, \cdots, p_n$ from $1$ to $n$, it is uncomplicated for each $1 \leq i \leq n$ to calculate $(l_i, r_i)$ meeting the condition that $\min(p_L, p_{L + 1}, \cdots, p_R) = p_i$ if and only if $l_i \leq L \leq i \leq R \leq r_i$ for each $1 \leq L \leq R \leq n$.
Given the positive integers $n$, $(l_i, r_i)$ $(1 \leq i \leq n)$, you are asked to calculate the number of possible permutations $p_1, p_2, \cdots, p_n$ from $1$ to $n$, meeting the above condition.
The answer may be very large, so you only need to give the value of answer modulo $10^9 + 7$.

Input

The input contains multiple test cases.
For each test case:
The first line contains one positive integer $n$, satisfying $1 \leq n \leq 10^6$.
The second line contains $n$ positive integers $l_1, l_2, \cdots, l_n$, satisfying $1 \leq l_i \leq i$ for each $1 \leq i \leq n$.
The third line contains $n$ positive integers $r_1, r_2, \cdots, r_n$, satisfying $i \leq r_i \leq n$ for each $1 \leq i \leq n$.
It's guaranteed that the sum of $n$ in all test cases is not larger than $3 \cdot 10^6$.
Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

Sample Input

3
1 1 3
1 3 3
5
1 2 2 4 5
5 2 5 5 5

Sample Output

Case #1: 2
Case #2: 3

Source

题意

求一个长度为$n$的排列的方案数,给出n个限制条件$l_i,r_i$,表示当且经当$l_i \leq L \leq i \leq R \leq r_i$的时候,$\min(p_L, p_{L + 1}, \cdots, p_R) = p_i$ ,否则一定不是。

思路

根据题述条件推得,对于每一对$l_i,r_i$来说,如果其左边存在,那么左边第一个数一定小于$p_i$,同理,右边的第一个数一定小于$p_i$。那么,对于所有的$l_i,r_i$来说,只存在包含和相离两种关系,绝对不能包含相交和重叠的关系,否则无解。对于一对$l_i,r_i$来说,该区间内的最小值一定在i位置,把这个最小值的位置确定下来后,还有$r_i-l_i$个数的位置不确定,现在,左区间的长度为$i-l_i$,那么选取$其中i-l_i$个数放到左区间,其余的放到右区间,计算组合数,递归出来左右区间即可。

 

HDU 6038 Function 循环节 方案数

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

Function

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

You are given a permutation $a$ from $0$ to $n - 1$ and a permutation $b$ from $0$ to $m - 1$.
Define that the domain of function $f$ is the set of integers from $0$ to $n - 1$, and the range of it is the set of integers from $0$ to $m - 1$.
Please calculate the quantity of different functions $f$ satisfying that $\displaystyle f(i) = b_{f(a_i)}$ for each $i$ from $0$ to $n - 1$.
Two functions are different if and only if there exists at least one integer from $0$ to $n - 1$ mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo $10^9 + 7$.

Input

The input contains multiple test cases.
For each case:
The first line contains two numbers $n,$ $m$. $(1 \leq n \leq 100000, 1 \leq m \leq 100000)$
The second line contains $n$ numbers, ranged from $0$ to $n - 1$, the $i$-th number of which represents $a_{i - 1}$.
The third line contains $m$ numbers, ranged from $0$ to $m - 1$, the $i$-th number of which represents $b_{i - 1}$.
It is guaranteed that $\sum{n} \leq 10^6,$ $\sum{m} \leq 10^6$.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

Sample Input

3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1

Sample Output

Case #1: 4
Case #2: 4

Source

 

题意

给一个长度为$n$的排列$a_i$,再给一个长度为$m$的排列$b_i$,问有多少组映射$f(i)$,满足 $ f(i) = b_{f(a_i)}$

思路

$f(i) = b_{f(a_i)} = b_{b_{f(a_{a_i})}} = \underbrace{b_{\cdots b_{f(i)}}}_{l\text{ times }b}$

由于$a_i, b_i$都是排列,所以上述的等式一定成立,(注意倒数第二个表达式a的下标),假设a的一个循环节的长度一定要是l,那么对应一定b一个有个循环节,长度为l的一个约数。可以将a的这个循环节看成一个换,将b的一个循环节布在这个环上,有多少种本质不同的情况,其实就是b的这个循环节大小。对于a的每一个循环节,可以和b的任意一个满足长度要求的循环节任意组合。所以,枚举a的每一个循环节,找到所有满足要求的b循环节,计算方案累加即可。

 

HDU6035 Colorful Tree DFS + 统计对答案的贡献

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

Colorful Tree

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

There is a tree with $n$ nodes, each of which has a type of color represented by an integer, where the color of node $i$ is $c_i$.
The path between each two different nodes is unique, of which we define the value as the number of different colors appearing in it.
Calculate the sum of values of all paths on the tree that has $\frac{n(n-1)}{2}$ paths in total.

Input

The input contains multiple test cases.
For each test case, the first line contains one positive integers $n$, indicating the number of node. $(2 \leq n \leq 200000)$
Next line contains $n$ integers where the $i$-th integer represents $c_i$, the color of node $i$. $(1 \leq c_i \leq n)$
Each of the next $n - 1$ lines contains two positive integers $x, y$ $(1 \leq x, y \leq n, x \neq y)$, meaning an edge between node $x$ and node $y$.
It is guaranteed that these edges form a tree.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

Sample Input

Sample Output

Source

 

题意

给一个$n$个点的树,每个点有一种颜色。一条路径的权重被定义为这条路径上不同颜色的个数。求所有路径权重的总和。

思路

可以单独考虑每种颜色对答案的贡献,假设我们现在关注的颜色为$c_i$,求有多少条路径上含有这种颜色,最后求和即可。但是这个东西还是不好求,可以考虑在树上把这些点删掉,剩下的路径就是不含关注颜色点的路径,数目为$\sum各个连通块大小s_i*(s_i-1)/2$。最后总路径条数减去这个和值即可。现在问题就转化到了就每个连通块的大小。首先dfs求出每个子树的大小,再次dfs,假设当前点为u,颜色为c[u],对u的一个子树v进行搜索的时候,如果发现v的某个子树的颜色和c[u]相同,且这个子树和u的路径上没有再出现颜色c[u],则sz[v]减去这个子树的大小。最后sz[v]的大小就是从u点向v点走,一个不含c[u]颜色的连通块的大小。当然这只是思路,在实际dfs的时候,用一个栈st[c[u]]来记录c[u]颜色上一次出现在什么位置,回溯的时候需要将栈pop。当在搜到颜色和u点相同颜色的点的时候,直接将搜到的子树的大小记录到u节点上即可。最后还要注意,需要给树加一个虚根,并且每种颜色第一次出现都是在这个虚根上,方便计算答案。

PS:栈的容器类型需要换成vector,开$10^5$个栈会直接MLE的

 

 

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就行优化即可。

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

代码