【Codeforces 696D】Legen…

Qizy AC Automaton, 字符串, 数论, 矩阵快速幂, 解题报告

题目传送门：http://codeforces.com/contest/696/problem/D
官方题解：http://codeforces.com/blog/entry/46031

这个题目，看一眼数据范围就知道是AC自动机+矩阵快速幂
所以剩下的唯一问题就是，我们重定义矩阵运算之后为何其仍然满足结合律？

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200+9;
const int SGZ = 27;
const int MX = 201;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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;
}

struct Matrix{
	LL a[N][N];
	inline Matrix() {memset(a,-1,sizeof(a));}
	inline Matrix(Matrix &v) {memcpy(this,&v,sizeof(v));}
	inline Matrix(int bas, int v) {memset(a,bas,sizeof(a));for (int i=1;i<=MX;i++) a[i][i]=v;}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret; 
		for (int i=1;i<=MX;i++) for (int j=1;j<=MX;j++) for (int k=1;k<=MX;k++) 
			if (~a[k][j] && ~B.a[i][k]) ret.a[i][j] = max(ret.a[i][j], a[k][j] + B.a[i][k]);
		return ret;
	}
	inline Matrix operator ^ (LL t) {
		Matrix ret(-1,0), tmp(*this); while (t) {
			if (t & 1) ret = ret * tmp;
			tmp = tmp * tmp; t >>= 1;
		} return ret; 
	} 
}tran,ans;

namespace AC_Automaton{
	#define ATM AC_Automaton
	int ch[N][SGZ],fail[N],val[N],cnt=1,vis[N];
	queue<int> que;
	
	inline void Add(char *s, int v){
		int w = 1, n = strlen(s+1);
		for (int i=1;i<=n;i++) {
			int c = s[i] - 'a' + 1;
			if (!ch[w]) ch[w] = ++cnt;
			w = ch[w];
		} val[w] += v;	
	}
	
	inline void Get_Fail(){
		que.push(1); fail[0] = fail[1] = 1; 
		for (int i=1;i<SGZ;i++) ch[1][i] = ch[1][i]?ch[1][i]:1;
		while (!que.empty()) {
			int w = que.front(); que.pop();
			val[w] += val[fail[w]]; vis[w] = 1;
			for (int c=1;c<SGZ;c++) if (ch[w]) {
				int nw = fail[w];
				while (nw > 1 && !ch[nw]) nw = fail[nw];
				fail[ch[w]] = nw!=w?ch[nw]:1; 
				if (!vis[ch[w]]) que.push(ch[w]);
			} else ch[w] = ch[fail[w]];
		}
	}
	
	inline void Build_Matrix(){
		ans.a[1][1] = 0;
		for (int i=1;i<=cnt;i++)
			for (int c=1;c<SGZ;c++) 
				tran.a[ch[i]][i] = val[ch[i]];	
	}
}; 

int main(){
	int n,val[N]; LL T; char pat[N]; cin>>n>>T;
	for (int i=1;i<=n;i++) cin>>val[i];
	for (int i=1;i<=n;i++) scanf("%s",pat+1), ATM::Add(pat,val[i]);
	ATM::Get_Fail(); ATM::Build_Matrix(); tran = tran^T; 
	ans = ans * tran; LL vout = 0; 
	for (int i=2;i<=MX;i++) vout = max(vout, ans.a[i][1]);
	printf("%I64d\n",vout);
 	return 0;
}

—– UPD 2016.10.2 —–
今天问了一下鏼爷，鏼爷给了一个非常简洁的证明：
最短路问题可以写成矩阵形式（比如倍增Floyd）
然后最短路显然满足结合律
然后这题对于矩乘的定义岂不是和最短路一样？

—————————— UPD 2017.2.1 ——————————
这题后来问了问YYY，结果YYY暴力展开矩乘
似乎这样就可以知道是否满足结合律了
不过如果在考场上，直接拍一拍吧
如果不出错，那就假装他满足结合律吧？

