BZOJ 1799 [Ahoi2009]self 同类分布

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1799

题意:略。

思路:虽然模数不确定,但注意到模数最多只有9\times 18个,所以我们枚举每个模数进行数位DP,定义状态dp[pos][sum][k]为到第pos位置位置和为sum,对当前枚举的模数取模得到k的满足条件的数字个数,状态转移方程即为dp[pos][sum][k]=\sum dp[pos-1][sum-p][(k-p\times 10^{pos-1})\bmod MOD],记忆化搜索即可。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
template <class T1, class T2>inline void gmax(T1 &a,T2 b){if (b>a) a=b;}
template <class T1, class T2>inline void gmin(T1 &a,T2 b){if (b<a) a=b;}
ll a,b;
ll dp[20][180][180],bin[20];
int digit[20],MOD;
ll dfs(int len,int sum,int k,bool jud){
    if (sum<0) return 0;
    if (!len) return !k && !sum;
    if (!jud && ~dp[len][sum][k]) return dp[len][sum][k];
    int limit=jud?digit[len]:9;
    ll ret=0;
    for (int i=0;i<=limit;i++){
        ret+=dfs(len-1,sum-i,(k-i*bin[len-1]%MOD+MOD)%MOD,jud&&i==limit);
    }
    if (!jud) dp[len][sum][k]=ret;
    return ret;
}
ll get(ll x){
    int len=0;
    while (x){
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,MOD,0,1);
}
int main(){
    read(a),read(b);
    ll ret=0;
    bin[0]=1;
    for (int i=1;i<=20;i++) bin[i]=bin[i-1]*10LL;
    for (MOD=1;MOD<=163;MOD++){
        memset(dp,-1,sizeof(dp));
        ret+=get(b)-get(a-1);
    }
    printf("%lld\n",ret);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注