洛谷傳送門

文章目錄

• 題目描述
• 解析
• 代碼

題目描述

給出兩個數(shù)a,b求出[a,b]中各位數(shù)字之和能整除原數(shù)的數(shù)的個數(shù)。
1<=a<=b<=10¹⁸

解析

容易想到數(shù)位dp
但本題的難點是如果只記錄數(shù)位和sum與取模的結(jié)果res，因為取模的除數(shù)發(fā)生改變，難以轉(zhuǎn)移
如何解決？
剛才也提到，本題的難點在于模數(shù)發(fā)生改變，所以我們就嘗試強制使取模的數(shù)不變
我們發(fā)現(xiàn)，因為a、b范圍有限，所以這個數(shù)位和的范圍也是很有限的
因此可以枚舉數(shù)位和分別求解再累加答案
問題得到解決

代碼

#include<bits/stdc++.h> #define ll long long using namespace std; const int M = 3000500; const int N = 200; //const int mod=1e9+7; int n; ll dp[20][N][N];//dp[pos][mod][sum][res] ll a[20]; ll l,r; int Mod=190; ll mi[22]; ll find(int pos,int mod,int sum,int res,int lim){ // for(int i=pos;i<n;i++)printf(" "); // printf("pos=%d mod=%d sum=%d res=%d lim=%d mx=%d\n",pos,mod,sum,res,lim,lim?a[pos]:9);if(pos==0) return sum==mod&&res==0;if(sum>mod) return 0;if(!lim&&dp[pos][sum][res]!=-1) return dp[pos][sum][res];ll ans=0;int mx= lim?a[pos]:9;for(int i=0;i<=mx;i++){ll res1=(ll)((ll)mi[pos-1]*i+res)%mod; // for(int j=pos;j<n;j++)printf(" "); // printf(" i=%d res1=%lld\n",i,res1);ans+=find(pos-1,mod,sum+i,res1,lim&&i==mx);}if(!lim) dp[pos][sum][res]=ans; // for(int i=pos;i<n;i++)printf(" "); // printf("return %d\n",ans);return ans; } ll solve(ll x){n=0;while(x){a[++n]=x%10;x/=10;}ll tot=0;for(int i=1;i<=Mod;i++){memset(dp,-1,sizeof(dp));tot+=find(n,i,0,0,1);}return tot; } int main() {mi[0]=1;for(int i=1;i<=20;i++) mi[i]=mi[i-1]*10;scanf("%lld%lld",&l,&r);printf("%lld\n",solve(r)-solve(l-1)); // int now,pre; // for(int i=1;i<=100;i++){ // now=solve(i); // if(now==pre+1) printf("i=%d ans=%d\n",i,solve(i)); // pre=now; // }return 0; } /* 1100 */

總結(jié)

以上是生活随笔為你收集整理的P4127 [AHOI2009]同类分布（数位dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。