洛谷 P3123 总结

发布时间 2023-06-08 11:49:58作者: xiehanrui0817

题目:洛谷 P3123

链接:洛谷逐月

题意

  • 给定整式 \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\),其中包含 \(7\) 个变量,现在给定一个包含 \(n\) 个整数的表格,每一行给定一个变量和一个整数 \(x\),表示这个变量可能\(x\),问有几种赋值方式使得整式的值为 \(7\) 的倍数。

  • \(1 \le n \le 500, -10^5 \le x \le 10^5\),所有输入均为整数

思路

  • 我们可以发现直接搜索每个数的值是会炸的,所以我们可以用桶记录每个变量对用数值出现了几次,搜索每个数的数值,但是 \(x\) 太大了,怎么办呢?

  • 我们发现答案要求是 \(7\) 的倍数,所有 \(x\) 只有它对 \(7\) 取模后的余数有用,所以 \(x \% \! = 7\),在搜索就可以啦。

  • 注意 \(x\) 为负数的问题,非常的坑,取模时特判一下即可。

时间复杂度

搜索变量的所有取值以及输入:\(O(7^7 + n)\)