Sheng_bill 不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。
这次，比赛规则是这样的：
给出 (N) 个长度相同的字符串（由小写英文字母和 ? 组成），(S_1,S_2,dots,S_N)，求与这 (N) 个串中的刚好 (K) 个串匹配的字符串 (T) 的个数，答案对 (1000003) 取模。
若字符串 (S_x(1le xle N)) 和 (T) 匹配，满足以下条件：
- (|S_x|=|T|)。
- 对于任意的 (1le ile|S_x|)，满足 (S_x[i]= exttt{?}) 或者 (S_x[i]=T[i])。
其中 (T) 只包含小写英文字母。
(1le Tle 5)，(1le N le15)，(1le|S_i|le50)。
其实就是问有多少种字符串可以和恰好 (k) 个字符串匹配。
考虑容斥，设 (f_S) 表示只有 (S) 这个集合中的数匹配的方案数，设 (g_S) 表示至少有 (S) 这个集合中的数的匹配的方案数，那么就有，设 (q_x) 表示一个大小为 (x) 的集合的容斥系数：
[ans=sum_{|S|=k}f_S
]
[f_S=sum_{Sin T}q_{|T|}g_T
]
然后考虑算 (q_x) ，因为 (xge k) ，所以考虑大小为 (x) 的集合 (T) 中一个物品对 (S) 的贡献，那么这个的容斥系数是：
[q_x=sum_{i=k}^{x}{x-kchoose {i-k}}(-1)^{i-k}=sum_{i=0}^{x-k}{x-kchoose i}(-1)^{i}
]
[=(-1+1)^{x-k}
]
只有 (x=k) 时 (q_x=1) 。
所以最后的答案就是这个式子：
[ans=sum_{|S|ge k}{|S|choose |S|-k}(-1)^{|S|-k}g(S)
]
然后考虑怎么算 (g(s)) ，直接看每一位是不是一样的，如果都是 (?) ，说明这个位置有 (26) 种选择，所以记 (x) 为都是 (?) 的位数的个数，(g(s)=26^x) 。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 50;
const int M = 15;
const int p = 1e6 + 3;
using namespace std;
int T,n,k,len,ans,cnt[1 << M],C[M + 5][M + 5],m2[N + 5];
char ch[M + 5][N + 5];
void prework()
{
for (int s = 0;s < (1 << M);s++)
for (int j = 0;j < M;j++)
if ((s >> j) & 1)
cnt[s]++;
for (int i = 1;i <= M;i++)
{
C[i][0] = C[0][i] = 1;
for (int j = 1;j <= i;j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
}
m2[0] = 1;
for (int i = 1;i <= N;i++)
m2[i] = 26ll * m2[i - 1] % p;
}
int g(int S)
{
int sw = 0;
for (int l = 1;l <= len;l++)
{
int fl = 1;
char chr = 0;
for (int i = 1;i <= n;i++)
if ((S >> i - 1) & 1)
{
if (!chr && ch[i][l] == '?')
{
chr = '?';
fl = 2;
continue;
}
if (!chr)
{
chr = ch[i][l];
continue;
}
if (chr == '?' && ch[i][l] != '?')
{
chr = ch[i][l];
fl = 1;
continue;
}
if (chr != '?' && ch[i][l] == '?')
continue;
if (chr != '?' && ch[i][l] != chr)
{
fl = 0;
break;
}
}
if (!fl)
return 0;
if (fl == 2)
sw++;
}
return m2[sw];
}
int main()
{
scanf("%d",&T);
prework();
while (T--)
{
scanf("%d%d",&n,&k);
for (int i = 1;i <= n;i++)
scanf("%s",ch[i] + 1);
len = strlen(ch[n] + 1);
ans = 0;
for (int s = 0;s < (1 << n);s++)
{
if (cnt[s] < k)
continue;
ans += 1ll * C[cnt[s]][k] * (((cnt[s] - k) % 2 == 0) ? 1 : -1) * g(s) % p;
ans %= p;
}
printf("%d
",(ans + p) % p);
}
return 0;
}