数位动态规划

题面什么都没有说清，出题人麻麻趋势。

题意：定义新运算 $a \oplus b$ 为按位进行的加法，但是当某一位加法结果大于 $9$ 时可以选择不进位并直接向结果添加一个 $1$ 作为新的一位。

$9876 \oplus 6543 = 16419$，全部进位（加法）。

$9876 \oplus 6543 = 1513119$，全部不进位。

设计 $dp_i$ 为通过 $x \oplus y$（$x,y$ 为任意非负整数）得到给定数字从左到右前 $i$ 位组成的数字的方案数。

对于不进位的情况，首先取得得到前 $i-1$ 位的方案数，然后独立计算得到第 $i$ 位的方案数。枚举第 $i$ 位是哪个数然后计算。

$$0=(0,0)$$

$$1=(1,0),(0,1)$$

$$2=(2,0),(1,1),(0,2)$$

$$3=(3,0),(2,1),(1,2),(0,3)$$

$$4=(4,0),(3,1),(2,2),(1,3),(0,4)$$

$$5=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)$$

$$6=(6,0),(5,1),(4,2),(3,3),(2,4),(1,5),(0,6)$$

$$7=(7,0),(6,1),(5,2),(4,3),(3,4),(2,5),(1,6),(0,7)$$

$$8=(8,0),(7,1),(6,2),(5,3),(4,4),(3,5),(2,6),(1,7),(0,8)$$

$$9=(9,0),(8,1),(7,2),(6,3),(5,4),(4,5),(3,6),(2,7),(1,8),(0,9)$$

使用 $a_i$ 表示给定数字从左到右第 $i$ 位，这一部分状态转移方程为 $dp_i=dp_{i-1} \times (a_i+1)$。

对于进位的情况，首先第 $i-1$ 位必定是 $1$，然后枚举第 $i$ 位的数计算，注意两个加数都不能大于 $9$。

$$10=(9,1),(8,2),(7,3),(6,4),(5,5),(4,6),(3,7),(2,8),(1,9)$$

$$11=(9,2),(8,3),(7,4),(6,5),(5,6),(4,7),(3,8),(2,9)$$

$$12=(9,3),(8,4),(7,5),(6,6),(5,7),(4,8),(3,9)$$

$$13=(9,4),(8,5),(7,6),(6,7),(5,8),(4,9)$$

$$14=(9,5),(8,6),(7,7),(6,8),(5,9)$$

$$15=(9,6),(8,7),(7,8),(6,9)$$

$$16=(9,7),(8,8),(7,9)$$

$$17=(9,8),(8,9)$$

$$18=(9,9)$$

这一部分的状态转移方程为 $dp_i=[a_{i-1}=1] \times dp_{i-2} \times (9 - a_i)$。

最终得到状态转移方程如下。

$$dp_i = \begin{cases} dp_{i-1} \times (a_i+1) & a_{i-1} \neq 1 \\ dp_{i-1} \times (a_i+1)+ dp_{i-2} \times (9 - a_i) & a_{i-1} = 1 \end{cases}$$

#include<bits/stdc++.h>
using namespace std;
long long dp[25];
int n,a[25];
string s;
int main(){
    cin>>s,dp[0]=1ll;
    for(auto i:s) a[++n]=i-'0';
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]*(a[i]+1);
        if(i>=2&&a[i-1]==1) dp[i]+=dp[i-2]*(9-a[i]);
    }
    cout<<dp[n]<<'\n';
    return 0;
}