{"problem":{"name":"K. Counting Good Teams","description":{"content":"When building teams for programming competitions, it is a good idea to team up people that are good at different topics. For instance, it would be a good idea to team up someone who is good at graph p","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10148K"},"statements":[{"statement_type":"Markdown","content":"When building teams for programming competitions, it is a good idea to team up people that are good at different topics. For instance, it would be a good idea to team up someone who is good at graph problems and bad at geometry problems with someone who is good at geometry problems but bad at graph problems.\n\nGEMA is a programming competition study group with N members. GEMA coaches are interested in counting the number of different good teams that can be created. A good team is composed of 2 members and each member is good at at least one topic that his teammate isn't good at. Two teams are considered different if at least one member is present in one team but not in the other.\n\nGEMA coaches are only considering the M most important topics, and they know, for each member, which topics they are good at, and which topics they are bad at.\n\nThe first line of the input contains two integers N (2 ≤ N ≤ 105) and M (2 ≤ M ≤ 21), indicating respectively the number of members in the study group and the number of topics that are being considered. \n\nThe second line contains N integers. The i-th integer corresponds to xi (0 ≤ xi < 2M). The j-th least significant digit of the binary representation of xi is 1 if the i-th member is good at the j-th topic and 0 otherwise. For instance, if M = 5 and the i-th member has xi = 11 = (01011)2, it means that he is good at the first, second and fourth topic and bad at the third and fifth topic.\n\nOutput a single integer: the number of different good teams that can be created.\n\n## Input\n\nThe first line of the input contains two integers N (2 ≤ N ≤ 105) and M (2 ≤ M ≤ 21), indicating respectively the number of members in the study group and the number of topics that are being considered. The second line contains N integers. The i-th integer corresponds to xi (0 ≤ xi < 2M). The j-th least significant digit of the binary representation of xi is 1 if the i-th member is good at the j-th topic and 0 otherwise. For instance, if M = 5 and the i-th member has xi = 11 = (01011)2, it means that he is good at the first, second and fourth topic and bad at the third and fifth topic.\n\n## Output\n\nOutput a single integer: the number of different good teams that can be created.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z} $ with $ 2 \\leq N \\leq 10^5 $, $ 2 \\leq M \\leq 21 $.  \nLet $ A = (x_1, x_2, \\dots, x_N) $ be a sequence of integers, where each $ x_i \\in \\{0, 1, \\dots, 2^M - 1\\} $ represents the set of topics member $ i $ is good at, encoded as a bitmask: bit $ j $ (0-indexed from LSB) is 1 iff member $ i $ is good at topic $ j+1 $.\n\n**Constraints**  \nFor all $ i \\in \\{1, \\dots, N\\} $: $ 0 \\leq x_i < 2^M $.\n\n**Objective**  \nCount the number of unordered pairs $ \\{i, j\\} $ with $ i \\neq j $ such that:  \n$$\n(x_i \\setminus x_j) \\neq \\emptyset \\quad \\text{and} \\quad (x_j \\setminus x_i) \\neq \\emptyset\n$$  \nEquivalently:  \n$$\nx_i \\not\\subseteq x_j \\quad \\text{and} \\quad x_j \\not\\subseteq x_i\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10148K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}