[SCOI2009] windy 数
首先肯定是要做差的：$ans_{[l,r]}=ans_{[r,0]}-ans_{[l-1,0]}$。
现在考虑如何求出 $ans_{[n,0]}$。
定义状态 $f(i,j,k)$，表示第 $i$ 位填 $j$，从高到低的前 $i$ 为是否贴着上界的情况为 $k$（若 $k=1$ 则贴着上界，$k=0$ 则不贴着上界）。
然后我们随便转移一下。
$$f(i,a_i,1)\rightarrow \begin{cases}f(i+1,p,0) & |p-a_i|\ge 2,p<a_{i+1} \\ f(i+1,a_{i+1},1) & |a_{i+1}-a_i|\ge 2\end{cases}$$
转移的意思是，如果前 $i$ 位都贴着上界，则后面这一位不能超过上界，且如果等于上界，则前面 $i+1$ 位都是贴着上界的。与此同时，我们还要满足数字差大于等于 2 的条件。
然后还有转移：
$$\begin{matrix}f(i,j,0)\rightarrow f(i+1,p,0)&|j-p|\ge 2\end{matrix}$$
然后我们要考虑一下前导 0 的情况。
显然前导零在两位之差大于等于 2 的情况下都能正常转移，但是一旦下一位是 1 和 0 的时候就转移不过去了，所以我们单独抽出这两个状态转移。
然后就是特判 0。。。因为这个情况它一位也拆不出来，但要输出 1（因为在计算其他数的时候我们也把 0 算上了）。
初始化就是最高位的那几种取值都是数量为 1。
时间复杂度 $O(\log n)$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
const ll N=15;
ll l,r;
ll f[N+5][N+5][2],a[N+5];
inline ll F(ll n) {
if(n==0) return 1;
memset(f,0,sizeof(f));
ll len=0;
while(n) {a[++len]=n%10;n/=10;}
for(ll i=0;i<a[len];i++) f[len][i][0]=1;f[len][a[len]][1]=1;
for(ll i=len;i>=2;i--) {
for(ll j=0;j<=9;j++) {
for(ll p=0;p<=9;p++) {
if(abs(j-p)>=2) {
f[i-1][p][0]+=f[i][j][0];
}
}
}
f[i-1][0][0]+=1;f[i-1][1][0]+=1;
if(abs(a[i]-a[i-1])>=2) f[i-1][a[i-1]][1]+=f[i][a[i]][1];
for(ll p=0;p<a[i-1];p++) {
if(abs(p-a[i])>=2) {
f[i-1][p][0]+=f[i][a[i]][1];
}
}
}
ll res=0;
for(ll i=0;i<=9;i++) {
res+=f[1][i][0];
}
res+=f[1][a[1]][1];
return res;
}
int main() {
l=read();r=read();
writeln(F(r)-F(l-1));
return 0;
}
|