洛谷 P2671 [NOIP2015 普及组] 求和

2023-11-04 15:51:10

Description

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ieUYI0vp-1636554354924)(1829-2364231.png)]

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

x y z xyz xyz是整数, x < y < z , y − x = z − y x<y<z,y-x=z-y x<y<z,y−x=z−y
c o l o r x = c o l o r z color\,x=color\,z colorx=colorz

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

Input

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

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

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

Output

一个整数，表示所求的纸带分数除以1000710007所得的余数。

Solution

1.纯模拟肯定超时，需要用数论思维化简。

2.三元组要求 y − x = z − y y-x = z-y y−x=z−y ，且x与z颜色相同。

则不难看出 x + z = 2 ∗ y x+z = 2*y x+z=2∗y ，需要x与z的奇偶性与颜色一致，在读入数据时可以根据此分类。

3.根据分类得出的数据优化。

设每个分类得出的部分有k个数，每个数下标分别为 x [ 1 ] , x [ 2 ] , . . . , x [ k ] x[1],x[2],...,x[k] x[1],x[2],...,x[k] ，在number数组中的值为 y [ 1 ] , y [ 2 ] , . . . , y [ k ] y[1],y[2],...,y[k] y[1],y[2],...,y[k] ，那么该分类部分对答案的贡献为

Δ a n s = ( x [ 1 ] + x [ 2 ] ) ∗ ( y [ 1 ] + y [ 2 ] ) + ( x [ 1 ] + x [ 3 ] ) ∗ ( y [ 1 ] + y [ 3 ] ) + . . . + ( x [ 1 ] + x [ k ] ) ∗ ( y [ 1 ] + y [ k ] ) + ( x [ 2 ] + x [ 3 ] ) ∗ ( y [ 2 ] + y [ 3 ] ) + . . . . ( x [ 2 ] + x [ k ] ) ∗ ( y [ 2 ] + y [ k ] ) + ( x [ k − 1 ] + x [ k ] ) ∗ ( y [ k − 1 ] + y [ k ] ) \Delta ans = \\ \quad (x[1]+x[2])*(y[1]+y[2])+(x[1]+x[3])*(y[1]+y[3])+...+(x[1]+x[k])*(y[1]+y[k])\\\,+(x[2]+x[3])*(y[2]+y[3])+....(x[2]+x[k])*(y[2]+y[k])\\\ +(x[k-1]+x[k])*(y[k-1]+y[k]) Δans=(x[1]+x[2])∗(y[1]+y[2])+(x[1]+x[3])∗(y[1]+y[3])+...+(x[1]+x[k])∗(y[1]+y[k])+(x[2]+x[3])∗(y[2]+y[3])+....(x[2]+x[k])∗(y[2]+y[k]) +(x[k−1]+x[k])∗(y[k−1]+y[k])

对x[i]运用分配率得

= ( ∑ i = 1 k − 1 ∑ j = i + 1 k x [ i ] ∗ ( y [ i ] + y [ j ] ) ) + ( ∑ j = 2 k ∑ i = 1 j − 1 x [ j ] ∗ ( y [ i ] + y [ j ] ) ) = (\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} x[i]*(y[i]+y[j]))\\ + (\sum_{j=2}^{k}\sum_{i=1}^{j-1}x[j]*(y[i]+y[j])) =(∑i=1k−1∑j=i+1kx[i]∗(y[i]+y[j]))+(∑j=2k∑i=1j−1x[j]∗(y[i]+y[j]))

= ∑ i = 1 k x [ i ] ( ∑ j = i + 1 k ( y [ i ] + y [ j ] ) + ∑ j = 1 i − 1 ( y [ j ] + y [ i ] ) ) =\sum_{i=1}^{k}x[i](\sum_{j=i+1}^{k}(y[i]+y[j])+\sum_{j=1}^{i-1}(y[j]+y[i])) =∑i=1kx[i](∑j=i+1k(y[i]+y[j])+∑j=1i−1(y[j]+y[i]))

= ∑ i = 1 k x [ i ] ( ∑ j = 1 k y [ j ] + ( k − 2 ) y [ i ] ) =\sum_{i=1}^{k}x[i](\sum_{j=1}^{k}y[j]+(k-2)y[i]) =∑i=1kx[i](∑j=1ky[j]+(k−2)y[i])

其中， ∑ j = 1 k y [ j ] \sum_{j=1}^{k}y[j] ∑j=1ky[j] 为定值，可以用前缀和解决

总复杂度 O ( n ) O(n) O(n)

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MOD 10007
#define intmax 2147483647
#define memmax 0x7fffffff

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

ll n, m;
ll number[100005], color[100005];
ll noof[100005][2], pre[100005][2];
ll ans;

void solve()
{
    n = read(), m = read();
    for(int i=1; i<=n; i++)
    {
        number[i] = read();
    }
    for(int i=1; i<=n; i++)
    {
        color[i] = read();

        // 统计当前分类容器数量
        noof[color[i]][i%2]++;
        // 前缀number[i]的和
        pre[color[i]][i%2] = (pre[color[i]][i%2] + number[i]) %MOD;
    }

    for(int i=1; i<=n; i++)
    {
        // (noof[color[i]][i%2]-2) == n-2
        // i == x[i]
        // number[i] == y[i]
        ans = (ans + (i * ((noof[color[i]][i%2]-2)*number[i] %MOD + pre[color[i]][i%2]) ) ) %MOD;
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve();
}

码农公寓