First, let’s consider a string with the same alphabet \(S\), the new string is \(T\):

• \(|S|<10\), then \(|T|=2\).
• \(|S|<100\), then \(|T|=3\).
• \(|S|<1000\), then \(|T|=4\).
• \(|S|<10000\), then \(|T|=5\).

So, a function can be defined as this: \( g(x)=\begin{cases} 2&(1\le x<10)\\ 3&(10\le x<100)\\ 4&(100\le x<1000)\\ 5&(1000\le x<10000)\end{cases} \)

Then, the problem can be solved with Dynamic Programming (DP).

The definition of DP

\(f[i][j]:=\) the number of strings that the original length is \(i\) and the new length is \(j\).

Since the \(i,j\) are in the range \([1,n]\), so there are \(O(N^2)\) states.

The initial value of DP

First of all, let \(f[i][g(i)]=26\) and fill the remaining elements with \(0\).

The transition of DP

Compute in the increasing order of \(i\). For \(j=1,2,...,n\) and \(k=1,2,...,n-i\).

• if \(j+g(k)\le n\), add \(25\times f[i][j]\) to \(f[i+k][j+g(k)]\), since the adjacent alphabets are different.

Answer

Finally, the answer is \(\sum_{j<i<n} f[i][j]\).

Now the computational complexity is \(O(N^3)\), which is not enough to pass this problem.

The optimization of DP

We can find that the \(g(k)\) is in \([2,3,4,5]\), so we can use fenwick tree to optimize it.

There are \(n\) fenwick trees, the \(i\)-th is called \(C[i]\).

For each \(i,j\):

• Add \(25\times f[i][j]\) to the \((i+1)\)-th element of \(C[j+2]\), and subtract it to the \((i+10)\)-th element of \(C[j+2]\).
• Add \(25\times f[i][j]\) to the \((i+10)\)-th element of \(C[j+3]\), and subtract it to the \((i+100)\)-th element of \(C[j+3]\).
• Add \(25\times f[i][j]\) to the \((i+100)\)-th element of \(C[j+4]\), and subtract it to the \((i+1000)\)-th element of \(C[j+4]\).
• Add \(25\times f[i][j]\) to the \((i+1000)\)-th element of \(C[j+5]\).

Now the computational complexity is \(O(N^2\log N)\), which is enough to pass this problem.

Code:

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ret return
using namespace std;
bool smoke_alarm1;
const int N=3e3+7;
const int Pa=998244353;
il ll read(){
	char c;
	ll x=0,f=1;
	while(!isdigit(c=getchar())){
		if(c==EOF)
			return -1321321327;
		f-=(c=='-')<<1;
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+f*(c^48);
		c=getchar();
	}
	ret x;
}
il void write(ll x,char ch='\n'){
	if(x<0)
		putchar('-');
	static char r[55];
	int cnt=0;
	do{
		int y=x%10;
		y=abs(y);
		r[++cnt]=y|48;
		x/=10;
	}while(x);
	for(int i=cnt;i;--i)
		putchar(r[i]);
	if(ch)
		putchar(ch);
}
template<class T,class T2>il void add(T& x,T2 y,int p=Pa){
	x+=y;
	if(x>=p)
		x-=p;
}
ll n,p,res,f[N][N];
struct BIT{
	ll c[N];
	BIT(){
		memset(c,0,sizeof(c));
	}
	void Add(int x,ll k){
		++x;
		for(;x<=n+1;x+=x&-x)
			add(c[x],k,p);
	}
	ll Ask(int x){
		++x;
		ll k=0;
		for(;x;x-=x&-x)
			add(k,c[x],p);
		ret k;
	}
}g[N];
int main(){
	n=read();
	p=read();
	g[2].Add(1,26);
	g[2].Add(10,p-26);
	g[3].Add(10,26);
	g[3].Add(100,p-26);
	g[4].Add(100,26);
	g[4].Add(1000,p-26);
	g[5].Add(1000,26);
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j){
		f[i][j]=g[j].Ask(i);
		if(!f[i][j])
			continue;
		g[j+2].Add(i+1,25*f[i][j]%p);
		g[j+2].Add(i+10,p-25*f[i][j]%p);
		g[j+3].Add(i+10,25*f[i][j]%p);
		g[j+3].Add(i+100,p-25*f[i][j]%p);
		g[j+4].Add(i+100,25*f[i][j]%p);
		g[j+4].Add(i+1000,p-25*f[i][j]%p);
		g[j+5].Add(i+1000,25*f[i][j]%p);
	}
	for(int i=1;i<n;++i)
		add(res,f[n][i],p);
	write(res);
	ret 0;
}

Since my English is poor, there may be some gramma mistakes.