BZOJ-1799

题目地址:点此传送

同步博客 https://cn.shcoc.ooo/2018/09/05/BZOJ-1799/#more

题目

Problem Description

input

Output

Sample Input

Sample Output

HINT

题意

看题(略)

思路

数位dp,我感觉很暴力,但是自己不会….
dp[pos][sum][val],其中pos代表第几位,sum是剩下位数需要凑够的数,val是现在模mod后剩下的值,为什么说暴力呢? 这道题就是暴力枚举所以可能出现的位数和,也就是mod,每次换一个mod就得清一次dp(没办法dp没办法再开mod大了),所以我感觉还是有点暴力的……

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e4 + 10;
ll dp[20][200][200];
ll d[20];
ll dfs(int pos,int sum,int val,int mod,int limit){if(sum-pos*9-9>0) return 0;if(pos<0) return sum==0&&val==0;if(sum<0) return 0;if(!limit&&dp[pos][sum][val]!=-1) return dp[pos][sum][val];ll ans=0;ll end=limit?d[pos]:9;for(int i=0;i<=end;i++){if(sum-i>=0){ans+=dfs(pos-1,sum-i,(val*10+i)%mod,mod,limit&(i==end));}}if(!limit)dp[pos][sum][val]=ans;return ans;}
ll solve(ll x){ll cnt=0;ll ans=0;while(x){d[cnt++]=x%10;x/=10;}for(int i=1;i<=cnt*9;i++){memset(dp,-1,sizeof(dp));ans+=dfs(cnt-1,i,0,i,1);}return ans;}
int main()
{ll a,b;scanf("%lld%lld",&a,&b);printf("%lld\n",solve(b)-solve(a-1));return 0;
}