题解 | #E-小红的序列乘积2.0 (前缀和优化DP)#

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;

#define ll long long
#define all(x) (x).begin(),(x).end()
const int N=1e5+10;
const int mod=1e9+7;

ll n,a[N],cnt[N];
// 1*6 2*3 2*8 4*4 4*9 6*6
// 以i结尾 相乘是j的子序列的数量 DP
// 以i结尾 相乘是j的子序列的权值 g 
ll dp[N][10],g[N][10],res[N][10]; 
void solve(){
	ll ans=0;
	dp[1][a[1]]=1; 
	if(a[1]==6) g[1][a[1]]=1,res[1][a[1]]=1;
	
	// 先暴力 再优化 
	for(int i=2;i<=n;i++){
		// 自己单独作为一个子序列
		dp[i][a[i]]=1; 
		if(a[i]==6) g[i][a[i]]=1,res[i][a[i]]=1;
		
//		//  与前面的子序列拼接 
//		for(int j=1;j<i;j++){
//			for(int k=0;k<=9;k++){
//				int x=k*a[i]%10;
//				dp[i][x]+=dp[j][k]; 
//				if(x!=6) g[i][x]+=g[j][k];
//				else{
//					g[i][x]+=g[j][k]+dp[j][k];
//				}
//				dp[i][x]%=mod,g[i][x]%=mod;
//			}
//		}
		// 前缀和优化 
		for(int k=0;k<=9;k++){
			int x=k*a[i]%10;
			dp[i][x]+=dp[i-1][k];
			g[i][x]+=g[i-1][k],res[i][x]=g[i][x];
			if(x==6) g[i][x]+=dp[i-1][k],res[i][x]=g[i][x];
			dp[i][x]%=mod,g[i][x]%=mod,res[i][x]%=mod;
		}
		for(int k=0;k<=9;k++) dp[i][k]+=dp[i-1][k],dp[i][k]%=mod;
		for(int k=0;k<=9;k++) g[i][k]+=g[i-1][k],g[i][k]%=mod;
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=9;j++) ans=(ans+res[i][j])%mod;
	cout<<ans; 
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],a[i]%=10,cnt[a[i]]++;
	solve();
	return 0;
}