文章
7
粉丝
387
获赞
7
访问
67.5k
主要是注意高精度,这样的话连续出现某一个数的状态计数就要更多
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod = 20123;
int s[105];
//pos num sta
ll dp[105][30][105];
//dfs参数:当前数位,当前状态,是否是开头,是否有最高位的限制,要求出现次数的数字
ll dfs(int pos, int sta, int lead, int limit, int number) {
if(pos == -1) return sta % mod;
if(!limit && !lead && dp[pos][number][sta] != -1)
return dp[pos][number][sta] % mod;
ll ret = 0;
int up = limit ? s[pos] : 9;//无限制则最高可以冲到9
for(int i = 0; i <= up; ++i) {
if(lead == 1 && i == 0)
ret = (ret + dfs(pos - 1, sta, lead, limit && (i == up), number)) % mod;
else
ret = (ret + dfs(pos - 1, sta + (number == i), lead && i == 0, limit && (i == up), number)) % mod;
}
if(!limit && !lead) dp[pos][number][sta] = ret % mod;
return ret % mod;
}
//[1, ...
登录后发布评论
暂无评论,来抢沙发