[HOJ] 232 - DNA

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 50005
char s[N],cc[5]="ACGT";
long long int dp[N][4][11]={0};
int add2[N]={0};
int main(){
    int n,k,i,x,y,a,b,c;
    long long int r,add,pre;
    scanf("%d%d%lld%s",&n,&k,&r,&s[1]);
    k-=1;
    s[0]='A';
    dp[n+1][3][0]=1;
    y=0;
    for(i=1;i<=n;i++){
        add2[i]=add2[i-1];
        if(s[i]=='A' || s[i]=='N') x=0;
        if(s[i]=='C') x=1;
        if(s[i]=='G') x=2;
        if(s[i]=='T') x=3;
        if(x<y)
            add2[i]++;
        y=x;
    }
    for(i=n;i>0;i--){
        if(s[i]!='N'){
            if(s[i]=='A') x=0;
            if(s[i]=='C') x=1;
            if(s[i]=='G') x=2;
            if(s[i]=='T') x=3;
            for(a=0;a<4;a++)
            for(b=0;b<=k;b++){
                dp[i][x][b+bool(x>a)]+=dp[i+1][a][b];
            }
        }
        else{
            for(x=0;x<4;x++)
            for(a=0;a<4;a++)
            for(b=0;b<=k;b++){
                dp[i][x][b+bool(x>a)]+=dp[i+1][a][b];
            }
        }
        add=0;
        for(a=0;a<4;a++)
            for(b=0;b<=k-add2[i-1]-bool(cc[a]<s[i-1]);b++)
                add+=dp[i][a][b];
        if(add>=r){
            x=i;
            break;
        }
        x=1;
    }
    for(i=1;i<x;i++){
        if(s[i]=='N')
            s[i]='A';
        if(s[i]<s[i-1])
            k--;
    }

    for(i=x;i<=n;i++){
        if(s[i]=='N'){
            if(s[i-1]=='A') x=0;
            if(s[i-1]=='C') x=1;
            if(s[i-1]=='G') x=2;
            if(s[i-1]=='T') x=3;
            pre=add=0;
            for(a=0;a<4;a++){
                for(b=0;b<=k-bool(a<x);b++)
                    add+=dp[i][a][b];
                if(add>=r){
                    r-=pre;
                    s[i]=cc[a];
                    if(a<x) k--;
                    break;
                }
                pre=add;
            }
        }
        else if(s[i]<s[i-1]) k--;
    }
    puts(&s[1]);
}