文件名称：sequence.pdf
文件大小：117KB
文件格式：PDF
更新时间：2023-06-23 12:24:33
NOIP C++ 信奥
时间限制： 2.0 秒 空间限制： 256 MB 题目描述 给定一个长度为 的非负整数序列 ，对于 的一个子序列 （ ， ，下同），称 是 的优秀子序列当且仅当，其任意两个不同元素的按位与结果均为 0，即： ，满足： ，其中 是按位与运算。 对于子序列 ，我们定义其价值为 ，其中 表示小等于 的正整数中与 互质的数的个数。 现在请你求出 的所有优秀子序列的价值之和，答案对 取模。 输入格式 第一行一个正整数 表示序列长度。 第二行 个用空格分隔的非负整数，表示 。 输出格式 仅一行一个整数，表示答案对 取模的结果。 样例1输入 4 1 2 2 3 n A = {a ,a ,⋯ ,a } 1 2 n A B = {a ,a ,⋯ ,a } b 1 b 2 b m 0 ≤ m ≤ n 1 ≤ b < 1 b < 2 ⋯ < b ≤ m n B A ∀1 ≤ i < j ≤ m a and a = b i b j 0 and B = {a ,a ,⋯ ,a } b 1 b 2 b m φ(1 + a ) ∑ i=1 m b i φ(x) x x A 10 + 9 7 n n a ,a ,⋯ ,a 1 2 n 10 + 9 7 样例1输出 12 样例1解释 符合条件的子序列有： ， ， ， ， ， ， ，它们价值依次为 1，1，2，2，2，2，2，总和为 12。 数据范围与提示 对于 的数据，满足 。 对于 的数据，满足 。 对于 的数据，满足 。 另有 的数据，满足 。 对于所有数据，满足 ， 。