C++14(g++5.4) 解法, 执行用时: 483ms, 内存消耗: 73836K, 提交时间: 2019-10-12 17:17:10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3000010;
const int mod=1e9+7;
const int inv2=500000004;
const int inv6=166666668;
ll s[maxn],ps1[maxn],ps2[maxn],N,n,q;
inline void Add(ll &x,const ll y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
inline ll f(ll n)
{
    return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
inline ll solve()
{
    ll m=N/n%mod,k=N%n,ans=0,sum=0;
    ans=(m*ps2[n]%mod+f((m-1+mod)%mod)*n%mod*s[n]%mod*s[n]%mod+(m-1+mod)%mod*m%mod*s[n]%mod*ps1[n]%mod)%mod;
    sum=(m*ps1[n]%mod+(m-1+mod)%mod*m%mod*n%mod*inv2%mod*s[n]%mod)%mod;
    if(k){
        Add(ans,(ps2[k]+k*m%mod*m%mod*s[n]%mod*s[n]%mod+2*m%mod*s[n]%mod*ps1[k]%mod)%mod);
        Add(sum,(ps1[k]+k*m%mod*s[n]%mod)%mod);
    }
    ans=(N+1)%mod*ans%mod;
    Add(ans,(mod-sum*sum%mod)%mod);
    return ans;
}
inline ll read()
{
    char ch=getchar();
    if(ch==EOF) return 0;
    ll ans=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
    return ans;
}
int main()
{
    #ifdef local
    freopen("a.in","r",stdin);
    #endif // local
    n=read(),q=read();
    for(int i=1;i<=n;++i){
        Add(s[i]=s[i-1],read());
        Add(ps1[i]=ps1[i-1],s[i]);
        Add(ps2[i]=ps2[i-1],s[i]*s[i]%mod);
    }
    while(q--){
        N=read();
        printf("%lld\n",solve());
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1282ms, 内存消耗: 38520K, 提交时间: 2019-10-11 20:15:52

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P 1000000007
#define MAXN 3000005
int n,q,s,i,t,a[MAXN],x[MAXN],y[MAXN],ans;
ll m,m1,m2;
int main()
{
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        a[i]+=a[i-1];
        if(a[i]>=P)a[i]-=P;
    }
    t=a[n];
    for(i=1;i<n;i++)
    {
        x[i]=x[i-1]+a[i];
        if(x[i]>=P)x[i]-=P;
        y[i]=(y[i-1]+(ll)a[i]*a[i])%P;
    }
    while(q--)
    {
        scanf("%lld",&m);
        s=m%n;
        m2=(m+1)%P;
        m=m/n%P;
        m1=m-1;
        if(m1<0)m1+=P;
        ans=((m+1)*y[s]+t*m%P*(m+1)%P*x[s]+(ll)t*t%P*m%P*(m+1)%P*(2*m+1)%P*(P+1)/6%P*(s+1)+(m1+1)*(y[n-1]-y[s]+P)+t*m1%P*(m1+1)%P*(x[n-1]-x[s]+P)+(ll)t*t%P*m1%P*(m1+1)%P*(2*m1+1)%P*(P+1)/6%P*(n-s-1))%P*m2%P;
        i=((m+1)*x[s]+t*m%P*(m+1)%P*(P+1>>1)%P*(s+1)+(m1+1)*(x[n-1]-x[s])+t*m1%P*(m1+1)%P*(P+1>>1)%P*(n-s-1))%P;
        ans=(ans+(ll)i*(P-i))%P;
        cout<<ans<<endl;
    }
    return 0;
}