数位DP!
dp[i][j][k]:第i位数,状态为j,长度为k
代码如下:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
using namespace std;
ll dp[][][];
int bit[],k;
int Getlen (int sta)//求出最长上升子序列的长度
{
int ret = ;
while (sta)
{
ret += (sta&);
sta >>= ;
}
return ret;
} int Getnew(int x , int sta)//更新当前数的最长上升子序列的状态
{
int i;
for (i = x ; i <= ; i++)
if ((sta & (<<i)))
return (sta-(<<i))|(<<x);
return sta|(<<x);
}
ll dfs(int pos,int s,bool z,bool f)
{
if(pos==-) return Getlen(s)==k;
if(!f&&dp[pos][s][k]!=-) return dp[pos][s][k];
ll ans=;
int e=f?bit[pos]:;
for(int i=;i<=e;i++){
ans+=dfs(pos-,(z&&i==)?:Getnew(i,s),z&&i==,f&&i==e);
}
if(!f&&dp[pos][s][k]==-) dp[pos][s][k]=ans;
return ans;
}
ll cal(ll n)
{
int m=;
while(n){
bit[m++]=n%;
n/=;
}
return dfs(m-,,,);
}
int main()
{
int t,i,j,ca=;
ll a,b;
scanf("%d",&t);
memset(dp,-,sizeof(dp));
while(t--){
scanf("%I64d%I64d%d",&a,&b,&k);
printf("Case #%d: %I64d\n",++ca,cal(b)-cal(a-));
}
return ;
}