相关链接
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4626
数据生成器:http://paste.ubuntu.com/24454724/
神犇题解Ⅰ:https://blog.sengxian.com/solutions/hdoj-4626
神犇题解Ⅱ:http://blog.csdn.net/u012345506/article/details/52040466
FWT相关:http://blog.csdn.net/liangzhaoyang1/article/details/52819835
解题报告
我们使用状压$DP$的话,每次询问相当于强制某些位为$0$
于是我们可以先$FWT$一发,搞出每个状态的方案数
然后我们可以再做一发子集$DP$,搞出每个状态的超集
然后询问就可以$O(1)$回答了
于是总的时间复杂度是:$O(20 \cdot 2^{20} + m + n)$
另外的话,因为本题的$k$非常的小
于是之前$FWT$那一块还可以用容斥来解决
只不过这样单次询问的复杂度是:$O(3^k)$的
Code
这个代码里$DP$超集那一块还是很妙妙的
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 3000000; const int M = 100009; const int UNIVERSE = (1 << 20) - 1; const int SGZ = 20; char pat[M]; int n,m,sta; LL a[N],f[N],zero; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void FWT(LL *arr, int len, int ty) { for (int d=1;d<len;d<<=1) { for (int i=0;i<=len;i+=d*2) { for (int j=0;j<d;j++) { LL t1 = arr[i+j], t2 = arr[i+j+d]; arr[i+j] = t1 + t2; arr[i+j+d] = t1 - t2; if (ty == -1) { arr[i+j] /= 2; arr[i+j+d] /= 2; } } } } } int main() { for (int T=read();T;T--) { memset(a, 0, sizeof(a)); scanf("%s",pat); n = strlen(pat); a[0]++; sta = zero = 0; for (int i=0;i<n;i++) { sta ^= 1 << pat[i] - 'a'; zero += a[sta]++; } FWT(a, UNIVERSE, 1); for (int i=0;i<=UNIVERSE;i++) { a[i] = a[i] * a[i]; } FWT(a, UNIVERSE, -1); a[0] = zero; for (int i=1;i<=UNIVERSE;i++) { a[i] /= 2; } for (int i=0;i<=UNIVERSE;i++) { if ((i ^ UNIVERSE) < i) { swap(a[i], a[i^UNIVERSE]); } } for (int j=0;j<SGZ;j++) { for (int i=0;i<=UNIVERSE;i++) { if (i & (1<<j)) { a[i^(1<<j)] += a[i]; } } } m = read(); for (int tt=1;tt<=m;tt++) { int k = read(), sta = 0; for (int i=1;i<=k;i++) { scanf("%s",pat); sta |= 1 << pat[0] - 'a'; } printf("%lld\n",a[sta]); } } return 0; }