题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1021

题解：简单的数位dp由于总共就只有16个存储一下状态就行了。

#include <iostream>#include <cstring>#include <cstdio>#include <cmath>using namespace std;typedef long long ll;ll dp[1 << 17][21] , po[20][20];int base , k , num[20];char s[20];ll dfs(int len , int stat , int mod , int Max) {    if(len == 0) {        if(mod % k == 0) return 1;        return 0;    }    if(dp[stat][mod] != -1) return dp[stat][mod];    ll sum = 0;    for(int i = 0 ; i < Max ; i++) {        if((1 << i) & stat) continue;        else {            sum += dfs(len - 1 , stat | (1 << i) , (num[i] + mod * base) % k, Max);        }    }    dp[stat][mod] = sum;    return sum;}int main() {    int t;    scanf("%d" , &t);    int ans = 0;    for(int i = 2 ; i <= 16 ; i++) {        po[i][0] = 1;        for(int j = 1 ; j <= 16 ; j++) {            po[i][j] = po[i][j - 1] * i;        }    }    while(t--) {        scanf("%d%d" , &base , &k);        scanf("%s" , s);        int len = strlen(s);        for(int i = 0 ; i < len ; i++) {            if(s[i] == ‘A‘) num[i] = 10;            else if(s[i] == ‘B‘) num[i] = 11;            else if(s[i] == ‘C‘) num[i] = 12;            else if(s[i] == ‘D‘) num[i] = 13;            else if(s[i] == ‘E‘) num[i] = 14;            else if(s[i] == ‘F‘) num[i] = 15;            else num[i] = s[i] - ‘0‘;        }        for(int i = 0 ; i < (1 << len) ; i++) {            for(int j = 0 ; j <= k ; j++) dp[i][j] = -1;        }        printf("Case %d: %lld\n" , ++ans , dfs(len , 0 , 0 , len));    }    return 0;}

lightoj 1021 - Painful Bases（数位dp+状压）