For example, when she see a number, she would think whether the digits of a number are strictly increasing. If you consider the number as a string and can get a longest strictly increasing subsequence the length of which is equal to k, the power of this number is k.. It is very simple to determine a single number’s power, but is it also easy to solve this problem with the numbers within an interval? xhxj has a little tired，she want a god cattle to help her solve this problem,the problem is: Determine how many numbers have the power value k in [L，R] in O(1)time.
InputFirst a integer T(T<=10000),then T lines follow, every line has three positive integer L,R,K.(
0<L<=R<2 63-1 and 1<=K<=10).OutputFor each query, print "Case #t: ans" in a line, in which t is the number of the test case starting from 1 and ans is the answer.
Sample Input
1
123 321 2
Sample Output
Case #1: 139
题意
求[L,R]中符合最长上升子序列为k的个数，一开始以为子序列是连续的，导致疯狂wa，qwq。
题解
思路：
dp[pos][sta][k]
pos:搜索到第几位
sta：之前的最长上升子序列的状态。
k：就是输入的那个k
此题的难点就在于中间的那一维--sta。
sta的二进制每一位，都对应了数位上的一个数字。
举例来说：如果sta按照数字13425来更新。
首先遇到1，变成 0100000000 （或者0000000010，其实这是完全一样的，只要保证不同状态的sta不一样就行了）
然后遇到3，很明显，之前没有比3更大的数字，然后变成0101000000
遇到4，sta变成0101100000
在这里打断一下，不能看出，sta中1的个数，就是LIS的长度。
然后遇到2，这时大于等于2的有一个3.于是把3的二进制1交给2，sta变成0110100000
为什么这么做？？？？？
首先我们知道，这样做绝不会改变1的个数，如果之前出现过2，那么sta就不会变化，否则就把之后最近的那个1挪到当前位置。
然后再看这4个数字：1342
如果之后出现的数字有比这四个数字都大的，那么之前究竟是1243还是1342都对后方的更新没有影响了。
就如同例子中的5，它只需知道，在之前出现的数字中最大的没有自己大就行了，因为只要这样，就可把5位置的0变成1。
注意：如果有多种状态，（ 1243 ，1342 ），只要对后续影响相同，就可以看做同一种状态。
如果之后出现的数字没有比这四个数都大的，那么还是不会改变1的个数。
但是，出现数字2的时候，第二个1向前挪了一位，这实际上是把LIS为2的序列由13变成了12，这里对后续的影响是不同的，可以手推323来解答你的困惑。
于是到此我们就知道了sta的真正含义。
如果sta的第a位上为1，并且之前（包括自己）有b个1，那么长度为b的上升序列的末尾的最小值就是a
这里还要判断前面是不是有前导0，不然01会被当成LIS是2，但是其实是1.
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define mes(p,b) memset(p,b,sizeof(p)) int t,k,a[20];ll l,r,dp[20][1025][11]; int new_sta(int x,int n){ rep(i,n,9){ if((1<<i)&x) return (x^(1<<i))|(1<<n); } return x|(1<<n); } int cal(int x){ int cnt=0; while(x){ cnt+=x&1; x>>=1; } return cnt; } ll dfs(int pos,int sta,bool limit,bool lead){ if(pos==-1) return cal(sta)==k; if(!limit&&!lead&&dp[pos][sta][k]!=-1) return dp[pos][sta][k]; int up=limit?a[pos]:9; ll ans=0; rep(i,0,up){ ans+=dfs(pos-1,(lead&&i==0)?0:new_sta(sta,i),limit&&i==up,lead&&!i); } if(!limit&&!lead) dp[pos][sta][k]=ans; return ans; } ll solve(ll x){ int pos=-1; while(x>0){ a[++pos]=x%10; x/=10; } return dfs(pos,0,1,1); } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>t; mes(dp,-1); rep(i,1,t){ cin>>l>>r>>k; cout<<"Case #"<<i<<": "<<solve(r)-solve(l-1)<<endl; } return 0; }