poj1715Hexadecimal Numbers（数位dp）

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 100000
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 LL s;
18 LL c[30][30];
19 int a[30];
20 bool vis[30];
21 void init()
22 {
23     int i,j;
24     for(i = 1; i <= 15 ; i++)
25     {
26         c[i][0] = 1;
27         for(j = 1; j <= i; j++)
28         {
29             int k = j,g=i;
30             c[i][j] = 1;
31             while(k)
32             {
33                 c[i][j]*=g;
34                 k--;
35                 g--;
36             }
37         }
38     }
39     for(i = 1 ;i <= 8; i++)
40     {
41         s+=15*c[15][i-1];
42     }
43 }
44 int main()
45 {
46     int i,j,g,e;
47     LL n;
48     init();
49     while(cin>>n)
50     {
51         memset(vis,0,sizeof(vis));
52         n = s-n+1;
53         LL ans=0;
54         int ts = 1,len;
55         for(i = 1; i <= 8 ; i++)
56         {
57             ans+=15*c[15][i-1];
58             if(ans>=n)
59             {
60                 n = n-ans+15*c[15][i-1];
61                 len = i;
62                 break;
63             }
64         }
65         int o = 1;
66         for(i = len ; i>= 1; i--)
67         {
68             ans = 0;
69             int kk;
70             int tt;
71             if(i==len) tt = 1;
72             else tt = 0;
73             for(i==len?j = 1:j=0; j <= 15; j++)
74             {
75                 if(vis[j]) continue;
76                 ans+=c[16-o][i-1];
77                 if(ans>=n)
78                 {
79                     n = n-ans+c[16-o][i-1];
80                     a[i] = j;
81                     vis[j] = 1;
82                     o++;
83                     break;
84                 }
85                 kk = j;
86             }
87         }
88         for(j = len ; j >= 1 ; j--)
89         {
90             if(a[j]>=10)
91             printf("%c",a[j]-10+‘A‘);
92             else
93             cout<<a[j];
94         }
95         puts("");
96     }
97     return 0;
98 }