Candies and Shops题解

Candies and Shops

题目分析

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;
}
上一篇:Codeforces Round #683 (Div. 2) Problem - A.Add Candies 题解


下一篇:LeetCode算法题:拥有糖果最多的孩子