昨天没做出来,今天请教了学长才会。我觉得这种dp的思想很好,想通了面对这种麻烦题目就有四两拨千斤之奇效。
首先构建一个dp[1<<18][100]的数组,这个数组是有含义的。下面解释下:
第一维:对于一个数字如123123453,对于每位可以用0和1表示它用过与否,这样就可以表现成二进制,对于题目的18位长度构建相应大小的数组。
第二维:表示这种状态下的余数。
用cnt[i]记录i出现次数。
为了方便且相同数字不重复,我们这里把每位想成排好序的状态,如 1 1 2 2 3 3 3 4 5 ,用a[i]表示i的起始位置,所以a[i]个到a[i+1]-1个都是i。
接下来就是dp的过程,由于第一位不能为0,特殊处理:
for(int i=1;i<10;i++)
{
if(cnt[i])dp[1<<a[i]][i%m]=1;
}
只看1~9,当前只是一位的情况。
下面再从二进制组成往后推
for(int i=1;i<(1<<l);i++) //这里枚举组成情况
{
for(int j=0;j<m;j++)//枚举余数
{
if(dp[i][j]) //如果这种情况存在
{
for(int k=0;k<=9;k++) //考虑这种情况的下一位的情况,此处枚举下一位数字
{
for(int p=a[k];p<a[k+1];p++) //结合上面解释,这里是枚举用的第几个k
{
if(i&(1<<p))continue; //如果这个k已经在 i 的这种情况中用过,则继续
dp[i+(1<<p)][(j*10+k)%m]+=dp[i][j]; //否则的话就有新的状态产生了。
break;//由于只考虑 i 这个状态下的后一位,所以有了一种可能后跳出考虑另外的数字
}
}
}
}
}
最后的答案是 dp[(1<<l)-1][0] , (1<<l)-1 换成二进制 l 位上每位都是1了,代表所以数都用了 , 后面 0 代表余数为0的情况,这就是答案了。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; long long dp[1<<18][111]; int cnt[11]; int a[11]; string s; int m; int main() { cin>>s>>m; int l=s.length(); memset(cnt,0,sizeof(cnt)); memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); for(int i=0;i<l;i++) { cnt[s[i]-'0']++; } for(int i=1;i<11;i++)a[i]=a[i-1]+cnt[i-1]; for(int i=1;i<10;i++) { if(cnt[i])dp[1<<a[i]][i%m]=1; } for(int i=1;i<(1<<l);i++) { for(int j=0;j<m;j++) { if(dp[i][j]) { for(int k=0;k<=9;k++) { for(int p=a[k];p<a[k+1];p++) { if(i&(1<<p))continue; dp[i+(1<<p)][(j*10+k)%m]+=dp[i][j]; break; } } } } } cout<<dp[(1<<l)-1][0]<<endl; return 0; }