题解 P5965 【[PA2019]A+B】

· · 题解

强烈建议修改题面

这道题我看题目描述卡了好久，题目中描述的是：

给定正整数 n，问有多少对非负整数 a,b 满足 a+b 会被错算成 n。

但是实际上题目可以理解为规定了一种不同于普通竖式加法的新运算，对于这种运算：

我们将所有的原位置按每一位按位置进行加法，

所以每一位的范围是 0 - 18

换句话说，这个题目说错算是不对的，很有可能符合正常竖式计算的也会符合这种新运算。

举个例子，66+22 = 88，这就是即符合竖式计算也符合该新运算的，也会被计算成一种情况。

理解了这个就好办了。。

其他的别人的讲解已经很清楚了，我们考虑f[i] 为前 ｉ 个数字的方案。

那就好办了。。 ## 代码 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; char s[20]; ll a[20]; ll len; ll f[20]; int main() { scanf("%s",s+1); ll len = strlen(s+1); for(int i = 1;i <= len;i++) { a[i] = s[i] - '0'; } f[0] = 1; f[1] = a[1]+1; for(int i = 2;i <= len;i++) { f[i] = f[i-1]*(a[i]+1); if(a[i-1] == 1) f[i] += f[i-2]*(9-a[i]); } printf("%lld\n",f[len]); return 0; } ```