相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2471
神犇题解:http://www.cnblogs.com/clrs97/p/5993606.html
解题报告
我们考虑从高位开始,逐位枚举。那么每枚举一位相当于将序列划分为10分,并且取其中一份。
对于一段连续的序列来讲,我们只需要关注其进入这段序列之前会匹配到x的哪一位、匹配完这一段之后匹配到了x的哪一位、这期间总共贡献了多少次成功的匹配。
不难发现这个状态是很少的,于是我们可以记忆化搜索。
另外这题很容易扩展到:“左右边界为任意值的情况”
然后我把这题搬到了今年的全国胡策里,不知道有没有人能切掉
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 16; const int M = 10; const int SGZ = 10; const int MOD = 1000000007; int n, m, nxt[M]; char s[M]; struct Transfer{ LL pos, cnt; inline Transfer() { } inline Transfer(LL a, LL b):pos(a), cnt(b) { } inline Transfer operator + (const Transfer &T) { return Transfer(T.pos, cnt + T.cnt); } }t[M][SGZ]; map<int, Transfer> f[N][M]; struct MatchStatus{ int HashVal; Transfer t[M]; inline void GetHashVal() { const static int MOD = 1000000007; const static int SEED1 = 13, SEED2 = 131; HashVal = 0; for (int i = 0; i < m; i++) { HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD; } } inline bool operator < (const MatchStatus &MS) const { return HashVal < MS.HashVal; } }; inline Transfer DFS(int w, int p, const MatchStatus &cur) { if (w <= 0) { return cur.t[p]; } else if (f[w][p].count(cur.HashVal)) { return f[w][p][cur.HashVal]; } else { Transfer ret(p, 0); for (int i = 0; i < SGZ; i++) { MatchStatus nw = cur; for (int j = 0; j < m; j++) { nw.t[j] = nw.t[j] + t[nw.t[j].pos][i]; } nw.GetHashVal(); ret = ret + DFS(w - 1, ret.pos, nw); } return f[w][p][cur.HashVal] = ret; } } int main() { while (~scanf("%d %s", &n, s + 1) && n) { m = strlen(s + 1); for (int i = 1; i <= m; i++) { s[i] -= '0'; } nxt[1] = 0; for (int i = 2, j = 0; i <= m; nxt[i++] = j) { for (; j && s[j + 1] != s[i]; j = nxt[j]); j += s[j + 1] == s[i]; } for (int i = 0; i < m; i++) { for (int j = 0; j < SGZ; j++) { int k = i; for (; k && s[k + 1] != j; k = nxt[k]); k += s[k + 1] == j; t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0); } } for (int i = 1; i <= n; i++) { for (int j = 0; j < m; j++) { f[i][j].clear(); } } Transfer ans(0, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j < SGZ; j++) { MatchStatus cur; for (int k = 0; k < m; k++) { cur.t[k] = t[k][j]; } cur.GetHashVal(); ans = ans + DFS(i - 1, ans.pos, cur); } } printf("%lld\n", ans.cnt); } return 0; }
brwoelpjd khzma iniocfo dveh okxuxmjxlnquvki
Hey There. I discovered your weblog the use of msn.
This is a very well written article. I’ll be sure to
bookmark it and return to read more of your helpful info.
Thank you for the post. I’ll certainly return.
Greetings I am so excited I found your website, I really found you by accident, while I was searching on Askjeeve for something else, Anyways I am
here now and would just like to say many thanks for a marvelous post
and a all round interesting blog (I also love the theme/design), I don’t have time to read it all at the
moment but I have book-marked it and also added in your RSS
feeds, so when I have time I will be back to read much more, Please do keep up the excellent work.
I don’t even know the way I ended up here, however
I thought this submit was once good. I do not understand who you are however certainly you’re going to a well-known blogger for those
who aren’t already. Cheers!
Quality posts is the crucial to invite the visitors to pay
a visit the website, that’s what this website is providing.
Heya i am for the primary time here. I found this board and I find It really useful & it helped me out much.
I hope to provide one thing back and help others like you helped me.
May I simply say what a comfort to discover somebody
who truly knows what they are discussing online.
You certainly know how to bring a problem to light and make it important.
More and more people should look at this and understand this side of
your story. It’s surprising you’re not more popular because you surely have
the gift.
It’s an remarkable piece of writing for all the internet
users; they will get advantage from it I am sure.
I think the admin of this web site is actually working hard for his
web page, for the reason that here every information is quality based information.
Hi, yes this paragraph is actually fastidious and I have learned lot of
things from it regarding blogging. thanks.
Magnificent goods from you, man. I’ve understand your
stuff previous to and you’re just too excellent. I really like what
you have acquired here, certainly like what you’re saying and the way in which you say it.
You make it enjoyable and you still take care of to keep it
sensible. I can not wait to read much more from you.
This is actually a terrific website.
Hi there to every body, it’s my first pay a quick visit of this blog;
this blog contains awesome and in fact excellent data for visitors.
Hi my family member! I wish to say that this article
is awesome, nice written and come with almost all vital infos.
I would like to peer more posts like this .
Wow, superb weblog format! How lengthy have you been blogging for?
you make blogging glance easy. The whole look of
your site is fantastic, let alone the content!
Nice blog! Is your theme custom made or did you download it from somewhere? A theme like yours with a few simple tweeks would really make my blog jump out. Please let me know where you got your design. Thank you
What i do not realize is in reality how you are now not really much more neatly-appreciated than you might be right now.
You are so intelligent. You already know therefore considerably
with regards to this subject, produced me for my part believe it from a
lot of numerous angles. Its like women and men aren’t involved
except it’s something to accomplish with Girl gaga!
Your own stuffs great. At all times deal with it up!
Hey are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started
and create my own. Do you require any html coding expertise to make your own blog?
Any help would be really appreciated!
Hola! I’ve been following your site for a long time now and finally got the bravery to go ahead and give you a shout out
from Dallas Tx! Just wanted to tell you keep up the excellent
job!
Wonderful article! This is the type of info that are meant to be
shared around the web. Disgrace on the seek engines for now
not positioning this publish higher! Come on over and discuss with my web
site . Thanks =)
Howdy! I know this is kinda off topic but I’d figured
I’d ask. Would you be interested in exchanging links or maybe guest authoring a blog post or vice-versa?
My site addresses a lot of the same subjects as yours
and I think we could greatly benefit from each other. If you might be interested feel free
to send me an email. I look forward to hearing from you!
Excellent blog by the way!
I read this article completely on the topic of the resemblance of most recent and previous technologies, it’s awesome article.
With havin so much written content do you ever run into any
issues of plagorism or copyright violation? My blog has a lot of completely unique content I’ve
either written myself or outsourced but it seems a lot of it
is popping it up all over the web without my authorization. Do you know any techniques to help prevent content
from being stolen? I’d certainly appreciate it.
I am continually invstigating online for posts that can aid me. Thanks!
What’s up, this weekend is fastidious in support of me,since this point in time i am reading this impressive educational article here at my house.
This site was… how do I say it? Relevant!! Finally I’ve found something which helped me.Thank you!
the time to read or stop by the subject material or web sites we’ve linked to below the
I really like it when individuals come together and share ideas.Great blog, stick with it!