题意

给出一个长度为n的数组a。区间[L,R]的值为 ∑R?Li=0a[L+i]?a[R?i]
求所有长度为质数的区间的值的总和。

题解

很容易想到，枚举一个数对，然后统计他的答案
比如说，我们枚举了一个数对$(i,j)$
那么他的答案的贡献会有两种情况
1.$i+j<=n+1$
这个的话，能包含他的区间长度是$[j-i+1,j-i+1+2*(i-1)]$
化简一下式子可以的得到$[j-i+1,j+i-1]$
也就是他的答案的贡献是$a[i]*a[j]*(s[i+j-1]-s[j-i])$
$s$表示质数个数的前缀和
然后这个显然可以用FFT处理
然后对于$i+j>n+1$的情况也是同理
这里就不写了
有一个要注意的地方就是，你要保证$(i,j)$合法，也就是要让$(i,j)$同奇偶
在计算的时候，我们不把2当作质数
最后单独算就行
然后取模什么的不用管。。
最后模就行
用double会炸精度，所以要开long double
CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
typedef long double LB;
const LB pi=M_PI;
const LL MOD=1e9+7;
const LL N=100005*10;
struct qq {LB x,y;qq (){}qq (LB _x,LB _y)    {
   x=_x;y=_y;}
};
qq operator + (qq x,qq y)   {
   return qq(x.x+y.x, x.y+y.y);}
qq operator - (qq x,qq y)   {
   return qq(x.x-y.x, x.y-y.y);}
qq operator * (qq x,qq y)   {
   return qq(x.x*y.x-x.y*y.y, x.x*y.y+x.y*y.x);}
LL bin[N];
void fft (qq *a,LL n,LL o)
{for (LL u=0;u<n;u++) bin[u]=(bin[u>>1]>>1)|((u&1)*(n>>1));for (LL u=1;u<n;u++)if (u<bin[u])swap(a[u],a[bin[u]]);for (LL u=1;u<n;u<<=1){qq wn=qq(cos(2*pi/(u<<1)),o*sin(2*pi/(u<<1)));for (LL i=0;i<n;i+=(u<<1)){qq w=qq(1,0);for (LL j=0;j<u;j++){qq t=w*a[u+i+j];a[u+i+j]=a[i+j]-t;a[i+j]=a[i+j]+t;w=w*wn;}}}
}
LL n;
LL f[N];
LL pri[N],tot;
bool ok[N];
void prepare ()
{memset(ok,true,sizeof(ok));ok[1]=false;for (LL u=2;u<=n;u++){if (ok[u])  pri[++tot]=u;for (LL i=1;i<=tot;i++){LL j=pri[i];if (j*u>n) break;ok[j*u]=false;if (u%j==0) break;}}ok[2]=false;for (LL u=1;u<=n;u++) f[u]=f[u-1]+ok[u];
}
LL ans=0;
LL a[N];
qq b[N],c[N];
LL g[N];//储存所有i+j=k的s[i]*s[j] 
void solve ()//统计情况 
{memset(b,0,sizeof(b));memset(c,0,sizeof(c));LL nn=n*2,now;now=1;while (now<=nn) now<<=1; now<<=1;//for (LL u=0;u<now;u++) b[u]=c[u]=qq(0,0);for (LL u=1;u<=n;u++) b[n+u].x=a[u];for (LL u=1;u<=n;u++) c[n-u].x=a[u];fft(b,now,1);fft(c,now,1);for (LL u=0;u<now;u++) b[u]=b[u]*c[u];fft(b,now,-1);for (LL u=0;u<=n;u++)   if (u%2==0)ans=(ans-(f[u]*(LL)(b[u+nn].x/now+0.5))%MOD)%MOD;if (ans<0) ans+=MOD;ans=ans*2%MOD;//printf("%lld\n",ans);/*i+j<=n+1*/memset(b,0,sizeof(b));memset(c,0,sizeof(c));for (LL u=1;u<=n;u++) b[u].x=a[u];for (LL u=1;u<=n;u++) c[u].x=a[u];now=1;while (now<=nn) now<<=1;fft(b,now,1);fft(c,now,1);for (LL u=0;u<now;u++) b[u]=b[u]*c[u];fft(b,now,-1);for (LL u=0;u<=nn;u++) g[u]=(LL)(b[u].x/now+0.5);for (LL u=1;u<=n+1;u++)//i+j=uif (u%2==0)ans=(ans+g[u]*f[u-1]%MOD)%MOD;for (LL u=n+1;u<=nn;u++)if (u%2==0)ans=(ans+g[u]*f[nn+1-u]%MOD)%MOD;
}
int main()
{//freopen("a.in","r",stdin);scanf("%lld",&n);prepare();/*for (LL u=1;u<=n;u++) printf("%lld ",f[u]);printf("\n");*/for (LL u=1;u<=n;u++) scanf("%lld",&a[u]);solve();for (LL u=1;u<n;u++)    ans=(ans+a[u]*a[u+1]*2%MOD)%MOD;printf("%lld\n",ans);return 0;
}