传送门：BNUOJ 52325 Increasing or Decreasing
题意：求[l,r]非递增和非递减序列的个数
思路：数位dp，dp[pos][pre][status]
- pos：处理到第几位
- pre：前一位是什么
- status：是否有前导零
递增递减差不多思路，不过他们计算的过程中像5555,444 这样的重复串会多算，所以要剪掉。个数是(pos-1)*9+digit[最高位]，比如一位重复子串是：1,2,3,4...9,9个，二位重复子串：11,22,33,44,...,99,9个；同理，其他类推；
不过这个题如果dp值每算完一个[l,r]就清零，会超时。那么我们这么分析，算[l1,r1]，[l2,r2]这两个区间时，dp是否真的有必要清零呢，答案是否定的，记忆化搜索的过程中记录的dp值如果计算过，那么当其他值算到他时，这个值是可以用的。具体的自己想想就好了
/**************************************************************
Problem:BNUOJ 52325 Increasing or Decreasing
User: youmi
Language: C++
Result: Accepted
Time: 380 ms
Memory: 1632 KB
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%lld",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%lld\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=*atan(1.0); using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
char c; int flag = ;
for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';
for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n * + c - ''; n *= flag;
}
ll Pow(ll base, ll n, ll mo)
{
ll res=;
while(n)
{
if(n&)
res=res*base%mo;
n>>=;
base=base*base%mo;
}
return res;
}
//*************************** int n;
const int maxn=+;
const ll mod=;
int digit[];
ll dp0[][][];
ll dp1[][][];
int tot=;
ll dfs0(int pos,int pre,int status,int limit)
{
if(pos<)
return status;
if(!limit&&dp0[pos][pre][status]!=-)
return dp0[pos][pre][status];
int ed=limit?digit[pos]:;
ll res=;
if(status==)
{
for(int i=;i<=min(pre,ed);i++)
{
if(i==)
res+=dfs0(pos-,,,limit&&(i==ed));
else
res+=dfs0(pos-,i,,limit&&(i==ed));
}
}
else
{
for(int i=;i<=min(ed,pre);i++)
res+=dfs0(pos-,i,status,limit&&(i==ed));
}
if(!limit)
dp0[pos][pre][status]=res;
return res;
}
ll dfs1(int pos,int pre,int status,int limit)
{
if(pos<)
return status;
if(!limit&&dp1[pos][pre][status]!=-)
return dp1[pos][pre][status];
int ed=limit?digit[pos]:;
ll res=;
for(int i=pre;i<=ed;i++)
res+=dfs1(pos-,i,status||i,limit&&(i==ed));
if(!limit)
dp1[pos][pre][status]=res;
return res;
}
void work(ll num)
{
tot=;
while(num)
{
digit[tot++]=num%;
num/=;
}
}
ll solve(ll num)
{
if(num==)
return ;
ll ans=(tot-)*+digit[tot-];
ll temp=;
int tt=;
while(tt<tot)
temp=temp*+digit[tot-],tt++;
if(temp>num)
ans--;
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
int T_T;
scanf("%d",&T_T);
ones(dp0);
ones(dp1);
for(int kase=;kase<=T_T;kase++)
{
ll num;
read(num);
num--;
work(num);
ll temp0=dfs0(tot-,,,);
temp0+=dfs1(tot-,,,);
temp0-=solve(num);
read(num);
work(num);
ll temp1=dfs0(tot-,,,);
temp1+=dfs1(tot-,,,);
temp1-=solve(num);
ptlld(temp1-temp0);
}
return ;
}