[SDOI2009] Bill的挑战
题目信息
题目描述
Sheng_bill 不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。
这次，比赛规则是这样的：
给出 \(N\) 个长度相同的字符串（由小写英文字母和 ? 组成），\(S_1,S_2,\dots,S_N\)，求与这 \(N\) 个串中的刚好 \(K\) 个串匹配的字符串 \(T\) 的个数，答案对 \(1000003\) 取模。
若字符串 \(S_x(1\le x\le N)\) 和 \(T\) 匹配，满足以下条件：
- \(|S_x|=|T|\)。
- 对于任意的 \(1\le i\le|S_x|\)，满足 \(S_x[i]= \texttt{?}\) 或者 \(S_x[i]=T[i]\)。
其中 \(T\) 只包含小写英文字母。
输入格式
本题包含多组数据。
第一行一个整数 \(T\)，表示数据组数。
对于每组数据，第一行两个整数，\(N\) 和 \(K\)。
接下来 \(N\) 行，每行一个字符串 \(S_i\)。
输出格式
每组数据输出一行一个整数，表示答案。
样例 #1
样例输入 #1
5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??
样例输出 #1
914852
0
0
871234
67018
数据规模与约定
- 对于 \(30\%\) 的数据，\(N\le5\)，\(|S_i|\le20\)；
- 对于 \(70\%\) 的数据，\(N\le13\)，\(|S_i|\le30\)；
- 对于 \(100\%\) 的数据，\(1\le T\le 5\)，\(1\le N \le15\)，\(1\le|S_i|\le50\)。
思路分析
这道题和[CEOI2010 day2] pin真的差不多。
显然
\[g(S)=\sum_{T\supseteq S}{f(T)} \]根据广义容斥原理
\[f(S)=\sum_{T\supseteq S}{(-1)^{|S|-|T|}g(T)} \]\(g(S)\) 直接暴力求就行了，卡个常，就过了！
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e4+10;
namespace math{
int MOD;
int frac[MAXN];
int qpow(int a,int b){
if(b==0) return 1;
if(b==1) return a;
int k = qpow(a,b>>1);
k*=k;k%=MOD;
if(b&1) k*=a;k%=MOD;
return k;
}
int inv(int a){
return qpow(a,MOD-2);
}
int C(int n,int m){
if(n<m) return 0;
return frac[n]*inv(frac[m]*frac[n-m]%MOD)%MOD;
}
int get(int n,int m){
return C(m+n-1,m);
}
void init(){
frac[0] = 0;
for(int i = 1;i<MAXN;i++){
frac[i] = frac[i-1]*i;
frac[i]%=MOD;
}
}
int lowbit(int k){
return k&(-k);
}
int bit(int k){
int sum = 0;
while(k){
sum ++;
k -= lowbit(k);
}
return sum;
}
int log2(int k){
for(int i = 0;i<=64;i++){
int p = 1;
if(p<<i==k) return i;
}
return 0;
}
}
using namespace math;
int n,m,k,g[1<<16],f[1<<16];
bool can[1<<16];
vector<int> v[1<<16];
char tmp[20][60];
void read(int &n){
char tmp;
int x = 1;
do tmp = getchar();
while(!(tmp=='-'||('0'<=tmp&&tmp<='9')));
if(tmp=='-'){
x = -1;
}
int gz = 0;
while('0'<=tmp&&tmp<='9'){
gz*=10;
gz+=tmp-'0';
tmp = getchar();
}
n = gz*x;
}
namespace code{
using namespace math;
signed main(){
read(n);read(k);
for(int i = 0;i<n;i++){
char k;
k = getchar();
int u = 0;
while(k!='\n'){
tmp[i][u++] = k;
k = getchar();
}
tmp[i][u] = '\0';
}
m = strlen(tmp[1]);
vector<int> p;
for(int i = 0;i<(1<<n);i++){
can[i] = 1;g[i] = 1;
for(int j = 0;j<m;j++){
char k = '?';
for(int u:v[i]){
if(tmp[u][j]!='?'){
if(k=='?') k = tmp[u][j];
else if(k!=tmp[u][j]){
can[i] = false;
break;
}
}
}
if(!can[i]) break;
if(k=='?') g[i]*=26;
g[i]%=MOD;
}
if(!can[i]) g[i] = 0;
p.push_back(i);
}
int ans = 0;
for(int S:p){
f[S] = 0;
if(bit(S)==k){
for(int T:p){
if((T&S)==S){
f[S] += qpow(-1,bit(T)-bit(S))*g[T]%MOD;
f[S] %= MOD;
}
}
ans += f[S];
ans%=MOD;
}
}
// cout << 0b1010 << endl;
cout << (ans%MOD+MOD)%MOD << '\n';
return 0;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
math::MOD = 1e6+3;
frac[0] = 1;
for(int i = 1;i<=MAXN-1;i++){
frac[i] = frac[i-1]*i;
}
for(int i = 0;i<(1<<15);i++){
int k = i;
while(k){
v[i].push_back(math::log2(lowbit(k)));
k-=lowbit(k);
}
}
int T;
read(T);
while(T--){
code::main();
}
return 0;
}