2015NOIP普及组第四题求和满分解法

你的名字 2021-03-29 13:37 435阅读 0赞

*经过两年再写这道题，还是能感到水平的提升的（*你一直都很弱好吗）

## 题目描述 ##

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

![img][]

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

1.  xyz是整数,x

### 输入输出格式 ###

输入格式：

第一行是用一个空格隔开的两个正整数n和m，n表纸带上格子的个数，m表纸带上颜色的种类数。

第二行有n用空格隔开的正整数，第i数字number表纸带上编号为i格子上面写的数字。

第三行有n用空格隔开的正整数，第i数字color表纸带上编号为i格子染的颜色。

输出格式：

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

### 输入输出样例 ###

输入样例\#1：

复制

6 2
    5 5 3 2 2 2
    2 2 1 1 2 1

输出样例\#1：

复制

输入样例\#2：

复制

15 4
    5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
    2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

输出样例\#2：

复制

1388

### 说明 ###

【输入输出样例 1 说明】

纸带如题目描述中的图所示。

所有满足条件的三元组为： (1, 3, 5), (4, 5, 6)。

所以纸带的分数为(1 + 5)*(5 + 2) + (4 + 6)*(2 + 2) = 42 + 40 = 82。

对于第 1 组至第 2 组数据， 1 ≤ n ≤ 100, 1 ≤ m ≤ 5；

对于第 3 组至第 4 组数据， 1 ≤ n ≤ 3000, 1 ≤ m ≤ 100；

对于第 5 组至第 6 组数据， 1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000，且不存在出现次数

超过 20 的颜色；

对 于 全 部 10 组 数 据 ， 1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ color\_i ≤ m，1≤number\_i≤100000

## 解法 ##

主要记录我的思考过程，想看正解直接向下翻。

由题可知Y是X和Z的中位数，所以2Y=X+Z，于是我就想暴力Y，然后穷尽X，再通过Y退出Z，但是这样做是N^2的，N的数据范围是10的五次方，所以不行。

再仔细想一想，把题目中的那个求和公式拆开，就能得到新的信息，（设X为A，Z为B，number\_x为C，number\_z为D）每一组的分数为AC+AD+BC+BD，那也就是说，与A一组的所有数是可以通过结合律累加的，以此类推，于是我们就要找出与A相同的所有数，其实就是分类。

我是这样分的，按颜色分类，再按序号的奇数和偶数分，因为一组的X和Z要不都是奇数，要不都是偶数，再把他们都丢到同一个颜色里，就不需要检验了。可是分下来暴力计算还是N^2的，如何变成N呢，就要用到刚才的东西了。

我们拿一组相同颜色的，都是奇数的四个数来举例。加入将这一组所有的式子全部拆开来，如下，可以得到公式，就能在O(N)的时间内搞定了。（线表示相乘关系）可以发现，每一个序号与下方每一个num都乘了一遍，并且与自己多成了总数-2遍（因为和其他每一个序号（总数-1个）组合的时候都与自己乘了一遍，除去算作总数的一遍，还剩总数-2个），就按照这个算就行了。!\[屏幕快照 2017-11-09 下午11.47.09\](/Users/yujian/Desktop/屏幕快照 2017-11-09 下午11.47.09.png)

## 程序 ##

激动人心

//库省略
    #define fi first
    #define se second
    #define mp make_pair
    #define pb push_back
    #define ll long long
    #define pii pair<int,int>
    #define pai pair<int,pii>
    using namespace std;
    const int maxn=100005,modn=10007;
    int n,m;
    ll ans;
    int col[maxn],num[maxn],sum1[maxn],sum2[maxn];
    vector<int> colv1[maxn],colv2[maxn];
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",num+i);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",col+i);
            if(i%2)
            {
                colv1[col[i]].pb(i);
                sum1[col[i]]+=num[i];
                sum1[col[i]]=sum1[col[i]]%modn;
            }
            else
            {
                colv2[col[i]].pb(i);
                sum2[col[i]]+=num[i];
                sum2[col[i]]=sum2[col[i]]%modn;
            }
        }
        for(int i=1;i<=m;i++)
        {
            int k=i;
            if(colv1[k].size()>=2)
            {
                ll sum=0,siz=colv1[k].size()-2;
                for(int j=0;j<colv1[k].size();j++)
                {
                    int now=colv1[k][j];
                    sum+=now*sum1[k];
                    sum=sum%modn;
                    sum+=now*siz*num[now];
                    sum=sum%modn;
                }
                ans+=sum;
                ans=ans%modn;
            }
            if(colv2[k].size()>=2)
            {
                ll sum=0,siz=colv2[k].size()-2;
                for(int j=0;j<colv2[k].size();j++)
                {
                    int now=colv2[k][j];
                    sum+=now*sum2[k];
                    sum=sum%modn;
                    sum+=now*siz*num[now];
                    sum=sum%modn;
                }
                ans+=sum;
                ans=ans%modn;
            }
        }
        ans=ans%modn;
        cout<<ans<<endl;
        return 0;
    }

[img]: /images/20210329/1617025015735.png