引用：最长上升子序列nlogn算法
在川大oj上遇到一道题无法用n^2过于是，各种纠结，最后习得nlogn的算法
最长递增子序列，Longest Increasing Subsequence 下面我们简记为 LIS。
排序+LCS算法 以及 DP算法就忽略了，这两个太容易理解了。
假设存在一个序列d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出来它的LIS长度为5。n
下面一步一步试着找出它。
我们定义一个序列B，然后令 i = 1 to 9 逐个考察这个序列。
此外，我们用一个变量Len来记录现在最长算到多少了
首先，把d[1]有序地放到B里，令B[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1
然后，把d[2]有序地放到B里，令B[1] = 1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解吧。这时Len=1
接着，d[3] = 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[1..2] = 1, 5，Len＝2
再来，d[4] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[1..2] = 1, 3，Len = 2
继续，d[5] = 6，它在3后面，因为B[2] = 3, 而6在3后面，于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6，还是很容易理解吧？ Len = 3 了噢。
第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3
第7个, d[7] = 8，它很大，比4大，嗯。于是B[4] = 8。Len变成4了
第8个, d[8] = 9，得到B[5] = 9，嗯。Len继续增大，到5了。
问L到R，各位数字组成的严格上升子序列的长度为K的个数。
* 0<L<=R<263-1 and 1<=K<=10
* 注意这里最长上升子序列的定义，和LIS是一样的，不要求是连续的
* 所以用十位二进制表示0~9出现的情况，和O(nlogn)求LIS一样的方法进行更新
解法：
很显然要数位DP，先考虑LIS的nlogn解法，我们用dp[len]记录LIS长度为len时的最后一个数的大小，然后不断更新这些值，让每一个值都尽可能小，比如我现在的LIS是1 2 4 6，这时候下一个数是3,那么我们就要更新成1 2 3 6,让前面的数尽可能的小，这样就是为了能让后面的数有更多的机会被加入。
同理，因为数字只有10个，我们可以状态压缩，记录每个数字是否出现在当前的LIS中，然后根据这个状态，用前面的办法转移就行了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <stack>
using namespace std;
typedef long long ll;
#define PI 3.1415926535897932
#define E 2.718281828459045
#define INF 0xffffffff//0x3f3f3f3f
#define mod 997
const int M=1005;
int n,m;
int cnt;
int sx,sy,sz;
int mp[1000][1000];
int pa[M*10],rankk[M];
int head[M*6],vis[M*100];
int dis[M*100];
ll prime[M*1000];
bool isprime[M*1000];
int lowcost[M],closet[M];
char st1[5050],st2[5050];
int len[M*6];
typedef pair<int ,int> ac;
//vector<int> g[M*10];
ll dp[50][1<<10][50];
int has[10500];
int month[13]= {0,31,59,90,120,151,181,212,243,273,304,334,0};
int dir[8][2]= {{0,1},{0,-1},{-1,0},{1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
void getpri()
{
ll i;
int j;
cnt=0;
memset(isprime,false,sizeof(isprime));
for(i=2; i<1000000LL; i++)
{
if(!isprime[i])prime[cnt++]=i;
for(j=0; j<cnt&&prime[j]*i<1000000LL; j++)
{
isprime[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
struct node
{
int v,w;
node(int vv,int ww)
{
v=vv;
w=ww;
}
};
vector<int> g[M*100];
char str[100005];
int ind[2550];
int bit[50];
int K;
//dp[i][j][k]:i为当前进行到的数位，j状态压缩，为10个数字出现过的，其中1的个数就是最长上升子序列，k要求的上升子序列的长度
int get_news(int s,int x)//更新状态，满足的位用1替换，把被替换的消成0，则1的个数为最长上升子序列长度，带1的下标组成的序列为该数的最长上升子序列
{
for(int i=x; i<10; i++)
if(s&(1<<i))return (s^(1<<i))|(1<<x);
return s|(1<<x);
}
int getnum(int s)//统计1的个数
{
int ans=0;
while(s)
{
if(s&1)ans++;
s>>=1;
}
return ans;
}
ll dfs(int cur,int s,int e,int z)
{
if(cur<0) return getnum(s)==K;
if(!e&&!z&&dp[cur][s][K]!=-1) return dp[cur][s][K];
int endx=e?bit[cur]:9;
ll ans=0;
for(int i=0; i<=endx; i++)
{
if(z&&!i) ans+=dfs(cur-1,0,e&&i==endx,1);
else ans+=dfs(cur-1,get_news(s,i),e&&i==endx,0);
}
if(!e&&!z) dp[cur][s][K]=ans;
return ans;
}
ll solve(ll n)
{
int len=0;
while(n)
{
bit[len++]=n%10;
n/=10;
}
return dfs(len-1,0,1,1);
}
int main()
{
int i,j,k,t;
ll l,r;
int cas=0;
memset(dp,-1,sizeof(dp));
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d%d",&l,&r,&K);
printf("Case #%d: %I64d\n",++cas,solve(r)-solve(l-1));
}
return 0;
}