bzoj 1799: [Ahoi2009]self 类似的分布解读

【原标题】

1799: [Ahoi2009]self 同类分布

Time Limit: 50 Sec Memory Limit: 64 MB

Submit: 554 Solved: 194

[][]

Description

给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

Input

Output

Sample Input

10 19

Sample Output

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;

}

162