D. Varying Kibibits

Codeforces

IDCF772D

Time3000ms

Memory256MB

Difficulty—

bitmasksdp

English · Original

Chinese · Translation

Formal · Original

You are given _n_ integers _a_1, _a_2, ..., _a__n_. Denote this list of integers as _T_. Let _f_(_L_) be a function that takes in a non-empty list of integers _L_. The function will output another integer as follows: * First, all integers in _L_ are padded with leading zeros so they are all the same length as the maximum length number in _L_. * We will construct a string where the _i_\-th character is the minimum of the _i_\-th character in padded input numbers. * The output is the number representing the string interpreted in base 10. For example _f_(10, 9) = 0, _f_(123, 321) = 121, _f_(530, 932, 81) = 30. Define the function Here, denotes a subsequence.In other words, _G_(_x_) is the sum of squares of sum of elements of nonempty subsequences of _T_ that evaluate to _x_ when plugged into _f_ modulo 1 000 000 007, then multiplied by _x_. The last multiplication is not modded. You would like to compute _G_(0), _G_(1), ..., _G_(999 999). To reduce the output size, print the value , where denotes the bitwise XOR operator. ## Input The first line contains the integer _n_ (1 ≤ _n_ ≤ 1 000 000) — the size of list _T_. The next line contains _n_ space-separated integers, _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 999 999) — the elements of the list. ## Output Output a single integer, the answer to the problem. [samples] ## Note For the first sample, the nonzero values of _G_ are _G_(121) = 144 611 577, _G_(123) = 58 401 999, _G_(321) = 279 403 857, _G_(555) = 170 953 875. The bitwise XOR of these numbers is equal to 292 711 924. For example, , since the subsequences \[123\] and \[123, 555\] evaluate to 123 when plugged into _f_. For the second sample, we have For the last sample, we have , where is the binomial coefficient.

你被给定 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]。记这个整数列表为 #cf_span[T]。定义函数 #cf_span[f(L)]，它接受一个非空整数列表 #cf_span[L]。该函数将输出另一个整数，如下所示：例如 #cf_span[f(10, 9) = 0]，#cf_span[f(123, 321) = 121]，#cf_span[f(530, 932, 81) = 30]。定义函数换句话说，#cf_span[G(x)] 是所有非空子序列的平方和之和，这些子序列在代入 #cf_span[f] 后结果为 #cf_span[x]，结果对 #cf_span[1 000 000 007] 取模，然后再乘以 #cf_span[x]。最后一次乘法不取模。你希望计算 #cf_span[G(0), G(1), ..., G(999 999)]。为减少输出大小，请输出这些值的异或和，其中表示按位异或运算符。第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000 000]) —— 列表 #cf_span[T] 的大小。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 999 999]) —— 列表的元素。输出一个整数，即问题的答案。对于第一个样例，#cf_span[G] 的非零值为 #cf_span[G(121) = 144 611 577]，#cf_span[G(123) = 58 401 999]，#cf_span[G(321) = 279 403 857]，#cf_span[G(555) = 170 953 875]。这些数的按位异或等于 #cf_span[292 711 924]。例如，，因为子序列 #cf_span[[123]] 和 #cf_span[[123, 555]] 在代入 #cf_span[f] 时结果为 #cf_span[123]。对于第二个样例，我们有对于最后一个样例，我们有，其中是二项式系数。 ## Input 第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000 000]) —— 列表 #cf_span[T] 的大小。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 999 999]) —— 列表的元素。 ## Output 输出一个整数，即问题的答案。 [samples] ## Note 对于第一个样例，#cf_span[G] 的非零值为 #cf_span[G(121) = 144 611 577]，#cf_span[G(123) = 58 401 999]，#cf_span[G(321) = 279 403 857]，#cf_span[G(555) = 170 953 875]。这些数的按位异或等于 #cf_span[292 711 924]。例如，，因为子序列 #cf_span[[123]] 和 #cf_span[[123, 555]] 在代入 #cf_span[f] 时结果为 #cf_span[123]。对于第二个样例，我们有对于最后一个样例，我们有，其中是二项式系数。

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ T = (a_1, a_2, \dots, a_n) $ with $ a_i \in \{0, 1, \dots, 999999\} $. Let $ f(L) $ be a function on non-empty subsequences $ L \subseteq T $, defined as: $$ f(L) = \left| \sum_{x \in L} x - \sum_{x \in L} \text{reverse}(x) \right| $$ where $ \text{reverse}(x) $ denotes the integer formed by reversing the decimal digits of $ x $ (e.g., $ \text{reverse}(123) = 321 $, $ \text{reverse}(530) = 35 $). Let $ G(x) $ be defined for $ x \in \{0, 1, \dots, 999999\} $ as: $$ G(x) = x \cdot \left( \sum_{\substack{L \subseteq T \\ L \neq \emptyset \\ f(L) = x}} \left( \sum_{y \in L} y \right)^2 \right) $$ (Only the sum of squares is taken modulo $ 10^9 + 7 $; the final multiplication by $ x $ is not modded.) **Constraints** 1. $ 1 \le n \le 10^6 $ 2. $ 0 \le a_i \le 999999 $ for all $ i $ **Objective** Compute: $$ \bigoplus_{x=0}^{999999} G(x) $$ where $ \oplus $ denotes bitwise XOR.

Samples

Input #1

3
123 321 555

Output #1

292711924

Input #2

1
999999

Output #2

997992010006992

Input #3

10
1 1 1 1 1 1 1 1 1 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Varying Kibibits",
    "description": {
      "content": "You are given _n_ integers _a_1, _a_2, ..., _a__n_. Denote this list of integers as _T_. Let _f_(_L_) be a function that takes in a non-empty list of integers _L_. The function will output another i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF772D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _n_ integers _a_1, _a_2, ..., _a__n_. Denote this list of integers as _T_.\n\nLet _f_(_L_) be a function that takes in a non-empty list of integers _L_.\n\nThe function will output another i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]。记这个整数列表为 #cf_span[T]。\n\n定义函数 #cf_span[f(L)]，它接受一个非空整数列表 #cf_span[L]。\n\n该函数将输出另一个整数，如下所示：\n\n例如 #cf_span[f(10, 9) = 0]，#cf_span[f(123, 321) = 121]，#cf_span[f(...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ T = (a_1, a_2, \\dots, a_n) $ with $ a_i \\in \\{0, 1, \\dots, 999999\\} $.  \nLet $ f(L) $ be a function on non-empty subsequences $ L \\subseteq T $, defined...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments