文件详细信息

下载本文件

本文件的大小为 1100 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
ll read(){
	int ch=getchar();
	ll num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
int T;
ll l,r,k;
int count1(ll num){
	int ans=0;
	while(num){
		ans+=(num&1);
		num>>=1;
	}
	return ans;
}
int new_state(int state,int k){
	for(int i=k;i<10;i++)
		if(state&(1<<i))
			return(state^(1<<i))|(1<<k);
	return state|(1<<k); 
}
int bit[20];
ll dp[20][1030][12];
ll dfs(int pos,int state,bool limit,bool pre){
	if(pos<0)return count1(state)==k;
	if(!limit&&dp[pos][state][k]!=-1)return dp[pos][state][k];
	ll ans=0;
	int up=limit?bit[pos]:9;
	for(int i=0;i<=up;i++)ans+=dfs(pos-1,(pre&&i==0)?0:new_state(state,i),limit&&(i==up),pre&&(i==0));
	if(!limit)dp[pos][state][k]=ans;
	return ans;
}
ll solve(ll n){
	int pos=0;
	while(n){
		bit[pos++]=n%10;
		n/=10;
	}
	return dfs(pos-1,0,true,true);
}
int main(){
	memset(dp,-1,sizeof(dp));
	T=read();
	for(int task=1;task<=T;task++){
		l=read(),r=read(),k=read();
		printf("Case #%d: %lld\n",task,solve(r)-solve(l-1));
	}
	return 0;
}