#PQJ211x4131. QOJ 211_4131
QOJ 211_4131
济南,中国环渤海地区南翼和黄河中下游地区中心城市,山东省省会,山东省第一大城 市,山东省政治、文化、教育中心,华东五大城市之一,区域性金融中心,副省级城市。济南位于山东省中西部,北临黄河,南依泰山。济南分别与西南部的聊城、北部的德州和滨州, 东部的淄博、南部的莱芜和泰安交界。济南有着2700余年的历史,是龙山文化的发祥地。 因境内有“七十二名泉”故被称为“泉城”,并素有“四面荷花三面柳,一城山色半城湖” 的美誉“济南历史上涌现了很多文人墨客,著名有李清照、辛弃疾等。济南是国家创新型城市、中国软件名城、全国重耍的交通枢纽和物流中心。继济南全运会取得圆满成功后,2013 年济南将举办第十届中国艺术节,并成为2015年“第二十二届国际历史科学大会”的主办 城市,为济南建设国际大都市注入了新的活力。
济南市“泉历史研究小组”依据济南特有的泉脉关系将济南的泉水分为六个区域,分别是市中区、历下区、天桥区、槐荫区、历城区、长清区。
作为光荣的济南泉历史研究小组中的一员,铭铭收集了历史上N个不同年份时不同泉区 的泉水流量指数,这个指数是一个小于 2 30 的非负整数。第i个年份时六个泉区的泉水流量指数分别为 , 𝐴 ( 𝑖 , 1 ) , , 𝐴 ( 𝑖 , 2 ) , , 𝐴 ( 𝑖 , 3 ) , , 𝐴 ( 𝑖 , 4 ) , , 𝐴 ( 𝑖 , 5 ) 与 , 𝐴 ( 𝑖 , 6 ) 。
现在铭铭希望知道有多少对不同的年份: 𝑖 和 𝑗 ,满足这两年恰好有 𝐾 个泉区的泉水流量指数对应相同。
输入格式
第一行有 2 个整数,分别是 𝑁 和 𝐾 。
之后 𝑁 行,每行有 6 个整数。第 𝑖 行的第 𝑗 个数字 𝐴 ( 𝑖 , 𝑗 ) 表示第 𝑖 个年份中第 𝑗 个泉区的泉水流量指数。
输出格式
只一行,一个整数。表示有多少对不同的年份,满足恰有 𝐾 个泉区的泉水流量指数对应相同。
样例数据 样例输入 3 3 1 2 3 4 5 6 1 2 3 0 0 0 0 0 0 4 5 6 样例输出 2 子任务 测试点 特殊性质
1 ∼ 4
𝑁
1 000
5 ∼ 11
𝑁
10 4
12 ∼ 17
𝐴 ( 𝑖 , 𝑗 ) ≤ 18
18 ∼ 25 无
对于 100 % 的数据, 1 ≤ 𝑁 ≤ 10 5 , 0 ≤ 𝐾 ≤ 6 ,且所有数据中 𝐾 是等概率出现的,即对于任意的 0 ≤ 𝑥 ≤ 6 ,都有大约 1 / 7 的数据中 𝐾
𝑥 。