E题

容易想到，只考虑前i个数的序列乘积的个位只有10种状态：个位为0~9

定义f[i][j]:前i个数中，序列乘积的个位为j的方案数

贡献：前i个数中，以a[i]结尾的序列且乘积个位为6能提供的贡献

这里与题意序列贡献有所不同，因为我们根据f[i][j]定义已知序列在前面的方案总数，我们只考虑当前序列作为序列的前缀还会在后面还会出现多少次，出现多少次就贡献了多少答案

结论：以a[i]结尾的序列作为序列的前缀还能在后面出现的次数为2^(n-i)（后面每个数有可选可不选两种抉择）

用样例一解释

3

4 4 6

序列[4,4]贡献答案 2（446 和 44_）（f[1][4]×a[2]×2^(3-2)==2）

序列[6]贡献答案 1 （6）（f[2][1]*a[3]==1）

序列[4,4,6]贡献答案 1 （446）（f[2][6]*a[3]==1）

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod=1e9+7;
int n,ans,a[100005],f[100005][10];

int quick_pow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return res;
}

void solved()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    //f[i][j]:前i个数中，序列乘积的个位为j的方案数
    f[0][1]=1;//初值
    for(int i=1;i<=n;i++)
        for(int j=0;j<=9;j++)//状态转移方程
        {
            f[i][j*a[i]%10]=(f[i][j*a[i]%10]+f[i-1][j])%mod;//以a[i]结尾的序列
            f[i][j]=(f[i][j]+f[i-1][j])%mod;//非a[i]结尾的序列
        }
        
    for(int i=1;i<=n;i++)
        ans=(ans+(f[i][6]-f[i-1][6]+mod)%mod*quick_pow(2,n-i)%mod)%mod;//以a[i]结尾的序列乘积贡献答案
    cout<<ans;
}

signed main()
{
    solved();
    return 0;
}