题解 | #小红删数字（线性dp）#

讲讲思路

最近做了各种dp，DAG上dp，分层dp，换根dp，AC自动机上dp......所以看到这道题第一眼就发现这是一个无后效性的线性递推。

为什么是线性？

因为某一轮各结果的方案数完全取决于上一轮各结果的方案数。

不难发现，本题虽然 比较大，但模数特别小，所以可以 实现的状态转移。

如何构造状态转移？

dp的要点之一是构造恰当的状态函数(数组)。在本题中， 表示：

• 当前正在处理第 与 位，且第 位上模 后结果为 的方案数。

初始状态

初始状态只有一个数，用状态函数表示就是

其余位的结果都是 。

转移方程

明确状态之后就清晰很多了，转移方程如下：

可以理解为当前 对这两项有贡献，并且这个贡献是可算的，对吧～

然后一层一层往前递推就好。

贴贴代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n, t, a[N], cnt[N][10];
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>t; 
        if(n>1) a[i]=t%10;
        else a[i]=t;//很无聊的特判诶
    }
    cnt[n][a[n]]++;//初始状态，显然只有一种可能
    for(int i=n; i>1; i--) {
        for(int j=0; j<10; j++) {
            cnt[i-1][(a[i-1]+j)%10]=(cnt[i-1][(a[i-1]+j)%10]+cnt[i][j])%1000000007;
            cnt[i-1][(a[i-1]*j)%10]=(cnt[i-1][(a[i-1]*j)%10]+cnt[i][j])%1000000007;
        }
    }
    for(int i=0; i<10; i++) {
        cout<<cnt[1][i]<<' ';
    }
}