{"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":"CF800D"},"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 integer as follows:\n\n*   First, all integers in _L_ are padded with leading zeros so they are all the same length as the maximum length number in _L_.\n*   We will construct a string where the _i_\\-th character is the minimum of the _i_\\-th character in padded input numbers.\n*   The output is the number representing the string interpreted in base 10.\n\nFor example _f_(10, 9) = 0, _f_(123, 321) = 121, _f_(530, 932, 81) = 30.\n\nDefine the function\n\nHere, 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.\n\nYou 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.\n\n## Input\n\nThe first line contains the integer _n_ (1 ≤ _n_ ≤ 1 000 000) — the size of list _T_.\n\nThe next line contains _n_ space-separated integers, _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 999 999) — the elements of the list.\n\n## Output\n\nOutput a single integer, the answer to the problem.\n\n[samples]\n\n## Note\n\nFor 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.\n\nFor example, , since the subsequences \\[123\\] and \\[123, 555\\] evaluate to 123 when plugged into _f_.\n\nFor the second sample, we have\n\nFor the last sample, we have , where is the binomial coefficient.","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(530, 932, 81) = 30]。\n\n定义函数 \n\n换句话说，#cf_span[G(x)] 是对所有非空子序列 #cf_span[S] ⊆ #cf_span[T]，若 #cf_span[f(S) = x]，则将这些子序列的元素和的平方求和，再对 #cf_span[1 000 000 007] 取模，最后乘以 #cf_span[x]（最后一项乘法不取模）。\n\n你希望计算 #cf_span[G(0), G(1), ..., G(999 999)]。为减少输出大小，请输出这些值的异或和，其中  表示按位异或运算符。\n\n第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 000 000]) —— 列表 #cf_span[T] 的大小。\n\n第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 999 999]) —— 列表的元素。\n\n输出一个整数，即问题的答案。\n\n对于第一个样例，#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]。\n\n例如，，因为子序列 #cf_span[[123]] 和 #cf_span[[123, 555]] 在代入 #cf_span[f] 时均得到 #cf_span[123]。\n\n对于第二个样例，我们有 \n\n对于最后一个样例，我们有 ，其中  是二项式系数。\n\n## Input\n\n第一行包含整数 #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]) —— 列表的元素。\n\n## Output\n\n输出一个整数，即问题的答案。\n\n[samples]\n\n## Note\n\n对于第一个样例，#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]。对于第二个样例，我们有 对于最后一个样例，我们有 ，其中  是二项式系数。","is_translate":true,"language":"Chinese"}],"meta":{"iden":"CF800D","tags":["combinatorics","dp"],"sample_group":[["3\n123 321 555","292711924"],["1\n999999","997992010006992"],["10\n1 1 1 1 1 1 1 1 1 1","28160"]],"created_at":"2026-03-03 11:00:39"}}