cf55dBeautiful numbers数位dp
浏览数：29 /
时间：2015年06月12日
想到 最小公倍数 其余的就好搞了 ，可是没想到
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> #include<math.h> using namespace std; typedef long long LL; const int mod=2520; LL dp[20][2520][1<<8]; int up[20]; LL dfs(int now,int pre,int gaojici,int flag) { if(now<=0){ for(int i=0;i<=7;i++) if((gaojici&(1<<i))&&pre%(i+2)) return 0; return 1; } if(!flag&&~dp[now][pre][gaojici]) return dp[now][pre][gaojici]; int limit = flag? up[now] : 9;LL ret=0 ; for(int i = 0;i<=limit;i++){ if(i>=2) ret+=dfs(now-1,(pre*10+i)%mod, gaojici|(1<<(i-2)) ,flag&&i==limit); else ret+=dfs(now-1,(pre*10+i)%mod, gaojici,flag&&i==limit); } return flag? ret: dp[now][pre][gaojici]= ret; } LL solve(LL x) { int len =0 ; while(x){ up[++len] = x%10; x/=10; } return dfs(len ,0, 0 , 1)-1; } int main() { int Icase;LL a,b; scanf("%d",&Icase); memset(dp,-1,sizeof(dp)); for(int i = 1;i<=Icase;i++){ scanf("%I64d%I64d",&a,&b); printf("%I64d\n",solve(b) - solve(a-1)); } return 0; }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
