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

Description

求 (1 le A le B le n) 中满足 (S(A)>S(B)) 的 ((A,B)) 个数，(S) 是数码和。

Solution

考虑数位 dp，设 f(i,d,x,y) 表示已经确定了最高的 i 位，两数字的数码和的差为 d，A 与 N 的大小关系为 x，A 与 B 的大小关系为 y，转移时暴力枚举后一位的数字即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int N = 105;
const int M = 2005;
const int O = 1000;
const int mod = 1e9+7;

// 确定到第 pos 位，两数字的数码和的差为 delta
// B 与 N 的大小关系为 x，A 与 B 的大小关系为 y
int f[N][M][2][2],a[N],n;
string s;

int dfs(int pos,int delta,int x,int y)
{
    if(pos==0) return delta>O;
    if(~f[pos][delta][x][y]) return f[pos][delta][x][y];
    int ans=0;
    for(int i=0;i<=(x?a[pos]:9);i++)    // 枚举 B
    {
        for(int j=0;j<=(y?i:9);j++)     // 枚举 A
        {
            ans+=dfs(pos-1,delta+j-i,x&(a[pos]==i),y&(i==j));
        }
    }
    return f[pos][delta][x][y]=ans%mod;
}

signed main()
{
    ios::sync_with_stdio(false);
    memset(f,-1,sizeof f);
    cin>>s;
    n=s.length();
    for(int i=0;i<n;i++) a[n-i]=s[i]-'0';
    cout<<dfs(n,O,1,1)<<endl;
    return 0;
}