self 同类分布 HYSBZ - 1799

本文主要是介绍self 同类分布 HYSBZ - 1799，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.lydsy.com/JudgeOnline/problem.php?id=1799

枚举各位数字之和 然后数位DP 将数值对所枚举的数字之和取模

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=20;
const int maxm=200;ll dp[maxn][maxm][maxm];
int pre[maxn];
int bit[maxn];void init(int mod)
{int i;pre[0]=1;for(i=1;i<=19;i++){pre[i]=(10*pre[i-1])%mod;}
}ll dfs(int pos,int sta1,int sta2,int mod,int limit)
{ll res;int up,i,tmp;if(pos==-1){if(sta1==0&&sta2==0) return 1;else return 0;}if(!limit&&dp[pos][sta1][sta2]!=-1) return dp[pos][sta1][sta2];if(limit) up=bit[pos];else up=9;res=0;for(i=0;i<=up;i++){if(sta2-i>=0){tmp=(sta1+i*pre[pos])%mod;res+=dfs(pos-1,tmp,sta2-i,mod,limit&&i==bit[pos]);}}if(!limit) dp[pos][sta1][sta2]=res;return res;
}ll solve(ll val)
{ll res;int n,i;n=0;while(val>0){bit[n++]=val%10;val/=10;}res=0;for(i=1;i<=9*n;i++){memset(dp,-1,sizeof(dp));init(i);res+=dfs(n-1,0,i,i,1);}return res;
}int main()
{ll l,r;scanf("%lld%lld",&l,&r);printf("%lld\n",solve(r)-solve(l-1));return 0;
}//1 999

 

这篇关于self 同类分布 HYSBZ - 1799的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---