Codeforces Round #387 (Div. 2) 747F(数位DP)

题目大意

给出整数k和t，需要产生一个满足以下要求的第k个十六进制数

即十六进制数每一位上的数出现的次数不超过t

首先我们先这样考虑，如果给你了0~f每个数字可以使用的次数num[i]，如何求长度为L且满足要求的十六进制数有多少个

dp[i][l]表示使用了前i个数字，已经将L的空位填上了l个的数有多少个

转移方程 dp[i][l] = sigma(dp[i-1][l-j]*C[len-l+j[j]) 其中j是枚举填新的数的个数，C是组合数（选出j个空位填上新数）

有了这个dp后，现在的问题就变成了找出第k个数

首先先确定位数，枚举位数，然后就可以找到第k个数的位数是多少

然后对从最高位开始枚举，确定每一位应该是多少

最后就可以得出答案

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long LL;

const int maxl = ;

LL C[maxl][maxl], dp[][maxl];

int num[], t;

LL k;

void prepare()

{

    for(int i = ; i < maxl; i++) C[i][] = ;

    for(int i = ; i < maxl; i++)

        for(int j = ; j <= i; j++)

            C[i][j] = C[i-][j] + C[i-][j-];

}

LL solve(int len)

{

    memset(dp, , sizeof(dp));

    for(int i = ; i <= num[]; i++) dp[][i] = C[len][i];

    for(int i = ; i < ; i++)

        for(int l = ; l <= len; l++)

            for(int j = ; j <= min(num[i], l); j++)

                dp[i][l] += dp[i-][l-j]*C[len-l+j][j];

    return dp[][len];

}

void print(int j)

{

    if(j < ) cout<<j;

    else cout<<(char)(j+'a'-);

}

int main()

{

    prepare();

    cin>>k>>t;

    for(int i = ; i < ; i++) num[i] = t;

    int len = ;

    for(;; len++)

    {

        LL tmp = ;

        if(len == ) tmp = ;

        else

            for(int j = ; j < ; j++)

            {

                num[j]--;

                tmp += solve(len-);

                num[j]++;

            }

        if(k > tmp) k -= tmp;

        else break;

    }

    for(int i = len; i > ; i--)

    {

        if(i == )

        {

            for(int j = ; j < ; j++)

            {

                if(j ==  && len == ) continue;

                if(num[j] != ) k--;

                if(k == ) { print(j); break; }

            }

            break;

        }

        for(int j = ; j < ; j++)

        {

            if(i == len && j == ) continue;

            num[j]--;

            LL tmp = solve(i-);

            if(k > tmp) k -= tmp;

            else

            {

                print(j);

                break;

            }

            num[j]++;

        }

    }

}

巴特西

Codeforces Round #387 (Div. 2) 747F(数位DP)

最新文章

热门文章