统计$[L,R]$内LIS长度为$k$的数的个数，$Q \le 10000,L,R < 2^{63}-1,k \le 10$。
首先肯定是数位DP。然后考虑怎么做这个dp。如果把$k$记录到状态里没有用。需要找到有效方法统一的表示前面填好的数的特点方便之后的填数。
回顾LIS过程，当前数结尾的LIS是前面比他小的数的LIS中的max+1，但是没有办法记录下来，因为如果记录下前面以数字$0\sim 9$结尾的maxLIS的话空间不够。
尝试换一种表示方法。回顾LIS的$O(nlogn)$做法，发现维护了一个$g$数组表示长度$i$的LIS结尾最小$g[i]$，这个数组是单调增的。
这是发现可以方便记录——用一个数$S$，把二进制第$g[i]$位$\text{or}$到$S$上去。这样，$S$中是$1$的位置从小到大写下来就是$g$数组了。
设$f(len,S,n,lead,limit)$，$S$是之前填好的数的$g$数组，$n$是前面的最长LIS长度。枚举当前位填啥，通过二分确定新的$S$，然后边界判一下是否$n=k$就好了。
code细节：
- 注意到$k$是相互独立的，可以分别进行统计，$f[k][...]$表示满足……条件（见上）之下、LIS长度为$k$的数的个数。
- 注意判断前导0。
- 加了一些剪枝，虽然并没有什么用。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define dbg(x) cerr << #x << " = " << x <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
ll f[][][<<][],b[],tot;
ll L,R;
int T,k;
ll dp(int len,int S,int n,int lead,int limit){
if(!len)return n==k;
if(n>k||n+len<k)return ;
if(!limit&&~f[k][len][S][lead])return f[k][len][S][lead];
int num=limit?b[len]:;ll ret=;
if(lead){
ret+=dp(len-,S,n,lead,limit&&!num);
for(register int i=;i<=num;++i)ret+=dp(len-,<<i,,,limit&&i==num);
}
else{
int a[]={},m=;
for(register int i=;i<=;++i)if(S&(<<i))a[++m]=i;
for(register int i=;i<=num;++i){
int pos=lower_bound(a+,a+m+,i)-a;
if(pos>m)ret+=dp(len-,S|(<<i),n+,,limit&&i==num);
else ret+=dp(len-,S^(<<a[pos])|(<<i),n,,limit&&i==num);
}
}
return limit?ret:f[k][len][S][lead]=ret;
}
inline ll solve(ll x){
tot=;while(x)b[++tot]=x%,x/=;
return dp(tot,,,,);
} int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
read(T);memset(f,-,sizeof f);
for(register int i=;i<=T;++i)
read(L),read(R),read(k),printf("Case #%d: %lld\n",i,solve(R)-solve(L-));
return ;
}
总结：还是那句话，用有效的方法表示好填好的数的性质。