求和(NOIP2015)

題目連結：​​求和​​​

這道題不是很簡單，因為資料并不是很小，正常計算會t。

這裡引用chenleyu的解答（如果想要cgg原創解答，……改天吧）：

這題相對是比較難的,首先我們要解讀題目的意思

一條狹長的紙帶被均勻劃分出了n個格子，格子編号從1到n。每個格子上都染了一種顔色color_i用[1，m]當中的一個整數表示），并且寫了一個數字number_i。

由這段不難得到,所謂紙帶,其實就是一個集合組,每一個小集合(格子)裡都有三個元素:編号,顔色和上面寫的數

就是這樣

紙帶[]

|num,col,i|num,col,i|num,col,i||num,col,i||num,col,i||num,col,i|

然後我們再來看那神奇的三元組

“定義一種特殊的三元組：(x,y,z)，其中x，y，z都代表紙帶上格子的編号，這裡的三元組要求滿足以下兩個條件：

1.xyz是整數,x小于y小于z，y-x=z-y

2.colorx=colorz

滿足上述條件的三元組的分數規定為(x+z)*(number_x+number_z)”

我們看三元組的第一個條件

首先x小于y小于z這很容易了解，我們來看y-x=z-y

通過等式的性質，我們可以将它進行一些變換

y-x=z-y

y+y=z+x

z+x=2y

這樣就可以知道z+x必為偶數，那又因為

奇數+奇數=偶數

偶數+偶數=偶數

奇數+偶數=奇數

是以x和z的奇偶性一定相同

是以題目三元組的條件就可以化為

1 z>x

2 z和x的奇偶性相同

3 z格和x格的顔色相同

（跟y一點關系也沒有）

換句話說，隻要有兩個數奇偶性相同，顔色相同，那他們必是會産生分數的

再來看分數的計算

分數=（x+z）*（num[x]+num[z]）

我們再來做一點變換

根據乘法配置設定律

（x+z）*（num[x]+num[z]）

=x*num[x]+x*num[z]+z*num[x]+z*num[z]

那假設i1，i2，i3，i4….的奇偶性相同，顔色相同，那麼

他們的得分就為

(i1*num[i1]+i1*num[i2]+i2*num[i1]+i2*num[i3])+(i1*num[i1]+i1*num[i3]+i3*num[i1]+i3*num[i3])+…………..

把括号去掉，把和i1有關的放在一起，把和in有關的放在一起

就成了這樣

i1*num[i1]+i1*num[i2]+ i1*num[i1]+i1*num[i3]+…….(和i1有關的)

=i1*(num[i1]+num[i2]+…….+num[in])+n*(i1*num[i1])

于是我們就可以得到這個公式

和in有關的得分就

= in*(num[i1]+num[i2]+…….+num[in])+n*(in*num[in])

再把i1，i2，i3….in的得分加起來就是總分了

#include<bits/stdc++.h>
#ifdef WIN32                  //1
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
int n,c;
int sum[2][100001]={0};
int d[2][100001]={0};
int num[100001];
int col[100001];
long long maxx=0;
int main()
{
    scanf("%d%d",&n,&c);
    for (int i=1;i<=n;i++){
        scanf("%d",&num[i]);
        num[i]%=10007;    
    }
    int n1=0,n2=0;
    for (int i=1;i<=n;i++){
        scanf("%d",&col[i]);
        sum[i%2][col[i]]+=num[i];       //2    
        sum[i%2][col[i]]%=10007;
        d[i%2][col[i]]++;        
    }
    for (int i=1;i<=n;i++){
        maxx+=1LL*i%10007*((sum[i%2][col[i]]+(d[i%2][col[i]]-2)%10007*num[i]+10007)%10007);   //3
        maxx%=10007;        
    }
    printf(LL,maxx);
    return 0;
}