题目连接：hdu_4352_XHXJ's LIS
题意：这题花大篇篇幅来介绍电子科大的一个传奇学姐，最后几句话才是题意，这题意思就是给你一个LL范围内的区间，问你在这个区间内最长递增子序列长度恰为K的数有多少个
题解：数位DP+状态压缩，这题首先考虑如何来求数位的LIS，很明显不可能用n*n的方法，考虑nlogn的方法，维护的是一个数组，在这里要严格递增，所以最长的LIS小于10，所以我们可以将这个数组用2进制压缩成一个状态，然后这个2进制1的个数就是LIS的值，如果不懂LIS nlogn的原理：传送门，然后再考虑决策状态：由于这题t比较大，只能初始化一次，所以会影响到前面状态的都不能当作决策条件，比如说inf(表示是否达到上限)，当前位置pos，压缩状态s肯定是要的，然后考虑到我们可以对每一个k进行DP，所以要多开一维来保存k，然后dp[i][j][k] 就是dp的状态保存，i表示考虑到当前第i位，j表示当前的压缩状态，k表示LIS恰好为k的答案
#include<cstdio>
#include<cstring>
#define F(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL; LL n,m,dp[][<<][];
int t,k,dig[],len,ic=; int getnew(int x,int s){
F(i,x,)if(s&(<<i))return (s^(<<i))|(<<x);//维护LIS的数组
return s|(<<x);
}
int getnum(int s){
int ret=;
for(;s;s>>=)if(s&)ret++;
return ret;
}
LL dfs(int pos,int s=,int z=,bool inf=){
if(!pos)return getnum(s)==k;
if(!inf&&~dp[pos][s][k])return dp[pos][s][k];
int end=inf?dig[pos]:;LL ans=;
F(i,,end)ans+=dfs(pos-,(z&&i==)?:getnew(i,s),z&&(i==),inf&&i==end);
if(!inf)dp[pos][s][k]=ans;
return ans;
} LL f_ck(LL x){
for(len=;x;x/=)dig[++len]=x%;
return dfs(len);
} int main(){
scanf("%d",&t);
memset(dp,-,sizeof(dp));
while(t--){
scanf("%I64d%I64d%d",&n,&m,&k);
printf("Case #%d: %lld\n",ic++,f_ck(m)-f_ck(n-));
}
return ;
}