BZOJ1799self 同类分布
题意
给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。
【约束条件】1 ≤ a ≤ b ≤ 10^18
题解
1.所有的位数之和<9*18=162
2.所以，dp[i][j][k][m]表示有i位（允许有前导0），数位和为k，模数为m，前i位与模数的模为j的符合条件的数的个数。这样要炸空间，怎么办！！其实这个dp的最后一维可以省去，因为对于不同的m值，dp互不相干。这样还是要超时的，有5亿多。于是就要卡常数，具体见代码里面的枚举的上下界。
代码
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
LL L,R;
LL dp[][][];
int a[],mod;
LL dfs(int d,int ds,int c,bool full){
if (d==)
return (ds==&&c==)?:;
if (!full&&dp[d][ds][c]!=-)
return dp[d][ds][c];
LL ans=;
int tp=min(ds,full?a[d]:);
for (int i=max(,ds-*(d-));i<=tp;i++)
ans+=dfs(d-,ds-i,(c*+i)%mod,full&&i==tp);
if (!full)
return dp[d][ds][c]=ans;
return ans;
}
LL solve(LL n){
if (n==)
return ;
int d=;
while (n>)
a[++d]=n%,n/=;
LL ans=;
for (int i=;i<=d*;i++){
memset(dp,-,sizeof dp);
mod=i;
ans+=dfs(d,i,,);
}
return ans;
}
int main(){
freopen("self.in","r",stdin);
freopen("self.out","w",stdout);
scanf("%lld%lld",&L,&R);
printf("%lld",solve(R)-solve(L-));
fclose(stdin);fclose(stdout);
return ;
}