Lightoj 1060 - nth Permutation

http://lightoj.com/volume_showproblem.php?problem=1060

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long int
4. ll permute[26];
5. string s;
6. ll nth;
7. int a[26];
8. void print(){
9.     for(int i = 0; i <26; i++) cout<<a[i]<<" ";
10. }
11. void per(){
12.     permute[0] = 1;
13.     for(int i = 1; i <26; i++) permute[i] = permute[i-1]*i;
14. }
15. ll possible(int n){
16.     ll ans = permute[n];
17.     for(int i = 0; i <26; i++) ans/= permute[a[i]];
18.     return ans;
19. }
20.  
21. string solve(int sz){
22.     string t;
23.     while(sz){
24.         ll upto = 0;
25.  
26.         bool found = false;
27.         for(int i = 0; i <26 && !found; i++){
28.             if(a[i]== 0)continue;
29.             a[i]--;
30.             ll now = possible(sz-1);
31.             //acout<<now<<" now upto "<<upto<<" nth "<<nth<<endl;
32.             if(now+upto>=nth){
33.                 nth-= upto;
34.                 t+= (char)('a'+i);
35.                 found = true;
36.                 sz--;
37.             }
38.             else{
39.                 upto+=now;
40.                 a[i]++;
41.             }
42.         }
43.         if(!found)break;
44.     }
45.     return t;
46. }
47.  
48. int main(){
49.     int ts;
50.     cin>>ts;
51.     per();
52.     for(int i = 1; i <=ts; i++){
53.     memset(a,0, sizeof(a));
54.     cin>>s;
55.     cin>>nth;
56.     for(int i = 0; i <s.size(); i++)a[s[i]-'a']++;
57.     if(nth>possible(s.size())) cout<<"Case "<<i<<": "<<"Impossible"<<endl;
58.     else cout<<"Case "<<i<<": "<<solve(s.size())<<endl;
59.     }
60.     return 0;
61. }