1879:
[Sdoi2009]Bill的挑战
Time Limit: 4
Sec Memory Limit: 64 MB
Description
Sheng_bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致Sheng_bill极度的不满。于是他再次挑战你。这次你可不能输！
这次，比赛规则是这样的：
给N个长度相同的字符串（由小写英文字母和’?’组成），S1, S2, …, SN，求与这N个串中的刚好K个串匹配的字符串T的个数（答案模1000003）。
若字符串Sx（1≤x≤N）和T匹配，满足以下条件：
1. Sx.length = T.length。
2. 对于任意1≤i≤Sx.length，满足Sx[i]=’?’或者Sx[i]=T[i]。
其中T只包含小写英文字母。
这次，比赛规则是这样的：
给N个长度相同的字符串（由小写英文字母和’?’组成），S1, S2, …, SN，求与这N个串中的刚好K个串匹配的字符串T的个数（答案模1000003）。
若字符串Sx（1≤x≤N）和T匹配，满足以下条件：
1. Sx.length = T.length。
2. 对于任意1≤i≤Sx.length，满足Sx[i]=’?’或者Sx[i]=T[i]。
其中T只包含小写英文字母。
Input
本题包含多组数据。
第一行：一个整数T，表示数据的个数。
对于每组数据：
第一行：两个整数，N和K（含义如题目表述）。
接下来N行：每行一个字符串。
T ≤ 5，N ≤ 15，字符串长度≤ 50。
Output
如题
Sample Input
5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??
Sample Output
914852
0
0
871234
67018
Solution
BZOJ的图片题让人看起来确实十分不适，于是笔者不辞劳苦将它转成了文字。
本题的Description部分描述的不甚清楚，无法理解题意的读者可以试着把“刚好”换成“恰好”，把“满足以下条件”换成“当且仅当”再次读题。
看到“恰好”，一个基本的思路是将其换成“至少”。由于N小于等于15，我们考虑使用状态压缩。注意到，与某一字符串S匹配的字符串的数量取决于S中’?’的数量。如果想计算出同时与两个字符串S1，S2匹配的字符串的数量，我们可以令S1与S2合并，记作S1∪S2。设S= S1∪S2，显然方案数取决于S中’?’的数量。合并操作的实现如下：
本题的Description部分描述的不甚清楚，无法理解题意的读者可以试着把“刚好”换成“恰好”，把“满足以下条件”换成“当且仅当”再次读题。
看到“恰好”，一个基本的思路是将其换成“至少”。由于N小于等于15，我们考虑使用状态压缩。注意到，与某一字符串S匹配的字符串的数量取决于S中’?’的数量。如果想计算出同时与两个字符串S1，S2匹配的字符串的数量，我们可以令S1与S2合并，记作S1∪S2。设S= S1∪S2，显然方案数取决于S中’?’的数量。合并操作的实现如下：
string merge(string a, string b)
{
int len = a.length();
string ans = "";
for (int i = 0; i<len; i++)
{
if (a[i] == b[i])ans += a[i];
else if (a[i] == '?')ans += b[i];
else if (b[i] == '?')ans += a[i];
else return "";
}
return ans;
}
这里用空字符串表示合并失败。
我们设strdp[i]表示状态i所表示的字符串合并后的结果，由于string对象不便于用memset快速、批量初始化。我们引入辅助变量bitdp[i]，bitdp[i]每一位描述strdp[i]在这一位上的字符，其中’?’用1表示，小写字母用0表示，比如”abc??ad?”用0011000表示（注意：字符串的高位在右侧，数字二进制的高位在左侧）。当strdp[i]=””时，bitdp[i]=-1，这样规定完全是为了用memset初始化。
设count1(x)表示x的二进制中1的个数，dp[i]表示与strdp[i]匹配的字符串的数量，显然，我们有dp[i]=26count1(bitdp[i])mod1000003。我们可以用搜索或动态规划求出dp、strdp、bitdp三个数组。这里给出用动态规划求解的实现：
//将bitdp[0]初始化为len个1
bitdp[0] = (1LL << len) - 1;
strdp[0] = "";
//将strdp[0]初始化为len个'?'
for (int i = 0;
i<len; i++)strdp[0] += '?';
for (int i = 0; i<(1
<< n); i++)
{
//如果当前状态可达
if (bitdp[i] != -1)
{
//pow26[i]表示pow(26,i)%mod
dp[i]
= pow26[count1(bitdp[i])];
for (int j = 0; j<n; j++)
{
//状态i的第j位是0，即状态i不包含字符串j
if (!(i&(1 << j)))
{
//尝试将当前状态与字符串j合并
strdp[i
| (1 << j)] = merge(strdp[i], str[j]);
//bitstr是str的二进制表示，方式与bitdp一样
bitdp[i
| (1 << j)] = bitdp[i] & bitstr[j];
//合并失败
if (strdp[i | (1 << j)] == "")
{
bitdp[i
| (1 << j)] = -1;
}
}
}
}
}
求解的过程比较容易想到，但dp数组中存放的不是最终答案。为了保证恰好，我们需要排除匹配了不只k个字符串的情况。我们可是枚举count1(i)=k的所有状态，对于每一个状态，我们枚举将strdp[i]看作一个整体，继续枚举其他字符串，用“奇加偶减”的方式去重。实现如下：
for (int i = 0; i<(1
<< n); i++)
{
if (count1(i)
== k)
{
int tmp = 0;
for (int j = 0; j<(1 << n); j++)
{
if ((j^i) == (j - i))
{
if ((count1(j)
- count1(i) + 1) & 1)
{
tmp
= (tmp + dp[j]) % mod;
}
else
{
tmp
= (tmp - dp[j] + mod) % mod;
}
}
}
ans
= (ans + tmp) % mod;
}
}
这段程序已经有些晦涩了。我们举例说明：
5 3
????ab
ab????
??ew??
???w??
????ab
我们令i=11001，即选择的字符串为”????ab”、”???w??”、”????ab”，strdp[i]=”???wab”，剩余的两个字符串为”ab????”和”??ew??”。我们首先试着笔算结果，将strdp[i]看作”??/?/wab”，前两个问号可以用除了ab外的任何一种方式填充，也就是有26×26-1中方式填充，后一个问号不能是e，也就是有26-1中填充方式。这样恰好与”????ab”、”???w??”、”????ab”这三个字符串匹配的字符串的数量为(26×26-1)×(26-1)=16857。或者用另一种方式计算：dp[11001]-dp[11101]-dp[11011]+dp[11111]，也就是与”????ab”、”???w??”、”????ab”匹配的方案数减去除了”????ab”、”???w??”、”????ab”匹配还与另一个字符串匹配的方案数，再加上重复的减去的方案数。用韦恩图表示如下：
(j^i) == (j - i)一行便是判断状态j是否为状态i的子集，从二进制的角度看，就是i中的每个1，在j中对于的位置也是1。
如果BZOJ的测评机不是土豆，这道题将就此结束。但可惜提交的结果是：
我们分析一下复杂度：最外层循环的次数为2n但只有count1(i)==k的状态才会进入第一个if语句，最坏情况为C(15,7)=6435，而对于内层循环，循环次数为2n，最坏情况为215=32768，这里姑且假设count1的用时为比较小的常数，最坏情况程序的循环次数为210862080，显然会TLE。
观察重复的计算：每一个状态j都会被使用多次，而可以使用状态j的状态i满足(j^i) == (j - i)，也就是说，从j的1中选出k个，将其余的1变成0，得到的新状态一定会使用状态j。这个数量为C(count1(j),count1(i))=C(count1(j),k)。于是统计答案的过程变成了：
for (int i = 0; i<(1 << n); i++)
{
int tmp = count1(i);
if (tmp >= k)
{
if ((tmp - k + 1)
& 1)
{
ans =
(ans + c[tmp][k] * dp[i] % mod) % mod;
}
else
{
ans =
(ans - c[tmp][k] * dp[i] % mod + mod) % mod;
}
}
}
注意到，tmp的含义发生了改变，现在它用于储存count1(i)，以进一步减少重复计算。
这道题其实还可以进一步优化，我们可以引入dp2，令dp2[i]=Σdp[j], where count1(j) = i。这样可以进一步减少统计答案时的循环次数，在BZOJ 3622的解题报告中读者可以看到这种优化。
Code
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
inline void read(int &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
inline void read(long long &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
string str[15];
int n, k, len;
//dp[i]——与用i表示的字符串都匹配的方案数
long long dp[32768];
//用状压表示字符串，0——a~z，1——?
long long bitstr[15];
long long bitdp[32768];
long long c[16][16];
string strdp[32768];
long long pow26[51];
long long ans = 0;
const long long mod = 1000003;
string merge(string a, string b)
{
int len = a.length();
string ans = "";
for (int i = 0;
i<len; i++)
{
if (a[i] == b[i])ans += a[i];
else if (a[i] == '?')ans += b[i];
else if (b[i] == '?')ans += a[i];
else return "";
}
return ans;
}
int count1(long long x)
{
int ans = 0;
while (x) { if (x & 1)ans++; x >>= 1; }
return ans;
}
int count1(int x)
{
int ans = 0;
while (x) { if (x & 1)ans++; x >>= 1; }
return ans;
}
int main()
{
int T;
read(T);
pow26[0] = 1;
for (int i = 1; i <=
50; i++)pow26[i] = pow26[i - 1] * 26 % mod;
c[0][0] = 1;
for (int i = 1; i <=
15; i++)
{
c[i][0] = 1;
for (int j = 1; j <=
i; j++)
{
c[i][j]
= (c[i - 1][j - 1] + c[i - 1][j]);
}
}
while (T--)
{
ans = 0;
memset(bitstr, 0, sizeof(bitstr));
memset(dp, 0, sizeof(dp));
memset(bitdp, 0xFF, sizeof(bitdp));
read(n); read(k);
if (k>n ||
k<0)
{
puts("0");
continue;
}
for (int i = 0; i<n;
i++)
{
cin >> str[i];
}
len =
str[0].length();
for (int i = 0; i<n;
i++)
{
for (int j = 0;
j<len; j++)
{
if (str[i][j] == '?')bitstr[i] |=
(1LL << j);
}
}
bitdp[0] =
(1LL << len) - 1;
strdp[0] = "";
//将strdp[0]初始化为len个'?'
for (int i = 0;
i<len; i++)strdp[0] += '?';
for (int i = 0; i<(1
<< n); i++)
{
//如果当前状态可达
if (bitdp[i] !=
-1)
{
//pow26[i]表示pow(26,i)%mod
dp[i]
= pow26[count1(bitdp[i])];
for (int j = 0; j<n;
j++)
{
//状态i的第j位是0，即状态i不包含字符串j
if (!(i&(1
<< j)))
{
//尝试将当前状态与字符串j合并
strdp[i
| (1 << j)] = merge(strdp[i],
str[j]);
//bitstr是str的二进制表示，方式与bitdp一样
bitdp[i
| (1 << j)] = bitdp[i] & bitstr[j];
//合并失败
if (strdp[i | (1
<< j)] == "")
{
bitdp[i
| (1 << j)] = -1;
}
}
}
}
}
for (int i = 0; i<(1
<< n); i++)
{
int tmp = count1(i);
if (tmp >= k)
{
if ((tmp - k + 1)
& 1)
{
ans
= (ans + c[tmp][k] * dp[i] % mod) % mod;
}
else
{
ans
= (ans - c[tmp][k] * dp[i] % mod + mod) % mod;
}
}
}
printf("%lld\n", ans);
}
return 0;
}
没有评论:
发表评论