本文主要是介绍Codeforces Round #235 (Div. 2) / 410D Roman and Numbers (带有整除性质的数位DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/problemset/problem/401/D
解释全部在代码的注释中：
/*78ms,205464KB*/#include<bits/stdc++.h>
using namespace std;
const int mx = 1 << 18;long long dp[mx][100];
///dp[mask][j]表示余数为j时的mask对应的x的个数
///(mask哪一位为1就表示哪一位上已枚举了数字)，
///最终我们输出dp[11...1][0]
bool vis[mx];
int len, m, one[20], bit[20];///dfs参数意义见dp定义
///整个dfs相当于暴力枚举每一位，但是使用了记忆化搜索
///用取模来归并某些枚举(见函数中的状态转移方程)
///入口为dfs(111...1) (n的位数个1)
void dfs(int mask)
{if (vis[mask]) return;int digitused = 0;for (int i = 0; i < len; ++i){if ((mask & one[i]) == 0 || digitused & one[bit[i]]) continue;///该位不在mask中或已经使用该数字(注意后面那个判断不是位是数字!)int mask_child = mask & (~one[i]);///改第i位为0，然后递归dfs(mask_child);for (int j = 0; j < m; ++j)dp[mask][(j * 10 + bit[i]) % m] += dp[mask_child][j]; ///ab%m=((a%m)*10+b)%mdigitused |= one[bit[i]];}vis[mask] = true;
}int main()
{for (int i = 0; i < 20; ++i) one[i] = 1 << i;long long n;scanf("%I64d%d", &n, &m);if (n < 10) puts(n % m ? "0" : "1");else{while (n){bit[len++] = n % 10;n /= 10;}for (int i = 0; i < len; ++i){if (bit[i]) ///不能有前导0dp[one[i]][bit[i] % m] = 1; ///一个数的方案只有一种vis[one[i]] = true; ///vis[100...000]=true}dfs(one[len] - 1); ///dfs(111...1)printf("%I64d\n", dp[one[len] - 1][0]);}return 0;
}
这篇关于Codeforces Round #235 (Div. 2) / 410D Roman and Numbers (带有整除性质的数位DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
