TAXID - VOI10 - Mã số thuế
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define DOWN(i,a,b) for(long i=a; i>=b; i--)
#define ll long long
using namespace std;
ll n,q;
long m,p,ct,cd;
long cs[20],c[40];
ll f[20][40][2][2];
void inp() {
cin >>n >>m >>p >>q;
FOR(i,1,(m-1)/2) cin >>c[i];
c[0]=1;
c[(m-1)/2+1]=36;
}
void update(long i,long last,long ok,long lower,long next,long lower2) {
long ok2=ok;
if (next>=cd) ok2=1;
f[i+1][next][ok2][lower2]+=f[i][last][ok][lower];
}
ll get(ll n) {
ll save=n;
cs[0]=0;
while (n) {
cs[0]++;
n/=36;
}
n=save; long now=cs[0];
while (n) {
cs[now]=n%36;
n/=36;
now--;
}
memset(f,0,sizeof f);
f[0][0][0][0]=1LL;
ct=c[(p+1)/2]-1;
cd=c[(p+1)/2-1];
FOR(i,0,cs[0]-1)
FOR(last,0,ct)
FOR(ok,0,1) {
FOR(next,0,ct)
update(i,last,ok,1,next,1);
FOR(next,0,min(ct,cs[i+1]-1))
update(i,last,ok,0,next,1);
if (cs[i+1]<=ct)
update(i,last,ok,0,cs[i+1],0);
}
ll res=0LL;
FOR(last,0,ct)
res+=f[cs[0]][last][1][1];
return res;
}
void print(ll res) {
if (!res) return ;
print(res/36);
long u=res%36;
if (u<10) printf("%ld",u);
else printf("%c",(char)('a'+u-10));
}
void solve() {
if (p%2==0)
q=1+get(n+1)-q;
ll l=0LL, r=n, res=n;
while (l<=r) {
ll mid=(l+r)/2;
if (get(mid+1)>=q) {
res=mid;
r=mid-1;
} else l=mid+1;
}
print(res);
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
inp();
solve();
return 0;
}