icontofig | 发布于 2019-09-22 21:13:56 | 阅读量 392 | FFT 字符串 生成函数
发布于 2019-09-22 21:13:56 | FFT 字符串 生成函数
BZOJ 3160 万径人踪灭 FFT + 回文自动机 + 生成函数
题目大意 给定一个字符集仅含a和b的字符串s,求字符串中不连续的回文子序列个数mod 1000000007的值。 题解如果是连续的回文子序列,也就是回文串,那就很好求了,直接运用Manacher算法就可以了。 但是这题是让算所有的不连续的回文子序列…… 然而这个是没法直接算出来的…… 所以我们反过来想,我们可以把所有回文子序列的数量求出来,然后减去回文子串的数量,就是不连续的回文子序列的数量。 上面说了,如果是回文子串的数量,可以直接用Manacher算法算出来。 所以现在我们考虑的就是全体回文子序列的数量该怎么算。 对一个回文子序列,一定有一个中心,假设两个对应字符位置分别为x,y
继续阅读
icontofig | 发布于 2019-09-21 15:29:50 | 阅读量 350 | FFT 生成函数
发布于 2019-09-21 15:29:50 | FFT 生成函数
The Preliminary Contest for ICPC Asia Shanghai 2019 C.Triple FFT + 生成函数
题目大意给定一个正整数n,有三个数组A,B,C,每个数组有n个数,求问有多少个三元组(i,j,k)满足|Ai-Bj|≤Ck,|Ck-Bj|≤Ai,|Ai-Ck|≤Bj 题解首先我们发现,其实三元组满足的条件其实非常像三角形的构成条件,所以我们可以叙述成 “最小值 + 中间值 ≤ 最大值” 满足这样的三元组个数。 官方题解是正着算的,然后还有什么去重什么麻烦的东西,看起来令人头大…… 所以我们为何不反过来算呢? 首先所有的取法总数是n3,然后我们只需要计算以下不满足的三元组总数即可了。 但是怎么做? 大概的思路就是对于某一个数组中的所有数,我们对每一个进行枚举,把当前枚举的数作为三元组的最大值,
继续阅读
icontofig | 发布于 2019-07-02 10:25:10 | 阅读量 114 | FFT
发布于 2019-07-02 10:25:10 | FFT
BZOJ 3527 [ZJOI2014]力 FFT模板题
题解就是把qj除掉,然后可以发现是裸的两个卷积形式,直接上FFT就可以。 这个博客写的非常好,我个人就比较渣了QAQ https://blog.csdn.net/qq_33929112/article/details/54590319 代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const double PI = acos(-1.0); const int maxn&n
继续阅读
icontofig | 发布于 2017-04-01 10:00:46 | 阅读量 298 | FFT
发布于 2017-04-01 10:00:46 | FFT
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <complex> using namespace std; const int maxn = 3e5+5; const doub
继续阅读