题目:洛谷 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)\)。