首页 > 代码库 > Codeforces 55 D. Beautiful numbers
Codeforces 55 D. Beautiful numbers
题目链接：http://codeforces.com/problemset/problem/55/D
很裸的数位$DP$但是要考虑一下如何设计状态保证复杂度且不会爆掉空间...
提供一种很暴力的状态表示
${f[len][zt][res]}$表示从高位往地位确定到了第$len$位，是否选取了${2..9}$这些数字状压为$zt$(因为${0,1}$不影响判定)，数字模$2520$的值为$res$的数字有多少个。
${gcd(2,3,4,5,6,7,8,9)=2520}$
然后记忆化一下就可以了，
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg int11 #define SIZE (1<<8)12 #define LL long long 13 #define md 252014 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);15 llg n,m,c[100],T;16 llg p[8]={2,3,4,5,6,7,8,9};17 LL f[20][SIZE+1][2520];18 19 inline llg getint()20 {21 llg w=0,q=0; char c=getchar();22 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 23 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;24 }25 26 LL dfs(llg len,llg zt,llg res,bool flag)27 {28 if (!len)29 {30 for (llg i=0;i<8;i++)31 if (zt&(1<<i) && res%(i+2)!=0)32 return 0;33 return 1;34 }35 if (!flag && f[len][zt][res]!=-1) return f[len][zt][res];36 llg up;37 LL sum=0;38 if (flag) up=c[len];else up=9;39 for (llg i=0;i<=up;i++)40 {41 llg nezt,neres;42 if (i>1) nezt=zt|(1<<(i-2)); else nezt=zt;43 neres=(res*10+i)%md;44 sum+=dfs(len-1,nezt,neres,(flag && i==up));45 }46 if (!flag) f[len][zt][res]=sum;47 return sum;48 }49 50 LL dp(LL x)51 {52 if (x==0) return 1;53 llg wei=0;54 while (x)55 {56 c[++wei]=x%10;57 x/=10;58 }59 return dfs(wei,0,0,1);60 }61 62 int main()63 {64 //yyj("number");65 cin>>T;66 LL a,b;67 memset(f,-1,sizeof(f));68 while (T--) 69 {70 scanf("%lld%lld",&a,&b);71 printf("%lld\n",dp(b)-dp(a-1));72 }73 return 0;74 }
Codeforces 55 D. Beautiful numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。