求和

Problem description

问题描述

一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色color_i（用[1，m]当中的一个整数表示），并且写了一个数字number_i。

　　定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：
　　xyz是整数,x<y<z，y-x=z-y colorx=colorz　　

满足上述条件的三元组的分数规定为(x+z)*(number_x+number_z)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。

Input format

第一行是用一个空格隔开的两个正整数n和m，n表纸带上格子的个数，m表纸带上颜色的种类数。
　　第二行有n用空格隔开的正整数，第i数字number表纸带上编号为i格子上面写的数字。
　　第三行有n用空格隔开的正整数，第i数字color表纸带上编号为i格子染的颜色。

Output format

共一行，一个整数，表示所求的纸带分数除以10,007所得的余数。

Algorithm design

Simple enumeration + Mathematics deal

Problem analysis

核心：数据分离

N太大直接搞O（N2）

读题

x<y<z，y-x=z-y，colorx=colorz
翻译一下

x,z奇偶性相同且同种颜色

那么把n拆成两条链：奇数链，偶数链，两链互不相干

对于链上所有同种颜色的点都可以求分数

既然如此再看

(x+z)*(number_x+number_z)

拆解后

x*num_x+z*num_z+x*num_z+z*num_x

前缀和思想

取一点x 那么关于x的所有三元组的分数之和

即

x*num_x*cnt_others + sumcnt_others + x*numcnt_others + num_x*idcnt_others

所以只需要分两条链

枚举每个点

根据其颜色进行处理

O(2n)

Anyway

把cnt处理完了再搞会有一倍冗出

所以边枚举边搞最好

先前忘了这点愣了几分钟

错误记录

1.没把ans求余

2.没考虑sum也很大也要求余

3.即使执行上述操作 sum还是很大所以开ll

Source code

 1 #include <bits/stdc++.h>
 2 #define F(i,j,k) for(int i=j;i<=k;i++)
 3 #define D(i,j,k) for(int i=j;i>=k;i--)
 4 #define sc(i) scanf("%lld",&i)
 5 #define mo 10007
 6 #define ll long long
 7 #define R return
 8  
 9 using namespace std;
10  
11 int n,m;
12 llans,num[100010],col[100010],sumnu[100010],sum[100010],sumid[100010],cnt[100010];
13  
14 void read()
15 {
16    cin>>n>>m;
17    F(i,1,n)sc(num[i]);
18    F(i,1,n)sc(col[i]);
19    R;
20 }
21  
22 void work()
23 {
24    F(jff,1,2)
25    {
26       memset(sumid,0,sizeof(sumid));
27       memset(sumnu,0,sizeof(sumnu));
28       memset(sum,0,sizeof(sum));
29       memset(cnt,0,sizeof(cnt));
30       for(int i=jff;i<=n;i+=2)
31       {
32          ans=(ans+sum[col[i]]+num[i]*i*cnt[col[i]])%mo;
33          ans=(ans+sumnu[col[i]]*i)%mo;
34          ans=(ans+sumid[col[i]]*num[i])%mo;
35 //通过前缀和计算 将结果数添加
36          sumid[col[i]]=(sumid[col[i]]+i)%mo;
37          sumnu[col[i]]=(sumnu[col[i]]+num[i])%mo;
38          sum[col[i]]=(sum[col[i]]+num[i]*i)%mo;
39 //像前面说的边推进边处理所有前缀和
40       }
41    }
42    cout<<ans<<endl;
43    R;
44 }
45  
46      
47  
48 int main()
49 {
50    freopen("sum.in","r",stdin);
51    freopen("sum.out","w",stdout);
52    read();
53    work();
54    R 0;
55 }
56

View Code

over