Description:

给出 $N$ 个串，每个串由小写字母或‘ ? ’组成，求与其中恰好 $K$ 个串匹配的字符串个数

$ 1 \le N \le 15 $ $ len \le 50 $

Solution:

$ f[i][j] $ 表示前 $i$ 位恰好与集合 $j$ 中的串匹配的字符串个数，注意是恰好，转移时枚举当前选哪个字符，注意需要保证"恰好"条件，设第 $i$ 位选字符 $j$ 能转移的集合为 $tag[i][j]$ ，则转移方程为：

$ f[i][k $ $\&$ $ tag[i][j]] $ = $\sum_{j='a'}^{'z'} f[i - 1][k]$

考虑它是怎样保证恰好条件的：若当前状态能保证恰好，则集合 $k$ 中可以从 $j$ 转移的子集（ $k\&tag[i][j]$ ）加上一个字符 $j$ 一定也不存在一个统计上的字符串可以满足其他状态

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000003

#define MAXN 16

#define MAXL 52

int cnt[1 << MAXN];

int testcases;

int n,k;

int l;

int f[MAXL][1 << MAXN];

char c[MAXN][MAXL];

void work()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)

	{

		scanf("%s",c[i]);

	}

	l = strlen(c[1]);

	for(int i = 1;i <= n;++i)

	{	

		for(int j = l;j >= 1;--j)

		{

			c[i][j] = c[i][j - 1];

		}

	}

	memset(f,0,sizeof(f));

	int tot = (1 << n) - 1;

	f[0][tot] = 1;

	for(int i = 1;i <= l;++i)

	{

		for(int j = 1;j <= 26;++j)

		{

			int tag = 0;

			for(int t = 1;t <= n;++t)

			{

				if(j + 'a' - 1 == c[t][i] || c[t][i] == '?')

				{

					tag |= (1 << (t - 1));

				}

			}

			for(int k = 0;k <= tot;++k)

			{

				f[i][k & tag] = (f[i][k & tag] + f[i - 1][k]) % MOD;

			}

		}

	}

	int ans = 0;

	for(int i = 0;i <= tot;++i)

	{

		if(cnt[i] == k)

		{

			ans = (ans + f[l][i]) % MOD;

		}

	}

	cout << ans << endl;

	return;

}

int main()

{

	cnt[0] = 0;

	for(int i = 1;i < (1 << MAXN);++i)

	{

		if(i & 1)cnt[i] = cnt[i >> 1] + 1;

		else cnt[i] = cnt[i >> 1];

	}

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)work();

	return 0;

}