题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4352
题意：求区间L到R之间的数A满足A的的数位的最长递增序列的长度为K的数的个数。
分析：数位dp，dp[i][j][k]表示后面还有i位，此时状态为k，最长上升子序列为j时的总数（在非限制即0~9任意填的情况下）。
要真正理解LIS的本质才能解这题，state状态维护的是前面上升子序列中出现的数字（二进制状态压缩），前面设状态为167（state为001100001），假设此时i=2，维护上升序列长度为3，应该把6变为2（此时state为001000011）127，最长上升子序列长度不变，但能让后面更多的数加进来。
这题还得注意前导0的影响。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-9
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int dig[];
LL dp[][][];
int k;//当前位，上升子序列出现的数字的状态，长度，是否上限，是否前导0
LL dfs(int pos,int state,int num,int limit,int fzore)
{
if(!pos)
{
return k==num;
}
if(!limit&&~dp[pos][k][state])return dp[pos][k][state];
int len=limit?dig[pos]:;
LL ans=;
for(int i=;i<=len;i++)
{
if((<<i)>state)
ans+=dfs(pos-,(fzore&&!i)?:state|(<<i),(fzore&&!i)?:num+,limit&&i==len,fzore&&!i);
else if(state&(<<i))
ans+=dfs(pos-,state,num,limit&&i==len,fzore&&!i);
else
{
for(int j=i+;j<=;j++)
if(state&(<<j))
{
ans+=dfs(pos-,state-(<<j)|(<<i),num,i==len&&limit,fzore&&!i);
break;
}
}
}
if(!limit)dp[pos][k][state]=ans;
return ans;
}
LL solve(LL x)
{
int len=;
while(x)
{
dig[++len]=x%;
x/=;
}
return dfs(len,,,,);
}
int main()
{
int T,cas=;
FILL(dp,-);
scanf("%d",&T);
while(T--)
{
LL a,b;
scanf("%I64d%I64d%d",&a,&b,&k);
printf("Case #%d: ",cas++);
printf("%I64d\n",solve(b)-solve(a-));
}
}