G. Sum the Fibonacci

Codeforces

IDCF914G

Time4000ms

Memory256MB

Difficulty—

bitmasksdivide and conquerdpfftmath

English · Original

Chinese · Translation

Formal · Original

You are given an array _s_ of _n_ non-negative integers. A 5-tuple of integers (_a_, _b_, _c_, _d_, _e_) is said to be valid if it satisfies the following conditions: * 1 ≤ _a_, _b_, _c_, _d_, _e_ ≤ _n_ * (_s__a_ | _s__b_) & _s__c_ & (_s__d_ ^ _s__e_) = 2_i_ for some integer _i_ * _s__a_ & _s__b_ = 0 Here, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation. Find the sum of _f_(_s__a_|_s__b_) * _f_(_s__c_) * _f_(_s__d_^_s__e_) over all valid 5-tuples (_a_, _b_, _c_, _d_, _e_), where _f_(_i_) is the _i_\-th Fibonnaci number (_f_(0) = 0, _f_(1) = 1, _f_(_i_) = _f_(_i_ - 1) + _f_(_i_ - 2)). Since answer can be is huge output it modulo 109 + 7. ## Input The first line of input contains an integer _n_ (1 ≤ _n_ ≤ 106). The second line of input contains _n_ integers _s__i_ (0 ≤ _s__i_ < 217). ## Output Output the sum as described above, modulo 109 + 7 [samples]

给定一个包含 #cf_span[n] 个非负整数的数组 #cf_span[s]。一个整数五元组 #cf_span[(a, b, c, d, e)] 被称为有效的，当且仅当它满足以下条件：这里，'|' 表示按位或，'&' 表示按位与，'^' 表示按位异或运算。求所有有效五元组 #cf_span[(a, b, c, d, e)] 上 #cf_span[f(sa]|#cf_span[sb) * f(sc) * f(sd]^#cf_span[se)] 的和，其中 #cf_span[f(i)] 表示第 #cf_span[i] 个斐波那契数（#cf_span[f(0) = 0, f(1) = 1, f(i) = f(i - 1) + f(i - 2)]）。由于答案可能很大，请输出其对 #cf_span[109 + 7] 取模的结果。输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 106]）。第二行包含 #cf_span[n] 个整数 #cf_span[si]（#cf_span[0 ≤ si < 217]）。请输出如上所述的和，对 #cf_span[109 + 7] 取模。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 106]）。第二行包含 #cf_span[n] 个整数 #cf_span[si]（#cf_span[0 ≤ si < 217]）。 ## Output 请输出如上所述的和，对 #cf_span[109 + 7] 取模。 [samples]

Let $ s = [s_0, s_1, \dots, s_{n-1}] $ be an array of $ n $ non-negative integers, with $ 0 \leq s_i < 2^{17} $. Let $ f(i) $ denote the $ i $-th Fibonacci number, defined by: $$ f(0) = 0, \quad f(1) = 1, \quad f(i) = f(i-1) + f(i-2) \text{ for } i \geq 2. $$ A 5-tuple $ (a, b, c, d, e) \in \{0, 1, \dots, n-1\}^5 $ is **valid** if and only if: $$ (s_a \mid s_b) \& (s_c \oplus s_d) = s_e. $$ Define the sum: $$ \sum_{\substack{(a,b,c,d,e) \in [n]^5 \\ (s_a \mid s_b) \& (s_c \oplus s_d) = s_e}} f(s_a \mid s_b) \cdot f(s_c) \cdot f(s_d) \cdot f(s_e) \mod (10^9 + 7). $$ Compute this sum modulo $ 10^9 + 7 $.

Samples

Input #1

2
1 2

Output #1

Input #2

3
7 4 1

Output #2

Input #3

10
1 3 0 7 3 7 6 5 7 5

Output #3

Input #4

10
50 9 11 44 39 40 5 39 23 7

Output #4

113860062

API Response (JSON)

{
  "problem": {
    "name": "G. Sum the Fibonacci",
    "description": {
      "content": "You are given an array _s_ of _n_ non-negative integers. A 5-tuple of integers (_a_, _b_, _c_, _d_, _e_) is said to be valid if it satisfies the following conditions: *   1 ≤ _a_, _b_, _c_, _d_, _e_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF914G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array _s_ of _n_ non-negative integers.\n\nA 5-tuple of integers (_a_, _b_, _c_, _d_, _e_) is said to be valid if it satisfies the following conditions:\n\n*   1 ≤ _a_, _b_, _c_, _d_, _e_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 #cf_span[n] 个非负整数的数组 #cf_span[s]。\n\n一个整数五元组 #cf_span[(a, b, c, d, e)] 被称为有效的，当且仅当它满足以下条件：\n\n这里，'|' 表示按位或，'&' 表示按位与，'^' 表示按位异或运算。\n\n求所有有效五元组 #cf_span[(a, b, c, d, e)] 上 #cf_span[f(sa]|#cf_span[sb) ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s = [s_0, s_1, \\dots, s_{n-1}] $ be an array of $ n $ non-negative integers, with $ 0 \\leq s_i < 2^{17} $.\n\nLet $ f(i) $ denote the $ i $-th Fibonacci number, defined by:\n$$\nf(0) = 0, \\quad f(1)...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments