問題#
[NOIP2015 普及组] 和を求める#
問題背景#
NOIP2015 普及组 T3
問題の説明#
細長い紙テープが均等に $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) \times (number_x+number_z)$ と定義されます。全体の紙テープのスコアは、条件を満たすすべての三つ組のスコアの合計です。このスコアは非常に大きくなる可能性があるため、全体の紙テープのスコアを $10,007$ で割った余りを出力してください。
（$n, m <= 100000$）
解答#
まず、結果が y に全く関係ないことが一目でわかります。y が唯一制限するのは x であり、z の奇偶性は同じでなければなりません。
したがって、答えに入るマスの間は同じ奇偶性かつ同じ色である必要があります。同じ奇偶性と色を持つマスをグループに分けます。
その中の一つのグループを考え、差分法を考慮します。新しい数が追加されると、答えにどれだけの貢献をするかを見てみましょう。
表を描くと、次のようにわかります。
| number\ 番号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| n_1 | 1 | 1 | ||
| n_2 | 1 | 1 | ||
| n_3 | 1 | 1 | ||
| n_4 | 1 | 1 | 1 | 1+1+1 |
例えば、このグループの 4 番目を追加すると、次のような貢献が生まれます。
その後、前方和を統計し、計算できます。
コード#
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
const int N = 100100;
const int mod = 10007;
int counta[N][2], sum_n[N][2], sum_f[N][2], sum_fn[N][2];//count i,j は色がi、番号がjの数量を表し、sum i,j は色がi、番号がjの
int a[N], b[N];
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
signed main()
{
n = read(), m = read();
long long ans = 0;
for(int i = 1;i <= n;i++)
{
a[i] = read();//数字——n
}
for(int i = 1;i <= n;i++)
{
b[i] = read();//色——b
}
for(int i = 1;i <= n;i++)
{
ans = (ans + sum_fn[b[i]][i % 2]) % mod;
counta[b[i]][i % 2] ++;
sum_f[b[i]][i % 2] = (sum_f[b[i]][i % 2] + i) % mod;
sum_n[b[i]][i % 2] = (sum_n[b[i]][i % 2] + a[i]) % mod;
sum_fn[b[i]][i % 2] = (sum_fn[b[i]][i % 2] + (i * a[i]) % mod) % mod;
ans = (ans + (i * sum_n[b[i]][i % 2]) % mod) % mod;
ans = (ans + (a[i] * sum_f[b[i]][i % 2]) % mod) % mod;
ans = (ans + (( (counta[b[i]][i % 2] - 3) * i * a[i]) % mod + mod ) % mod) % mod;
}
printf("%lld", ((ans % mod) + mod) % mod);
return 0;
}