首页 > 代码库 > bzoj 1799: [Ahoi2009]self 同类分布 题解
bzoj 1799: [Ahoi2009]self 同类分布 题解
【原题】
1799: [Ahoi2009]self 同类分布
Time Limit: 50 Sec Memory Limit: 64 MBSubmit: 554 Solved: 194
[Submit][Status]
Description
给出a,b,求出[a,b]中各位数字之和能整除原数的数的个数。
Input
Output
Sample Input
10 19
Sample Output
3
HINT
【约束条件】1 ≤ a ≤ b ≤ 10^18
Source
Day1
【分析】肯定是数位DP。不过望着50s的时限我大笑:这么宽?
于是匆匆整理了思路。
最多时18个9,也就是和最大值是162。首先我要先枚举和P。状态怎么表示呢?哦,f[i][j][k][sum]表示到第i位,首位是j,目前总和是sum,且目前模P的答案是K。推起来简单,就是统计的时候还是得一位一位的来,略麻烦。
但是写完后,我发现样例时过了,可连样例都跑得飞慢!!!
计算效率:162*18*10*162*162。咦?怎么算都是超时的!!!
【代码1】
#include<cstdio> #include<cstring> #include<cmath> #define D 19 #define S 163 #define G 10 using namespace std; typedef long long LL; LL f[D][G][S][S],A,B,M[D][S]; LL PRE() { int a[D]={0},cnta=0;LL ansa=0; for (;A;A/=10ll) a[++cnta]=A%10; int b[D]={0},cntb=0;LL ansb=0; for (;B;B/=10ll) b[++cntb]=B%10; for (int P=1;P<=162;P++) { memset(f,0,sizeof(f)); for (int i=0;i<10;i++) f[1][i][i%P][i]=1ll; for (int i=1;i<cntb;i++) for (int j=0;j<=9;j++) for (int k=0;k<P;k++) for (int sum=0;sum<=P;sum++) if (f[i][j][k][sum]) { for (int now=0;now<=9;now++) f[i+1][now][(k+now*M[i][P])%P][sum+now]+=f[i][j][k][sum]; } LL ta=ansa,tb=ansb; int s=0,d=0,now=0; for (int i=cnta;i;i--) { for (int j=(i==1);j<a[i];j++) ansa+=f[i][j][now][P-d]; s=(s+a[i])*10%P;d+=a[i];now=(P-s)*(P!=s); } s=0;d=0;now=0; for (int i=cntb;i;i--) { for (int j=(i==1);j<b[i];j++) ansb+=f[i][j][now][P-d]; s=(s+b[i])*10%P;d+=b[i];now=(P-s)*(P!=s); } } if (!ansa) ansa--; return ansb-ansa; } int main() { scanf("%lld%lld",&A,&B);A--; M[0][1]=0;for (int j=2;j<=162;j++) M[0][j]=1; for (int i=1;i<=18;i++) for (int j=1;j<=162;j++) M[i][j]=M[i-1][j]*10ll%j; printf("%lld",PRE()); return 0; }
于是无节操的去看题解。
有一位P党的大神是按位去枚举sum的,效率很高。
于是就。。。嘿嘿。。。赶紧借鉴一下。
然后发现空间上过不去。。。。
上面内存限制64M(当然BZOJ上超一点点没什么事),我68M!
于是开始压内存,把没用的全删除了——66M!
怎么办?打了一个很小的点(其实也不算是打点,只是把sum=162的这种情况去掉)
65M多!!还是卡不过去!!
气死了,就用数组自然溢出吧!咦?竟然过了!!
【代码】
#include<cstdio> #include<cstring> #include<algorithm> #define D 19 #define S 160 //原来是163 using namespace std; typedef long long LL; LL f1[S-1][S][S-1],f2[S-1][S][S-1];LL A,B; LL PRE(LL A) { int a[D]={0},cnt=0,y,i,j,k,l,z,sum=0;LL ans=0,x=A,mul,now; if (!A) return 0; for (;A;A/=10ll) a[++cnt]=A%10,sum+=a[cnt]; for (i=1;i<=cnt/2;i++) swap(a[i],a[cnt-i+1]); memset(f1,0,sizeof(f1)); for (i=1;i<S;i++) f1[0][i][0]=1ll; if (x%sum==0) ans++;mul=1ll; for (i=0;i<cnt;i++) { x/=10ll;mul*=10ll;now=x*mul;sum-=a[cnt-i]; for (z=0;z<a[cnt-i];z++) { for (j=sum+z+(sum+z==0);j<=sum+z+i*9;j++) y=(now%j)?j-now%j:0,ans+=f1[j-sum-z][j][y]; now+=mul/10; } memcpy(f2,f1,sizeof(f1)); memset(f1,0,sizeof(f1)); for (j=0;j<=i*9;j++) for (k=j;k<S;k++) for (l=0;l<k;l++) for (z=0;z<=9;z++) f1[j+z][k][(l*10+z)%k]+=f2[j][k][l]; } return ans; } int main() { scanf("%lld%lld",&A,&B); if (B>=999999999999999999ll) B=999999999999999998ll,printf("%lld",PRE(B)-PRE(A-1)+1); else printf("%lld",PRE(B)-PRE(A-1)); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。