[SAM模板题] P3975 [TJOI2015] 弦论

题目思路

对原串建立 S A M SAM SAM，然后分情况考虑：

• t = 0 t = 0 t=0，代表本质不同即为不同，那么我们需要对每个 S A M SAM SAM节点 u u u维护 u u u能够到达的点的数量，即为经过 u u u的本质不同的子串的数量。
• t = 1 t = 1 t=1，代表位置不同即为不同，那么我们考虑对于每个节点 u u u计算经过该点位置不同的子串数量。那么我们可以想到这需要先求串 s s s的出现次数，也就是 e n d p o s ( s ) endpos(s) endpos(s)的大小，而根到 u u u表示的串的 e n d p o s endpos endpos大小为 p a r e n t   t r e e parent\ tree parent tree上 u u u的子树中的前缀点的数量

不难发现，我们可以维护一个 d p [ u ] dp[u] dp[u]表示不同限制下的子串数目，以及每个点的点权。对于 t = 0 t = 0 t=0，所有点的点权都是 1 1 1，否则先 d f s dfs dfs求子树大小作为点权，然后 d f s dfs dfs求答案即可。

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, MOD = 1e9 + 7;

int dp[N], siz[N];

struct SAM{
    int ch[N