万径人踪灭 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 1936  Solved: 1076[Submit][Status][Discuss] Description Input Output Sample Input Sample Output HINT   题目大意：给定一个由'a'和'b'构成的字符串，求不

这个题感觉很神呀。将 FFT 和 Manacher 有机结合在了一起。 首先我们不管那个 “不能连续” 的条件，那么我们就可以求出有多少对字母关于某一条直线对称，然后记 $T_i$ 为关于直线 $i$ 对称的字母对的数量，那么答案（暂记为 $Ans$）就会是： $$Ans = \sum 2^{T_i}-1$$ 在不管那个 “不能连续” 的条件的时候，这个应该是显然的。 怎么算的话，我们弄两次。分

Description Input Output Sample Input Sample Output HINT 先在串中两两之间插入#，形成新串s，主要是考虑中心不在列上令$f[i]$表示以i为中心，两边为a或b且相同的对数$f[i]=\sum_{x+y=i*2}[s[x]==s[y]]$注意$s[x]s[y]$不能为#发现这其实是一个卷积，于是FFT，求出f[i]于是通

Solution $ans=$回文子序列$-$回文子串的数目。 后者可以用$manacher$直接求。 前者设$f[i]$表示以$i$为中心的对称的字母对数。 那么回文子序列的数量也就是$\sum_{i=0}^{n-1}2^{f[i]-1}$ 构造两个数组$a[i],b[i]$。若第$i$位为$a$，那么$a[i]=1$，否则$b[i]=1$。 可以发现$a$数组自身卷积就是$a$字

Description Input Solution 考虑先忽略不可以连成一段的条件。 那么，暴力的做法就是，枚举一个中心点，暴力找出旁边有多少个对称的点，设数量为\(x\)，则这个中心点对答案的贡献为\(2^x-1\)。 这样是\(O(n^2)\)的，考虑怎么优化。 对于中心点\(mid\)，能对\(x\)造成贡献的位置\(i,j\)，一定是满足\(i+j=mid*2\)且\(s[i]=

【bzoj3160】万径人踪灭 FFT 题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3160 我是一个傻叉 微笑脸 1 #include<bits/stdc++.h> 2 #define inf 1000000000 3 #define ll long long 4 #define N 200005 5 #de

。。恩 打了四五遍 不会也背出来了。。 BZOJ3160 【听说时限紧？转C++的优势么？】 上AC代码 fft 1 /*Problem: 3160 2 User: cyz666 3 Language: C++ 4 Result: Accepted 5 Time:1992 ms 6 Memory:18492 kb 7 ********

P2895 万径人踪灭 题目描述 如果机房马上要关门了，或者你急着要和MM 约会，请直接跳到第六个自然段。 VFleaKing注意到了这条上山下山的土路，有些地方能欣赏到美景，有些地方则不能。把上山的道路每10cm分为一小段，则对于每一小段，用a 表示能欣赏到美景，用b表示不能欣赏到美景，就能得到一个只含a,b的字符串s。当然由于下山和上山是一条路，所以下山的道路的字符串就是将上山的道路的