牛客contest5671-H

传送门

题目大意

定义S(x)为x数位和，给出N,满足S(A)>S(B),1≤A≤B≤N的A,B组数。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll dp[110][1810][2][2];
char c[910];
int	l;

ll dfs( int x, int y, int u, int v )
{
	ll res = 0, a, b;
	
	if ( x > l ) return y > 900;
	if ( ~dp[x][y][u][v] ) return dp[x][y][u][v];
	if ( u ) a = c[x] - '0';
	else a = 9;
	
	for (int i = 0; i <= a; i++ )
	{
		if ( v )
			b = i;
		else b = 9;
		for (int j = 0; j <= b; j++ )
			(res += dfs( x + 1, y + j - i, (u && i == a), (v && j == b) ) ) %= mod;
	
	}
	
	return dp[x][y][u][v] = res;
}

int main()
{
	memset( dp, -1, sizeof(dp) );
	
	scanf( "%s", c + 1 );
	l = strlen( c + 1 );
	printf( "%lld\n", dfs( 1, 900, 1, 1 ) );
	
	return 0;
}