小红的序列乘积2.0

思路 ：

动态规划，令 表示所有考虑前 个元素的子序列种构成的题意中 f 数组最后一个元素的个位是 0...9 的个数， 表示所有前 个元素的子序列中 0...9 的个数。转移显然。

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()

using namespace std ;

const int inf = 0x3f3f3f3f ;
const int LLinf = 0x3f3f3f3f3f3f3f3f ;
const int mod = 1e9 + 7 ;
const int N = 1e5 + 10 ;

int f[N][10] , d[N][10] , n , a[N] ;

void solve()
{
	cin >> n ;
	for(int i = 1 ; i <= n ; ++ i)
	{
		cin >> a[i] ;
		a[i] %= 10 ;
	}
	for(int i = 1 ; i <= n ; ++ i)
	{
		for(int j = 0 ; j <= 9 ; ++ j)
		{
			d[i][j] = d[i - 1][j] * 2 % mod ;
			f[i][j] = f[i - 1][j] ;
		}
		f[i][a[i]] ++ ; 
		d[i][a[i]] ++ ;
		for(int j = 0 ; j <= 9 ; ++ j)
		{
			int t = (j * a[i]) % 10 ;
			f[i][t] = (f[i][t] + f[i - 1][j]) % mod ;
			d[i][t] = (d[i][t] + f[i - 1][j]) % mod ;
		}
	}
	cout << d[n][6] << '\n' ;
}

signed main()
{
	cin.tie(nullptr)->ios::sync_with_stdio(false) ;

	int t = 1 ;
	// cin >> t ;

	for(int i = 1 ; i <= t ; i++)
	{
		// cout << "case #" << i << " : " << '\n' ;
		solve() ; 
	}
	return 0 ; 
}