模拟($On^2$ 40pts)

• 枚举左端点和中间点，计算右边界，然后对符合条件的点进行累加。

#include<bits/stdc++.h>
using namespace std;
const int N=100010,mod=10007;
int a[N],b[N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
	}
	int ans=0;
	for(int x=1;x<=n;x++) //枚举左边元素
	{
		for(int y=x+1;2*y-x<=n;y++) //枚举中间元素 
		{
			int z=2*y-x; //最右边元素 
			if(b[x]==b[z])
			{
				ans=(ans+(2*y)%mod*(a[x]+a[z])%mod)%mod;
			}
		}	
	} 
	cout<<ans;
	return 0;
}

分类模拟(80pts)

• 将每种颜色分类讨论统计，统计分析易得只有相同的颜色才可能符合条件,在颜色相同的条件下,只需要满足$y-x=z-y$,也就是说$y=\frac {z+x} 2$是整数即符合条件。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,MOD=10007;
typedef pair<int,int> PII;
#define x first
#define y second
int n,m;
int num[N],col[N];
vector<PII> q[N][2];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>num[i]; //数字
    for(int i=1;i<=n;i++) cin>>col[i]; //颜色
    for(int i=1;i<=n;i++)
    {
        q[col[i]][i%2].push_back({i,num[i]%MOD}); //同颜色，同奇偶
    }
    int res=0;
    for(int i=1;i<=m;i++) //枚举颜色
    {
        for(int j=0;j<2;j++) //枚奇/偶
        {
            vector<PII> v=q[i][j];
            for(int a=0;a<v.size();a++) //枚举x
            {
                for(int b=a+1;b<v.size();b++) //枚举y
                {
                    res=(res+(v[a].x+v[b].x)%MOD*(v[a].y+v[b].y)%MOD)%MOD;
                }
            }
        }
    }
    cout<<res;
    return 0;
}

分类统计+前缀和优化(100pts)

• 在最后计算的时候再加上前缀和即可使程序的复杂度变成$O(n)$的

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,MOD=10007;
typedef pair<int,int> PII;
#define x first
#define y second
int n,m;
int s1[N],s2[N],s3[N];
int num[N],col[N];
vector<PII> q[N][2];
int work(vector<PII> p) //计算同一种颜色，奇偶相同的分数
{
    int k=p.size(); //数组长度
    for(int i=1;i<=k;i++)
    {
        s1[i]=(s1[i-1]+p[i-1].x)%MOD; // 编号
        s2[i]=(s2[i-1]+p[i-1].y)%MOD; //数字
        s3[i]=(s3[i-1]+p[i-1].x*p[i-1].y)%MOD; //编号*数字
    }
    int res=0;
    for(int i=1;i<=k;i++)
    {
        int x=p[i-1].x,nx=p[i-1].y;
        res=(res+x*nx%MOD*(k-i)%MOD+x*(s2[k]-s2[i])%MOD+nx*(s1[k]-s1[i])%MOD+(s3[k]-s3[i])%MOD)%MOD;
    }
    /*
    (x+z)*(nx+nz)=x*nx+ x*nz+z*nx+z*nz
    当x固定时->等价于x*nx*z的个数+x*nz x的后面所有数的和+nx*z x后面的所有数的编号+z*nz x后面的所有数的编号*对应上的数字
    */
    return res; //返回总和
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>num[i]; //数字
    for(int i=1;i<=n;i++) cin>>col[i]; //颜色
    for(int i=1;i<=n;i++)
    {
        q[col[i]][i%2].push_back({i,num[i]%MOD}); //同颜色，同奇偶
    }
    int res=0;
    for(int i=1;i<=m;i++) //枚举颜色
    {
        for(int j=0;j<2;j++) //枚奇/偶
        {
            res=(res+work(q[i][j]))%MOD;
        }
    }
    cout<<(res+MOD)%MOD;
    return 0;
}