Codeforces 121 C Lucky Permutation

問題

lucky numberとは10進数で表したときに、全ての桁の数字が4または7である数を言う。

1からnまでの整数の順列のうち、k番目のものについて、
それぞれの数字をa[1],a[2],...,a[n]とおく。

1≦i≦nで、iがlucky numberかつa[i]がlucky numberであるようなiの個数を求めよ。

制約条件

n,k≦10^9

方針

k番目の順列は、kが10^9以下なので、
順番が入れ替わっているのはせいぜい後ろの20項くらいである。

したがって、後ろの20項くらいだけ、具体的に順列を求めてやって、
iとa[i]がともにlucky numberになっている個数を数えればよい。

それに、残りのn-20項でlucky numberになっている数
（これは、1,2,3,...,n-20と並んでいるはずなので、単にlucky numberの数を数えるだけでよい）を足してやればよい。

ソースコード

const int LIM=(int)1e9;
int n,k;
ll fact[20];

vector<ll> lucky;
void gen(ll c){
  lucky.pb(c);
  if(c*10+4<LIM)gen(c*10+4);
  if(c*10+7<LIM)gen(c*10+7);
}
bool islucky(int x){
  for(;x;x/=10)if(x%10!=4&&x%10!=7)return 0;
  return 1;
}
void run(){
  cin>>n>>k;
  fact[0]=1;
  rep(i,19)fact[i+1]=fact[i]*(i+1);
  
  int l=0;
  for(;fact[l]<k;l++);
  if(l>n){
    cout<<-1<<endl;
    return;
  }
  
  lucky.clear(); gen(0); 
  sort(all(lucky));
  
  bool use[20]={};
  int ans[20];
  rep(i,l){
    int ix=0;
    while(fact[l-i-1]<k)ix++, k-=fact[l-i-1];
    rep(j,l)if(!use[j]){
      if(ix--==0){
        use[j]=1;
        ans[i]=n-l+j+1;
        break;
      }
    }
  }
  
  int cnt=upper_bound(all(lucky),n-l)-lucky.begin();
  cnt--;
  
  rep(i,l)if(islucky(n-l+i+1)&&islucky(ans[i]))cnt++;
  cout<<cnt<<endl; 
}