BZOJ 5544: [PA2019]A + B

5544: [PA2019]A + B

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 16 Solved: 13
[Submit][Status][Discuss]

Description

在列竖式计算两个十进制数的和的时候，人们可能会错算成这样：

在图里的左边，248+208被错算成了4416。

给定正整数n，问有多少对非负整数a,b满足a+b会被错算成n。请注意a可以等于b，且a=1,b=2和a=2,b=1是两种不同的方案。

Input

第一行包含一个正整数n(1<=n<10^18)。

Output

输出一个整数，即满足条件的a,b的数量。

Sample Input

112

Sample Output

HINT

Source

鸣谢Claris上传

[Submit][Status][Discuss]

老年人好久没来BZOJ做题了……

数位DP，F[i]表示前i位方案数，转移有两种——

1. 第i位由一对数字加出

2. 第i位和第i-1位一起由一对数字加出

 1 #include <iostream>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 typedef long long Int;
 7 
 8 int main() {
 9     Int n;
10     cin >> n;
11     int a[20], c = 0;
12     for (; n; n /= 10)
13         a[++c] = n % 10;
14     reverse(a + 1, a + c + 1);
15     Int f[20] = {};
16     f[0] = 1;
17     for (int i = 1; i <= c; ++i) {
18         f[i] += f[i - 1] * (a[i] + 1);
19         if (i >= 2 && a[i - 1] == 1)
20             f[i] += f[i - 2] * (9 - a[i]);
21         // cout << i << ": " << f[i] << endl;
22     }
23     cout << f[c] << endl;
24     return 0;
25 }

BZOJ 5544