jzoj 3316. 【BOI2013】非回文数字

Question

当一个数字不包含长度大于1的子回文数字时称为非回文数字。
求$a$~$b$之间的非回文数字。

Solution

比赛是想到数位DP，只需搞一搞回文数字部分为3位或2位的即可。
然后想着怎么求回文数字个数$k$，然后用$x-k$。
刚了1h，结果啥也没刚出来，想到容斥去了。最后交了个暴力17分走起。
就是没想到DP非回文数字个数。
设$f[i][j][k]$表示当前到第$i$位，当前为$j$，上一位为$k$。
且当前$i$以前所组成的数小于原串数 （且符合费回文数字） 的个数。
设$g[i][j][k]$表示当前到第$i$位，当前为$j$，上一位为$k$。
且当前$i$以前所组成的数等于原串数 （且符合费回文数字） 的个数。
小心点前导零以及个位数即可。（赛后又刚了$1.5h$——o(╥﹏╥)o）

Code

#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int num[20],tot=0,g[20][11][11];
ll a,b,f[20][11][11];

void ycl(ll x) {tot=0; while (x>0) num[++tot]=x%10,x/=10;}

ll query(ll x)
{
	ycl(x);num[tot+1]=10;
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	ll ans=0;
	g[tot][num[tot]][10]=1;
	for (int i=1;i<num[tot];i++)
		f[tot][i][10]=1;
	f[tot][10][10]=1;
	for (int i=tot-1;i>0;i--)
	{
		if (num[i+1]!=num[i+2])
		{
			if (num[i]!=num[i+1] && num[i]!=num[i+2])
				g[i][num[i]][num[i+1]]+=g[i+1][num[i+1]][num[i+2]];
			for (int j=0;j<num[i];j++)
				if (j!=num[i+1] && j!=num[i+2])
					f[i][j][num[i+1]]+=g[i+1][num[i+1]][num[i+2]];
		}
		for (int j=0;j<=10;j++)
			for (int k=0;k<=10;k++)
			{
				if ((j==k && j!=10) || !f[i+1][j][k]) continue;
				for (int l=0;l<=9;l++)
				{
					if (j==l || k==l) continue;
					if (l==0 && j==10) continue;
					f[i][l][j]+=f[i+1][j][k];
				}
			}
		f[i][10][10]=1;
	}
	for (int i=0;i<=9;i++)
		for (int j=0;j<=10;j++)
 			if (i!=j) ans+=f[1][i][j];
	ans+=g[1][num[1]][num[2]];
	return ans;
}

int main()
{
//	freopen("num.in","r",stdin);
//	freopen("num.out","w",stdout);
	scanf("%lld%lld",&a,&b);
	if (b<10) printf("%d
",b-a+1);
	else if (a<10) printf("%lld
",query(b)-a+1);
	else printf("%lld
",query(b)-query(a-1));
	return 0;
}