#P1884. [Ipsc2008]Discover All Sets

    ID: 906 传统题 15000ms 888MiB 尝试: 25 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-折半枚举两半结果排序匹配状态编码可行性剪枝位集求交位集求补重复元素除重乘法原理

[Ipsc2008]Discover All Sets

题目描述

每张牌有 NN 项属性,每项属性的值都是 11 到 MM 中的一个整数。一副完整的牌包含所有 MNM^N 种属性组合,每种恰有一张。现在从中给出 KK 张不同的牌。

从给出的牌里选恰好 MM 张。如果对于每一项属性,这 MM 张牌在该项上的值要么全相同,要么两两不同,这组牌称为一个集合。请计算可以选出多少个不同的集合。每个集合内的牌没有顺序,不同集合可以共用牌。

输入格式

第一行一个整数 TT,表示数据组数。每组开头给出 N,M,KN,M,K,接下来 KK 行,每行 NN 个整数,表示一张牌的属性。空行可忽略。

本站使用 IPSC 2008 官方 D1、D2 两份固定数据,各有 1212 组。它们满足 4≤N≤104\le N\le10,3≤M≤83\le M\le8,6≤K≤50006\le K\le5000,NM≤64NM\le64,这些边界取自官方数据实际范围。官方题面提供的是固定输入文件。

输出格式

每组输出一行一个整数,表示不同集合数。输出精确值。

样例

1
4 3 12
1 1 1 2
2 3 3 3
2 2 3 1
1 3 1 3
3 3 3 3
1 2 1 1
2 1 3 2
1 1 3 2
2 3 2 3
1 3 2 3
3 2 1 1
3 1 2 2
11

IPSC 2008 组委会原题与官方数据