Palisection(Codeforces Beta Round #17E+回文树)

题目链接

传送门

题意

给你一个串串，问你有多少对回文串相交。

思路

由于正着做不太好算答案，那么我们考虑用总的回文对数减去不相交的回文对数。

而不相交的回文对数可以通过计算以\(i\)为右端点的回文串的个数\(\times\)以\(i+1,i+2\dots,n\)为左端点的回文串的个数计算得到。

以\(i\)为右端点的回文串的个数可以直接用回文树\(O(n)\)求出来，以\(i\)为左端点的回文串的个数反着求一遍即可。

不过要注意本题由于数据范围比较大，使用邻接矩阵会导致\(MLE\)，因此需要使用邻接矩阵来代替。

代码实现如下

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<= 1; --i) {
		sum[i] = (sum[i+1] + pam.add(s[i] - 'a' + 1)) % mod;
	}
	pam.init();
	for(int i = 1; i <= n; ++i) {
		int cnt = pam.add(s[i] - 'a' + 1);
		(ans += 1LL * cnt * sum[i+1] % mod) %= mod;
	}
	pam.solve();
	printf("%lld\n", (((1LL * tmp * (tmp-1) / 2 % mod) - ans) % mod + mod) % mod);
    return 0;
}
迷之回文树

相关

标签