Description：

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

$1\leqslant n\leqslant 10^7$

Solution：

首先统计 $f[i]$ 表示长度为 $i$ 的不含回文后缀的回文串个数，那么答案就是： $$ ans=S^n-\sum_{i=2}^nf[i]S^{n-i} $$ 考虑预处理 $f$ 的过程，直觉告诉我们答案应该是： $$ f[n]=S^{\lceil\frac n 2\rceil}-\sum_{i=2}^{\lceil\frac n 2\rceil}f[i]S^{\lceil\frac n 2\rceil-i} $$ 但是后面那个 $\lceil\frac n 2\rceil$ 并不是很好理解，其实这是因为如果一个回文串有一个大于 $\lceil\frac n 2\rceil$ 的回文后缀，那它一定还有一个小于 $\lceil\frac n 2\rceil$ 的回文后缀，如果都减掉的话肯定是不对的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,s,m;

#define MAXN 10000010

int f[MAXN];

int pows[MAXN];

int sum[MAXN];

int main()

{

	freopen("suffix.in","r",stdin);

	freopen("suffix.out","w",stdout);

	scanf("%d%d%d",&n,&s,&m);

	pows[0] = 1;

	for(int i = 1;i <= n;++i)pows[i] = 1ll * pows[i - 1] * s % m;

	for(int i = 2;i <= n;++i)

	{

		f[i] = (pows[(i + 1) / 2] - sum[(i + 1) / 2] + m) % m;

		sum[i] = (1ll * sum[i - 1] * s % m + f[i]) % m;

	}

	int ans = pows[n];

	for(int i = 2;i <= n;++i)

	{

		ans = (ans - 1ll * f[i] * pows[n - i] % m + m) % m;

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}