吉比特4.1笔试第二题
4.1吉比特笔试第二题,状压写的,对拍了一下好像没问题。有问题希望指出(昨晚状压忘记去重了只过了60%)
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; typedef long long ll; ll dp[1 << 16][55]; char s[50]; int main() { ll l, r, n, m, i, j, t; while (scanf("%s %lld", s, &m) != EOF) { n = strlen(s); memset(dp, 0, sizeof(dp)); sort(s, s + n);//对数字进行排序 dp[0][0] = 1; for (i = 0; i < (1LL << n); i++) { for (j = 0; j < n; j++) { if (!(i & (1LL << j))) { if (j == 0 || s[j] != s[j - 1] || (i & (1LL << (j - 1)))) {//保证对于同一数字按序 for (t = 0; t < m; t++) { dp[i ^ (1LL << j)][(t * 10 + (s[j] - '0')) % m] += dp[i][t]; } } } } } printf("%lld\n", dp[(1 << n) - 1][0]); } }