会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
题目要求从数组中选出若干元素组成子序列，使得子序列元素之和既是 3 的倍数又是 5 的倍数，但不能是 4 的倍数。
- “既是 3 的倍数又是 5 的倍数”等价于 该和是 15 的倍数。
- 在 15 的倍数中剔除 4 的倍数，相当于要求 和是 15 的倍数但不是 60 的倍数（因为 15 和 4 的最小公倍数是 60）。
- 在模 60 的意义下，15 的倍数有 0, 15, 30, 45；其中 0 同时也是 4 的倍数（60 的倍数），需要排除。因此满足条件的和的模 60 余数只能是 15, 30, 45。
问题转化为：求所有子序列中，元素之和模 60 等于 15、30 或 45 的方案数，对 109+7 取模。
