2020牛客暑期多校训练营（第六场）H

题目描述

  Roundgod is obsessive about numbers. Let be the sum of the digits of in decimal notation, is a harmony pair if and only if . Roundgod is given , and she wants to count the number of harmony pairs modulo satisfying .

输入描述

  The only line of input contains one integer .

输出描述

  Output one integer indicating the answer.

示例1

输入

100

输出

967

  比较套路的数位 问题。
   的数位长度为 ，同时构造 的第 位（数位自左向右，左边的数位小），采用记忆化搜索的形式。 表示对 的限制，限制 ； 表示对 的限制，限制 。定义 表示 有 位，， 且 时，构造 的方案数。由于 有可能为负数，所以需要加上 的偏移量。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem H
Date: 8/27/2020
Description: Digit Dynamic Programming
*******************************************************************/
#include<iostream>
#include<cstring>
using namespace std;
const int N=102;
const int mod=1000000007;
int f[N][N*22][2][2];
int number[N];
int len;
char str[N];
int dfs(int pos,int difference,bool limit1,bool limit2){
    if(pos==len+1){
        //减去偏移量差值大于0表示可行
        return difference>1000;
    }
    if(~f[pos][difference][limit1][limit2]){
        return f[pos][difference][limit1][limit2];
    }
    int res1=limit1?number[pos]:9;
    int ans=0;
    for(register int i=0;i<=res1;i++){
        //枚举B的数位
        int res2=limit2?i:9;
        for(register int j=0;j<=res2;j++){
            //枚举A的数位
            ans+=dfs(pos-1,difference+j-i,i==res1&&limit1,i==j&&limit2);
            ans%=mod;
        }
    }
    f[pos][difference][limit1][limit2]=ans;
    return f[pos][difference][limit1][limit2];
}
int main(){
    cin>>(str+1);
    len=strlen(str+1);
    //12345
    for(register int i=1;i<=len;i++){
        //按照习惯排列
        number[i]=str[i]-'0';
    }
    memset(f,-1,sizeof(f));
    cout<<dfs(1,1000,1,1)<<endl;
    return 0;
}