洛谷P2602 [ZJOI2010]数字计数(数位dp)

水深无声 2023-08-17 17:21 83阅读 0赞

# 数字计数 #

[题目传送门][Link 1]

## 解题思路 ##

用\\(dp\[i\]\[j\]\[k\]\\)来表示长度为\\(i\\)且以\\(j\\)为开头的数里\\(k\\)出现的次数。

则转移方程式为：\\(dp\[i\]\[j\]\[k\] += \\sum\_\{t=0\}^\{9\} dp\[i - 1\]\[t\]\[k\]\\)，即在每个数前面放一个\\(j\\)，但是对于放在前面的这个\\(j\\)我们还没有计算进去，所以有：\\(dp\[i\]\[j\]\[j\] += 10^\{i-1\}\\)。注意此时计算的是有前导0的。

接下来见代码(其实是不知道怎么描述)。

## 代码如下 ##

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; inline ll fpow(ll x, ll p){ ll ans = 1; for(; p; p >>= 1, x = 1LL * x * x)if(p & 1)ans = 1LL * x * ans; return ans; } ll dp[20][15][15]; void work(ll x, ll ans[]) { ll num[15]; ll t = x; int cnt = 0; while(t){ //把每一位拆出来 num[++cnt] = t % 10; t /= 10; } for(int i = 1; i < cnt; i ++) //小于cnt的位数全加上 for(int j = 1; j <= 9; j ++) for(int k = 0; k <= 9; k ++) ans[k] += dp[i][j][k]; for(int j = 1; j < num[cnt]; j ++) //相同位数小于最高位的全加上 for(int k = 0; k <= 9; k ++) ans[k] += dp[cnt][j][k]; for(int i = cnt - 1; i >= 1; i --){ //遍历每一位 for(int j = 0; j < num[i]; j ++) //小于这位上数字的全加上 for(int k = 0; k <= 9; k ++) ans[k] += dp[i][j][k]; for(int u = cnt; u > i; u --) //前面这几位都相等，出现了相同的次数 ans[num[u]] += num[i] * fpow(10LL, i - 1); } } int main() { ll a, b; scanf("%lld%lld", &a, &b); for(int i = 1; i <= 12; i ++){ for(int j = 0; j <= 9; j ++){ for(int k = 0; k <= 9; k ++) for(int t = 0; t <= 9; t ++) dp[i][j][k] += dp[i - 1][t][k]; dp[i][j][j] += fpow(10LL, i - 1); } } ll ans1[15] = {0}; ll ans2[15] = {0}; work(b + 1, ans1); work(a, ans2); for(int i = 0; i <= 9; i ++) printf("%lld ", ans1[i] - ans2[i]); return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11404057.html

[Link 1]: https://www.luogu.org/problem/P2602