几乎是copy的P4999为啥只有40pts
查看原帖
几乎是copy的P4999为啥只有40pts
558324
AutiFancers楼主2023/12/18 19:25

rt

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

const int mod=1e9+7;
const int N=1000100;

int num[N];
ll f[200][200];

ll dfs(int len,int sum,bool limit) {
	ll res=0;
	if(!len) return sum;
	if(!limit && f[len][sum]>=0) return f[len][sum];
	int up=(limit ? num[len] : 9);
	for(int i=0;i<=up;i++)
		res=(res+dfs(len-1,sum+i,limit && (i==up)))%mod;
	if(!limit) f[len][sum]=res;
	return res;
}

ll solve(ll x) {
	int len=0;
	while(x) {
		num[++len]=x%10;
		x/=10;
	}
	return dfs(len,0,1)%mod;
}

int main() {
	memset(f,-1,sizeof f);
	ll R;
	cin>>R;
	cout<<solve(R)<<'\n';	 
	return 0;
}

2023/12/18 19:25
加载中...