题目分析
Part 1
首先，它告诉你要选择三家糖果店 \((x,y,z)\) 满足一些条件。我们先一条条分析。
- \(x \leq z\)
这其实就是排了个序。
- \(x = 3y + z\)
稍微整理一下，变成 \(x - z = 3y\)，也就是说 \(3 | x - z\)，也就是说 \(x \equiv z \ (\bmod 3)\)。
到这里，其实我们发现这第二个奇怪的式子其实就是个幌子，目的就是为了告诉你 \(x\) 和 \(z\) 模 \(3\) 同余。
- \(col_x = col_z\)
要求 \(x\) 和 \(z\) 的颜色相同，那么，我们可以将同样颜色糖果店按照编号模 \(3\) 的余数分为三类，我们只需要选择余数相同的糖果店，就可以满足所有要求（对，其实 \(y\) 压根没用）。
那么，我们已经找到了符合题意的所有三元组，该如何统计答案呢？这就是下一个部分了。
PS：Part 2中的三元组指的都是按照上文的分类要求（颜色、模 \(3\) 余数）分类过后的三元组。
Part 2
我们先看一下每个三元组对答案的贡献：\((x + y)(col_x + col_y)(w_x + w_y)\)。看起来好像没什么头绪，于是，我们可以先举个例子算一算。不妨假设有 \(3\) 家糖果店 \(x,y,z\) 符合 Part 1中分析出的要求。
那么对答案的贡献就是：
\[(x + x)(col_x + col_x)(w_x + w_x) + (y + y)(col_y + col_y)(w_y + w_y) + (z + z)(col_z + col_z)(w_z + w_z) + (x + y)(col_x + col_y)(w_x + w_y) + (y + z)(col_y + col_z)(w_y + w_z) + (z + x)(col_z + col_x)(w_z + w_x) \]因为他们的颜色都相同，不妨直接记成 \(c\)。
\[2c(4xw_x) + 2c(4yw_y) + 2c(4zw_z) + 2c(x + y)(w_x + w_y) + 2c(y + z)(w_y + w_z) + 2c(z + x)(w_z + w_x) \] \[2c(4xw_x + 4yw_y + 4zw_z + xw_x+xw_y+yw_x+yw_y+yw_y+yw_z+zw_y+zw_z+zw_z+zw_x+xw_z+xw_x) \] \[2c(x(2w_x+w_y+w_z)+y(w_x+2w_y+w_z)+z(w_x+w_y+2w_z)) \]多举几个例子，我们发现，一般地，对于 \(n\) 家符合 Part 1要求的糖果店，其贡献为：
\(2c(a_1((n+3)w_1+w_2+...+w_n)+a_2(w_1+(n+3)w_2+...+w_n)+...+a_n(w_1+w_2+...+(n+3)w_n))\)
这样的话，我们只需要对于每种颜色模 \(3\) 的每种余数，预处理 \(w_1+w_2+...w_n\) 的结果，就可以 \(O(n)\) 统计答案，具体可参见下方代码。
细节问题
-
对 \(998244353\) 取模。
-
由于中间计算过程中连乘了很多项，为了保险起见，可适当在某些乘号再取模一次，以免爆 int。
代码
#define MOD 998244353
#define MAXN 100000
#define MAXC 100000
#define MAXW 100000//大可不必管这些
#include <cstdio>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
inline int read(){
int t = 0,flag = 1;
register char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1;c = getchar();}
while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
return flag * t;
}//快读，可忽略。a = read() 可以认为等价于 cin >> a
int n,m,ans,col[MAXN],w[MAXN],sum[MAXC][3],tot[MAXC][3];
int main(){
n = read(),m = read();//读入，可以认为等价于 cin >> n >> m;
for (int i = 1;i <= n;i++){
col[i] = read(),w[i] = read();
sum[col[i]][i % 3] += w[i];//统计 w[i] 之和
++tot[col[i]][i % 3];//统计每类的个数
}
for (int i = 1;i <= n;i++){
ans = (ans + 2 * col[i] % MOD * (i * (sum[col[i]][i % 3] + (tot[col[i]][i % 3] + 2))) % MOD) % MOD;//那行统计答案的式子，略有改动
}
printf("%d\n",ans % MOD);
return 0;
}