定义:cnt[L][K]表示长度为L,最高位为K的满足条件C的个数。
首先预处理出cnt数组，枚举当前长度最高位和小一个长度的最高位，如果相差大于2则前一个加上后一个的方法数。
然后给定n，计算[1,n-1]中满足条件C的数的个数。
设有K位数，则不足K位的累加，然后枚举K位数的情况，从高位到低位枚举，每次枚举到比该位小1的数，注意：如果某时刻该数中有两位相差大于2，则再枚举下去已经没有意义，因为以后的数再也不会满足条件C，这时退出即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#define Mod 1000000007
#define ll long long
using namespace std;
#define N 100007 ll cnt[][]; //cnt[L][K]:长度为L,最高位为K的满足条件C的数的个数
ll NUM[]; ll DP(ll a) //[1,n-1]
{
int i,j,K;
int pre,head;
ll res = ;
K = ;
while(K <= && NUM[K] <= a)
K++;
K--;
//cout<<"K is "<<K<<endl;
for(i=;i<K;i++) //所有小于a长度的长度
for(j=;j<=;j++) //所有首位
res += cnt[i][j];
head = a/NUM[K]; //数a的首位
for(i=;i<head;i++) //从1开始（不含前导0）
res += cnt[K][i];
a %= NUM[K]; //去除首位
pre = head; //多一位的首位
for(i=K-;i>=;i--) //长度逐次递减,高位到低位
{
head = a/NUM[i];
for(j=;j<head;j++) //小于a的当前位的数做首位
if(abs(pre-j) >= )
res += cnt[i][j];
if(abs(head-pre) < ) //如果前面某两位出现差小于2，再枚举后面的数就没意义了，因为无论如何都不会满足了。
break;
pre = head;
a %= NUM[i]; //一个一个去除
}
return res;
} int main()
{
int i,j,l,k;
ll a,b;
j = ;
NUM[j++] = 0LL;
for(i=;i<=;i++)
NUM[j++] = (ll)pow(,i-);
//for(i=0;i<j;i++)
//cout<<NUM[i]<<" ";
//cout<<endl;
memset(cnt,,sizeof(cnt));
for(k=;k<=;k++)
cnt[][k] = ;
for(l=;l<=;l++)
{
for(i=;i<=;i++) //长度为l时的首位
{
for(k=;k<=;k++) //长度为l-1时的首位
{
if(abs(k-i) >= )
cnt[l][i] += cnt[l-][k];
}
}
}
for(k=;k<=;k++) //10^18
if(abs(-k) >= )
cnt[][] += cnt[][k]; while(scanf("%lld%lld",&a,&b)!=EOF)
{
printf("%lld\n",DP(b+)-DP(a));
}
return ;
}