回文后缀（suffix）

题目描述

给定字符集大小 SS ，问有多少个长度为 NN 的字符串不存在长度 >1>1 的回文后缀。

答案对 MM 取模。

输入格式

第一行两个正整数 n, kn,k，表示树的点数和特殊点的数量。kk 为偶数。

接下来 n − 1n−1 行每行三个正整数 a, b, ca,b,c，表示 aa 和 bb 两点之间有一条边权为 cc 的无向边。

接下来一行 kk 个互不相同的 [1, n][1,n] 的正整数，为 kk 个特殊点的编号。

输入格式

一行三个数，分别为N, S, MN,S,M。

输出格式

一个数表示答案。

 

---

solution

考虑从后往前加数。

令g[i]表示后i位符合要求的串个数。

考虑从gi-1转移到gi，我们用随便放的方案减去不合法的。

而不合法的只可能是i~n为回文串

那么取f[i]=g[1+i/2]，i/2即为回文串一半

g[i]=S*g[i-1]-f[i-1] 即可。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long long#define maxn 10000007using namespace std;int n; ll S,mod,f[maxn],g[maxn];int main(){ cin>>n>>S>>mod; f[1]=g[1]=S; for(int i=2;i<=n;i++){ g[i]=(S*g[i-1])%mod-f[i-1]; g[i]%=mod; f[i]=g[(i/2)+1]; } g[n]=(g[n]%mod+mod)%mod; cout<
             
              <