相关链接
题目传送门：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;
}
I am actually grateful to the holder of this website who has
shared this impressive paragraph at at this
place.
My brother recommended I might like this website.
He was totally right. This post truly made my day. You can not imagine just how
much time I had spent for this info! Thanks!
Excellent post. I used to be checking continuously this weblog and I am inspired!
Extremely useful information specifically the ultimate phase 🙂 I take care of such information a lot.
I used to be looking for this particular information for a very lengthy time.
Thank you and best of luck.
I just couldn’t go away your site before suggesting that I extremely loved
the usual info an individual provide to your guests? Is going to
be back regularly to check up on new posts
Have you ever considered publishing an e-book or guest authoring on other sites?
I have a blog based on the same subjects you discuss and would really like to have you share some stories/information. I know my readers would
value your work. If you’re even remotely
interested, feel free to shoot me an e mail.
Have you ever thought about writing an ebook or
guest authoring on other blogs? I have a blog based upon on the same information you
discuss and would really like to have you share some stories/information. I know my audience
would appreciate your work. If you are even remotely interested, feel
free to send me an e-mail.
Howdy! I understand this is kind of off-topic however I needed to ask.
Does operating a well-established website such as yours take a massive amount work?
I’m completely new to operating a blog but I do write in my diary daily.
I’d like to start a blog so I can share my own experience and feelings online.
Please let me know if you have any kind of recommendations or tips for brand new aspiring blog owners.
Thankyou!
This piece of writing is actually a nice one it assists new net visitors, who are wishing
in favor of blogging.
Awesome post.
It’s very effortless to find out any topic on web as compared to textbooks, as I found this paragraph at this web page.
Pretty component of content. I just stumbled upon your blog and in accession capital to say that I acquire actually
enjoyed account your blog posts. Any way I will be subscribing
in your feeds and even I success you access constantly quickly.
I have been surfing on-line more than 3 hours nowadays, but I never discovered any interesting article like yours. It’s pretty price sufficient for me. In my view, if all site owners and bloggers made good content as you did, the internet will be much more helpful than ever before.
Hey! This is my 1st comment here so I just wanted to give a quick shout out
and tell you I really enjoy reading your posts.
Can you recommend any other blogs/websites/forums that deal with the same
topics? Thank you so much!
I’ve read some excellent stuff here. Definitely
price bookmarking for revisiting. I wonder how a lot attempt you set
to create any such wonderful informative site.
It’s hard to find knowledgeable people on this subject, however, you seem like you know what you’re talking about!
Thanks
Hiya! I know this is kinda off topic but I’d figured I’d
ask. Would you be interested in trading links or maybe guest
authoring a blog post or vice-versa? My blog discusses a lot of the same topics as yours and
I believe we could greatly benefit from each other. If you might be interested feel free to shoot me an e-mail.
I look forward to hearing from you! Wonderful blog by the way!
I absolutely love your blog.. Excellent colors & theme.
Did you build this website yourself? Please reply back as I’m wanting to
create my own personal blog and would like to learn where you got this from or just what the theme is
called. Kudos!
Amazing blog! Do you have any hints for aspiring writers?
I’m hoping to start my own website soon but I’m a little lost on everything.
Would you propose starting with a free platform like WordPress or go
for a paid option? There are so many options
out there that I’m completely overwhelmed .. Any recommendations?
Many thanks!
Thanks , I have recently been looking for information about
this subject for a long time and yours is the best I have found out so far.
But, what concerning the conclusion? Are you certain concerning the
source?
This is my first time visit at here and i am in fact pleassant to read all at single place.
Very quickly this web page will be famous among all blogging and site-building people, due to
it’s pleasant content
I keep listening to the news lecture about receiving boundless online grant applications so I have been looking around for the finest site to get one. Could you tell me please, where could i acquire some?