245 thoughts to “【Codeforces 696D】Legen…”

  2. I was wondering if you ever thought of changing the structure of your website?
    Its very well written; I love what youve got to say.
    But maybe you could a little more in the way of content so people could connect with it better.
    Youve got an awful lot of text for only having 1
    or 2 pictures. Maybe you could space it out better?

    Reply

  4. Thanks for your marvelous posting! I actually enjoyed reading it, you might be
    a great author. I will make sure to bookmark your blog and definitely will come back very soon.
    I want to encourage you to continue your great work, have a nice morning!

    Reply

  5. I know this if off topic but I’m looking into starting my own weblog and was curious what all is needed to get set up?
    I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web savvy so I’m not 100% sure.
    Any recommendations or advice would be greatly appreciated.
    Kudos

    Reply

  8. Great beat ! I would like to apprentice while you amend your site,
    how could i subscribe for a blog website? The account aided me a acceptable deal.
    I had been tiny bit acquainted of this your broadcast provided bright clear concept

    Reply

  9. Undeniably believe that which you said. Your favorite
    justification seemed to be on the web the easiest thing to
    be aware of. I say to you, I definitely get annoyed while people think about worries that
    they plainly do not know about. You managed to hit the
    nail upon the top as well as defined out the whole thing without having side-effects , people could take a signal.

    Will likely be back to get more. Thanks

    Reply

  10. Howdy! Quick question that’s completely off topic. Do you know
    how to make your site mobile friendly? My blog looks weird when browsing from my iphone
    4. I’m trying to find a theme or plugin that might be able to
    correct this problem. If you have any recommendations, please share.
    Thank you!

    Reply

  15. of course like your web-site however you have to take
    a look at the spelling on quite a few of your posts.
    Several of them are rife with spelling issues and I find it very troublesome to
    inform the truth nevertheless I will surely come back again.

    Reply

  17. Everything is very open with a very clear clarification of the challenges.
    It was really informative. Your site is very useful.
    Thanks for sharing! natalielise plenty of fish

    Reply

  18. I think this is among the most important info for me.
    And i’m glad reading your article. But want to remark on some general things,
    The site style is wonderful, the articles is really excellent : D.
    Good job, cheers

    Reply

  19. Hi, I do think this is a great site. I stumbledupon it 😉 I’m going to
    return once again since i have book-marked it.
    Money and freedom is the best way to change, may you be rich and continue to guide
    other people.

    Reply

  21. An outstanding share! I’ve just forwarded this onto a colleague who has been doing a little homework on this.
    And he actually ordered me lunch because I discovered it for him…
    lol. So let me reword this…. Thanks for the meal!! But yeah, thanx for spending the time to
    talk about this issue here on your site.

    Reply

  25. This is really attention-grabbing, You’re a very professional blogger.
    I’ve joined your feed and stay up for in search of more of your wonderful post.

    Additionally, I have shared your web site in my social networks

    Reply

  27. You really make it appear so easy with your presentation however I in finding this topic to be actually something which I think I’d
    by no means understand. It sort of feels too complex and extremely huge for
    me. I am looking ahead on your next submit, I’ll attempt to get
    the cling of it!

    Reply

  28. Howdy! This post couldn’t be written any better! Reading through this post reminds me of my previous room mate!
    He always kept talking about this. I will forward this post to him.
    Fairly certain he will have a good read. Many thanks for sharing!

    Reply

  29. I loved as much as you’ll receive carried out right here.
    The sketch is tasteful, your authored subject matter
    stylish. nonetheless, you command get bought an nervousness
    over that you wish be delivering the following. unwell unquestionably come further
    formerly again as exactly the same nearly a lot often inside
    case you shield this hike.

    Reply

  33. When I initially commented I clicked the “Notify me when new comments are added” checkbox and now
    each time a comment is added I get three emails with the same comment.
    Is there any way you can remove me from that service? Appreciate it!

    Reply

  39. I really like what you guys are usually up too. This kind of clever work and coverage!
    Keep up the fantastic works guys I’ve incorporated you guys to my blogroll.

    Reply

  40. I’m extremely impressed with your writing skills as well as
    with the layout on your weblog. Is this a paid theme or did you customize it yourself?
    Anyway keep up the excellent quality writing, it’s rare to
    see a great blog like this one nowadays.

    Reply

  52. It is appropriate time to make a few plans for the future and
    it is time to be happy. I’ve learn this post and if I could I wish to counsel you few
    interesting issues or tips. Perhaps you could write subsequent articles
    regarding this article. I desire to read even more
    issues approximately it!

    Reply

  61. Hi there! Someone in my Facebook group shared this site with us so I came to
    look it over. I’m definitely loving the information. I’m book-marking and will be tweeting this to my followers!
    Great blog and amazing design.

    Reply

  66. My partner and I absolutely love your blog and find many of
    your post’s to be just what I’m looking for.
    can you offer guest writers to write content for yourself?

    I wouldn’t mind creating a post or elaborating
    on a number of the subjects you write regarding
    here. Again, awesome blog!

    Reply

  69. Hello there! This article couldn’t be written any better!

    Looking at this post reminds me of my previous roommate!
    He constantly kept talking about this. I most certainly will send
    this article to him. Fairly certain he’s going to have a very good read.

    I appreciate you for sharing!

    Reply

  77. Appreciating the persistence you put into your blog and in depth information you offer.

    It’s nice to come across a blog every once in a while that isn’t the same unwanted rehashed material.

    Wonderful read! I’ve bookmarked your site and I’m including
    your RSS feeds to my Google account.

    Reply

  97. I absolutely love your site.. Very nice colors & theme.
    Did you build this web site yourself? Please reply back as I’m trying
    to create my own personal blog and want to find out where you got this from or just what
    the theme is called. Many thanks!

    Reply

  98. Attractive component to content. I simply stumbled upon your web
    site and in accession capital to say that I acquire
    in fact enjoyed account your blog posts. Anyway I will be
    subscribing for your feeds and even I fulfillment you get admission to persistently fast.

    Reply

  99. Thanks for the good writeup. It actually was a
    enjoyment account it. Look complicated to far brought agreeable from you!
    By the way, how could we be in contact?

    Reply

  104. Thanks for every other magnificent post. Where else could anybody get that type
    of info in such an ideal manner of writing? I’ve a
    presentation subsequent week, and I am on the search for such info.

    Reply

  108. Today, I went to the beach with my children. I
    found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.”
    She put the shell to her ear and screamed. There was a hermit crab
    inside and it pinched her ear. She never wants to go back!
    LoL I know this is entirely off topic but I had to tell someone!

    Reply

  111. Today, I went to the beach front with my kids.
    I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell
    to her ear and screamed. There was a hermit crab inside and it pinched her
    ear. She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!

    Reply

  113. Simply wanna comment on few general things, The website pattern is perfect, the articles is real wonderful. “If a man does his best, what else is there” by George Smith Patton, Jr..

    Reply

  135. I love what you guys are usually up too. Such clever work and exposure!
    Keep up the superb works guys I’ve incorporated you guys to blogroll.

    Reply

  150. Spot on with this write-up, I honestly believe this web site needs a lot more attention. I’ll probably be returning to see more, thanks for the advice!

    Reply

  151. Heya i am for the first time here. I found this board and I in finding It truly useful & it helped me
    out a lot. I hope to give one thing back and help others
    such as you aided me.

    Reply

  161. I’m impressed, I must say. Rarely do I encounter a blog that’s equally educative and engaging,
    and without a doubt, you have hit the nail on the head.
    The issue is an issue that not enough men and women are speaking intelligently about.

    I’m very happy that I found this during my search
    for something concerning this.

    Reply

  176. I was recommended this web site by my cousin. I’m not sure whether this post is written by
    him as nobody else know such detailed about my trouble. You’re wonderful!
    Thanks!

    Reply

  178. Sweet blog! I found it while searching on Yahoo News. Do you have any tips on how
    to get listed in Yahoo News? I’ve been trying for a while but I never seem to get
    there! Cheers

    Reply

  243. [url=https://atorvastatinlipitor.com/]lipitor 10mg price australia[/url] [url=https://zoloftgen.com/]zoloft 10[/url] [url=https://wellbutrinlab.com/]wellbutrin drug[/url]

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *