[组合] 各个位数上的数字都不相同的正整数

realnumber

小明心中有一种美丽整数，这种数是指各个位数上的数字都不相同的正整数.
例如：12345是美丽整数，121就不是美丽整数.
a 是某正整数，问闭区间内[1，a]有几个美丽整数.
样例a=10,则有10个
a=1000,有738个.

realnumber

是的，通式要分很多类，暂时没找到好算法
小朋友编的，通过

1. #include<stdio.h>
   
2. using namespace std;
   
3. 
   
4. int h(int n,int m){
   
5.         int H=1;
   
6.         for(int i=0;i<m;i++,n--)H*=n;
   
7.         return H;
   
8. }
   
9. 
   
10. int g(int n){
    
11.         if(!n)return 0;
    
12.         int a[10],num=0,G=0;
    
13.         bool b[10]={1,1,1,1,1,1,1,1,1,1};
    
14.         while(n){
    
15.                 num++;
    
16.                 a[num]=n%10;
    
17.                 n/=10;
    
18.         }
    
19.         for(int i=num;i>1;i--){
    
20.                 for(int j=!(num-i);j<a[i];j++)if(b[j])G+=h(10-num+i-1,i-1);
    
21.                 if(b[a[i]]){
    
22.                         b[a[i]]=0;
    
23.                 }
    
24.                 else return G;
    
25.         }
    
26.         for(int j=!(num-1);j<=a[1];j++)if(b[j])G++;
    
27.         return G;
    
28. }
    
29. 
    
30. int t(int n){
    
31.         int T=0;
    
32.         int num=0,sum=9;
    
33.         while(n>sum){
    
34.                 num++;
    
35.                 sum=sum*10+9;
    
36.                 T+=9*h(9,num-1);
    
37.         }
    
38.         return T;
    
39. }
    
40. 
    
41. int f(int n){
    
42.         int F=0;
    
43.         F+=t(n);
    
44.         F+=g(n);
    
45.         return F;
    
46. }
    
47. 
    
48. int main(){
    
49.         int t;
    
50.         scanf("%d",&t);
    
51.         for(int i=0;i<t;i++){
    
52.                 int l,r;
    
53.                 scanf("%d%d",&l,&r);
    
54.                 printf("%d\n",f(r)-f(l-1));
    
55.         }
    
56.         return 0;
    
57. }

复制代码