P4127 [AHOI2009]同类分布

题解

好的，敲上数位DP  DFS板子

记录一下填的各位数字之和 sum ，然后记录一下原数 yuan

最后判断一下  yuan%sum==0 不就好啦？？？

突然意识到 dp 数组咋存？？？

dp[pos][sum][yuan]

pos , sum 都可以记录，但是 yuan ？？？ 1e18？？？

我们可以把yuan取模啊！

yuan%mod  ?

取模啥呢？？？如果固定一个取模数字，结果很有可能就不对了，那就枚举吧

看到原式 yuan%sum ?= 0

mod = 1~sum 好啦

yuan%mod = 0 并且 sum=mod 不就相当于 yuan%sum==0 么

所以 dp[pos][sum][yuan%mod]

代码

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

ll a,b;

ll c[],len=;

ll dp[][][];

ll mod;

ll dfs(ll pos,ll sum,ll k,ll yuan,bool limit,bool qdl)

{

    if(pos<=) return sum==mod&&k==;

    if(!limit&&!qdl&&dp[pos][sum][k]!=-) return dp[pos][sum][k];

    ll ans=;

    ll up=limit?c[pos]:;

    for(ll i=;i<=up;i++)

      ans+=dfs(pos-,sum+i,(yuan*+i)%mod,yuan*+i,limit&&(i==up),qdl&&(i==));

    if(!limit&&!qdl) dp[pos][sum][k]=ans;

    return ans;

}

ll fun(ll x)

{

    memset(c,,sizeof(c));len=;

    while(x)

    {

        c[++len]=x%;

        x/=;

    }

    ll ans=;

    for(mod=;mod<=len*;mod++)

    {

        memset(dp,-,sizeof(dp));

        ans+=dfs(len,,,,,);

    }

    return ans;

}

int main()

{

    a=read();b=read();

    printf("%lld\n",fun(b)-fun(a-));

    return ;

}