描述

传送门：2018”百度之星”程序设计大赛 - 资格赛1001

度度熊为了完成毕业论文，需要收集一些数据来支撑他的论据，于是设计了一份包含 $m$ 个问题的调查问卷，每个问题只有 ‘A’ 和 ‘B’ 两种选项。

将问卷散发出去之后，度度熊收到了 $n$ 份互不相同的问卷，在整理结果的时候，他发现可以只保留其中的一部分问题，使得这 $n$ 份问卷仍然是互不相同的。这里认为两张问卷是不同的，当且仅当存在至少一个被保留的问题在这两份问卷中的回答不同。

现在度度熊想知道，存在多少个问题集合，使得这 n 份问卷在只保留这个集合的问题之后至少有 $k$ 对问卷是不同的。

Input

第一行包含一个整数 $T$，表示有 $T$ 组测试数据。

接下来依次描述 $T$ 组测试数据。对于每组测试数据：

第一行包含三个整数 $n$，$m$ 和 $k$，含义同题目描述。

接下来 $n$ 行，每行包含一个长度为 m 的只包含 ‘A’ 和 ‘B’ 的字符串，表示这份问卷对每个问题的回答。

保证 $1 \leq T \leq 100$，$1 \leq n \leq 10^3$，$1 \leq m \leq 10$，$1 \leq k \leq 10^6$，给定的 $n$ 份问卷互不相同。

Output

对于每组测试数据，输出一行信息 “Case #x: y”（不含引号），其中 x 表示这是第 x 组测试数据，y 表示满足条件的问题集合的个数，行末不要有多余空格。

Examples

intput
1
2
3
4
5
6
7
2
2 2 1
AA
BB
2 2 2
AA
BB
output
1
2
Case #1: 3
Case #2: 0

思路

暴力遍历所有问题集的情况，对于每种情况就枚举所有的试卷，对于每一张试卷，判断这种情况在这张试卷之前的试卷中有多少张是跟它一样的，然后减去。最后大于$k$就ans++。

把问题集和每张试卷状压一下，用二进制数表示。

对于问题集，用1表示取这个问题，0表示不取这个问题,例如选第1，3个问题，那么就是101对应十进制的3。

对于试卷，用1表示选$A$，0表示选$B$。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N = 1e3 + 5;

int main()
{
    int T, n, m, k, ans, a[N] = { 0 },M[1025];
    cin >> T; char x;
    rep(Case,1,T+1) {
        ans = 0;
        scanf("%d%d%d",&n,&m,&k); getchar();
        rep(i, 0, n)
            while ((x = getchar()) != '\n')
                a[i] = x == 'A' ? a[i] << 1 | 1 : a[i] << 1;    //状压答卷

        int Len=1<<m,tem;       //Len为问题集的情况总数
        rep(i, 1, Len) {        //遍历所有问题集
            CRL(M,0);tem=0;
            rep(j,0, n)         //遍历所有问卷
                tem+=j-M[a[j]&i]++;     //M[i]表示当前问题集的i答案的试卷数，a[j]&i表示当前问题集下，a[j]答卷的答案状态。

            if (tem >= k) ans++;    //如果有k对以上，ans++
        }
        printf("Case #%d: %d\n",Case,ans);
    }
    return 0;
}