lightoj 1021 (数位DP)

题意：给你一个b进制的数，再给你一个十进制数k，你可以重新排列b进制数的每一位得到其他b进制数，问你这些数中有多少可以整除k？

思路：数位dp。

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

long long int dp[1 << 16][20];

int hashDigit(char ch){

    if(ch >= '0' && ch <= '9') return ch-'0';

    return 10 + ch - 'A';

}

int main(){

    int t,b,K,CASE(0);

    char str[20];

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%s",&b,&K,str);

        memset(dp,0,sizeof dp);

        dp[0][0] = 1;

        int len = strlen(str),range = 1 << len;

        for(int i = 0;i < range;i ++){

            for(int j = 0;j < len;j ++){

                if(i & (1 << j)) continue;

                for(int k = 0;k < K;k ++)

                    dp[i|(1 << j)][(k*b + hashDigit(str[j]))%K] += dp[i][k];

            }

        }

        printf("Case %d: %lld\n",++CASE,dp[range-1][0]);

    }

    return 0;

}

巴特西

lightoj 1021 (数位DP)

最新文章

热门文章