#**HƯỚNG DẪN:**<br>
- Do tính chất cộng sai (từng chữ số) của $a$ và $b,$ các giá trị cộng lại không liên quan đến nhau(không có nhớ đơn vị như cộng bình thường)<br>
- Xét $dp[i]$ là số cách tạo số $n$ từ chữ số thứ $1$ tới $i.$<br>
Ta có $2$ cách:<br>
$+$ Cặp chữ số cuối của $a,b$ khi đó cộng bằng $n[i]$ (ghép vào $a,b$ của $dp[i-1]$)<br>
$+$ Cặp chữ số cuối của $a,b$ khi đó cộng bằng $2$ chữ số cuối của $n$.(ghép vào $a,b$ của $dp[i-2]$)<br>
- Xét $n=\overline{...abcd},(x,y);(z,t)$ là $2$ cặp nào đó cộng sai bằng $\overline{...ab}$ <br>
$+$ Trường hợp $1:$<br>
Thêm $a1,b1$ sao cho $a1+b1=\overline{cd}$.<br>
$+$ Trường hợp $2:$<br>
Thêm $a2,b2,a3,b3$ sao cho $a2+b2=c;a3+b3=d.$<br>
Giả sử cặp $\overline{xa_1},\overline{yb_1}$ và $\overline{za_2a_3},\overline{ta_2b_3}$ bị trùng.<br>
$\Rightarrow a_1=a_3,b_1=b_3$ mà như thế thì $a_3+b_3=d=a_1+b_1 = \overline{cd}$.<br>
$\Rightarrow c=0.$ Mà không có $a1+b1$ nào tổng bằng $\overline{0d}.\rightarrow$ Khi đó sẽ không tạo được tổng bằng $2$ chữ số cuối của $n$<br>
Do đó cứ mỗi bộ khác nhau cộng sai thành $\overline{cd}$ hoặc $a2+b2=c;a3+b3=d.$ thì ghép với số thỏa mãn $dp[i-2]$ sẽ tạo $1$ cặp mới.<br>
- Gọi $S(i)$ là số bộ chữ số cộng thành $i$ chữ số cuối của $n.$<br>
$\rightarrow dp[i]=dp[i-2]\*S(2)+ dp[i-1]\*S(1)$ (chú ý $S(2)$ mà có số $0$ ở đầu thì không lấy hoặc đặt bằng $0$)<br>
##**CODE MẪU:**<br>
```cpp
#include<iostream>
#include<string>
using namespace std;
string n;
long long l,dp[20];
int slcap(int m)
{
if(m>18||m<10) return 0;
return (18-m+1);//9-(m-9)+1
}
int main()
{
cin>>n;
n="1"+n;
dp[1]=n[1]-'0'+1;
dp[0]=1;//co 1 cach lm la 0 0.
l=n.size();
for(int i=2;i<l;i++)
{
dp[i]=dp[i-2]*slcap(stoi(n.substr(i-1,2)))+dp[i-1]*(n[i]-'0'+1);
}
cout<<dp[l-1];
}
```
sharinganvanhoadong
Created at
1 likes