噗嗤——这种一眼就能看出是**倒排动态规划（DP）**的题目，居然还有杂鱼在纠结？逻辑简单到连路边的牛都能秒懂吧？

既然你们这些大脑空空的家伙还在搜索题解，本天才少女翔子就勉为其难地给你们讲讲。好好听着，这可是杂鱼们唯一的救赎机会哦！详情可看【1月20日 牛客每日一题【C++/Python】】

📊 翔子的天才课堂：后缀归并 DP

🧐 核心逻辑：别被“最后两个数”骗了！

题面说每次操作“最后两个数 ”，这意味着什么？这意味着这个数组的合并顺序是从右往左固定的！

想象一下，你有一排数字 。

  1. 第一次操作一定是合并 和 ，变成一个新数。
  2. 第二次操作一定是合并 和刚才那个新数。
  3. ...以此类推。

这不就是个简单的后缀处理吗？如果你连这个合并顺序都看不出来，建议直接把杂鱼❤键盘捐给有需要的人，呵呵❤~

💡 DP 状态定义

我们只需要记录：处理到第 个数字时，后面所有数字合并出的结果为 的方案数分别有多少。

  • 状态：dp[i][j] 表示从第 个数到第 个数，合并后的结果为 的方案数。
  • 转移：当我们把 加入合并时，它会和后面已经合并出的结果 进行加法或乘法：
  • 加法：new_val = (a[i] + j) % 10
  • 乘法：new_val = (a[i] * j) % 10
  • dp[i][new_val] += dp[i+1][j]

这种 的复杂度，简直是闭着眼都能跑过，只有没用的杂鱼才会担心超时吧❤？

💻 毫无难度的 C++ 代码

这里的代码宏定义写得这么多，真是❤杂鱼❤最后的倔强呢~

#include <bits/stdc++.h>
#define il inline
#define double long double
using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128 = __int128_t;

const ll N = 5e5 + 5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
double PI = 3.1415926;

il void solve(){
    int n;
    cin>>n;
    if(n==1){
        ll a;
        cin>>a;
        for(int i=0;i<10;i++){
            cout<<(i==a%10?1:0)<<' ';
        }
        return ;
    }
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=10; // 杂鱼记得取模，不然爆掉就搞笑了
    }
    // 这个DP表大得离谱，不过谁让内存不值钱呢
    vector<vector<ll>>dp(n+5,vector<ll>(10));
    dp[n][a[n]]=1;

    for(int i=n-1;i>=1;i--){
        for(int j=0;j<10;j++){
            // 乘法合并，智商乘法也是0吗？
            ll ed=j*a[i]%10;
            (dp[i][ed]+=dp[i+1][j])%=mod;
            
            // 加法合并，像不像在数自己的失误次数？
            ed=(j+a[i])%10;
            (dp[i][ed]+=dp[i+1][j])%=mod;
        }
    }
    for(int i=0;i<10;i++){
        cout<<dp[1][i]<<" ";
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--){
        solve();
    }
    return 0;
}

🐍 慢悠悠的 Python 代码

Python 的处理速度虽然像杂鱼爬行一样慢，但写起来倒是挺省事的。

import sys

# 这种递归深度设置，杂鱼是不是想把内存撑爆呀？
sys.setrecursionlimit(1145141919)
input = sys.stdin.readline

def read():
    line = sys.stdin.readline()
    if not line: return []
    return list(map(int, line.split()))

mod = 10**9 + 7

def solve():
    n_list = read()
    n = n_list[0]
    
    a = [0] + read()
    if n == 1:
        # 只有一个数的情况，杂鱼一定要看清楚题哦
        for i in range(10):
            print(1 if a[1] % 10 == i else 0, end=' ')
        return
    
    for i in range(n + 1):
        a[i] %= 10

    # 简单的二维数组，杂鱼能学会吗？
    dp = [[0] * 10 for i in range(n + 5)]
    dp[n][a[n]] = 1
    
    for i in range(n - 1, 0, -1):
        for j in range(10):
            if dp[i+1][j] == 0: continue
            
            # 乘法转移
            ed = j * a[i] % 10
            dp[i][ed] = (dp[i][ed] + dp[i + 1][j]) % mod
            
            # 加法转移
            ed = (j + a[i]) % 10
            dp[i][ed] = (dp[i][ed] + dp[i + 1][j]) % mod

    for i in range(10):
        print(dp[1][i], end=' ')

def main():
    t = 1
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

🙄 翔子的最后叮嘱

❤看完了吗？看完了就赶紧拿着这份代码去提交，别再盯着屏幕发呆了！

这种后缀合并的思路，只要稍微带点脑子就能想到。要是下次还问这种水平的题，翔子真的会忍不住笑出声来的，呵呵~ 明白了吗？杂鱼们❤❤！