【Tsinsen 1255】拉拉队排练

题目传送门:http://www.tsinsen.com/A1255
离线版题目:http://paste.ubuntu.com/17831783/
数据生成:http://paste.ubuntu.com/17831834/

眼残,没看到只求长度为奇数,调了好久好久 QAQ
另外k可能会爆int QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const LL MOD = 19930726;

char pat[MAXN];
int n;

namespace Palindromic_Tree{
    #define PAM Palindromic_Tree
    #define SIGMA_SIZE 26
    int ch[MAXN][SIGMA_SIZE];
    int len[MAXN],sz[MAXN],fail[MAXN],ord[MAXN];
    int last,cnt; char *s; LL tag;
    
    inline bool cmp_sort(const int &a, const int &b){
        return len[a] > len[b];
    }
    
    inline void extend(int pos, int c){
        int w = last;
        while (s[pos-len[w]-1] != s[pos]) w = fail[w];
        if (!ch[w]){
            int nw = ++cnt,k=fail[w];
            len[nw] = len[w]+2;
            while (s[pos-len[k]-1] != s[pos]) k = fail[k];
            fail[nw] = ch[k]; ch[w] = nw; 
        }
        last = ch[w];
        sz[last] ++;
    }
    
    inline void GetSum(){
        for (int i=cnt;i;i--){
            sz[fail[i]] += sz[i];
            ord[i] = i; 
			if (len[i]&1) tag += sz[i];
        }
    }
    
    inline void build(char *S){
        fail[0] = fail[1] = 1; s = S;
        cnt = 1; len[1] = -1; last = 1;
        n = strlen(s+1);
        for (int i=1;i<=n;i++)
            extend(i,s[i]-'a');
        GetSum();
    }
    
    inline LL pow(LL a, LL t){
        LL ret = 1;
        while (t){
            if (t&1) ret *= a, ret %= MOD;
            a *= a; a %= MOD; t >>= 1;
        }
        return ret%MOD;
    }
    
    inline int solve(LL k){
        if (tag < k) return -1;
        else {
            sort(ord+1,ord+1+cnt,cmp_sort); LL ret = 1;
            for (int j=1,i=ord[1];j<=cnt && k;j++,i=ord[j]){
                if (!(len[i]&1)) continue;
				ret *= pow(len[i],min(k,(LL)sz[i]));
                ret %= MOD;
                k = max(0LL,k-(LL)sz[i]);
            }
            return int(ret%MOD);
        }
        
    }
};
int main(){
    LL n,k; cin>>n>>k;
    scanf("%s",pat+1);
    PAM::build(pat);
    printf("%d\n",PAM::solve(k));
    return 0;
}

289 thoughts to “【Tsinsen 1255】拉拉队排练”

  1. I think everything said made a lot of sense. However, think about this,
    what if you were to write a awesome headline?
    I ain’t suggesting your information is not good, but what if you added a title that makes people want more?
    I mean 【Tsinsen 1255】拉拉队排练 – Qizy's Database is a little plain.
    You might glance at Yahoo’s front page and see how they write news headlines to get people
    to click. You might try adding a video or a related picture or two to get
    people excited about everything’ve got to say.
    Just my opinion, it might make your blog a little livelier.

  2. Do you mind if I quote a couple of your posts as long as I provide
    credit and sources back to your weblog? My website
    is in the exact same niche as yours and my users would genuinely benefit from a lot of the information you provide here.
    Please let me know if this alright with you. Regards!

  3. After looking into a number of the blog articles on your website,
    I seriously appreciate your technique of writing a blog.
    I saved it to my bookmark webpage list and will be checking back soon. Please check
    out my web site too and tell me how you feel.

  4. great put up, very informative. I’m wondering why
    the other experts of this sector don’t notice this.
    You must proceed your writing. I’m confident, you’ve a huge readers’ base already!

  5. Just desire to say your article is as amazing.
    The clarity in your submit is just cool and i can suppose you’re knowledgeable in this subject.
    Fine with your permission let me to snatch your
    feed to stay updated with imminent post. Thanks one million and please carry on the
    rewarding work.

  6. My programmer is trying to persuade me to move to .net from PHP.
    I have always disliked the idea because of the costs.

    But he’s tryiong none the less. I’ve been using Movable-type on a number of websites
    for about a year and am nervous about switching to another platform.
    I have heard fantastic things about blogengine.net.
    Is there a way I can transfer all my wordpress content into it?
    Any help would be greatly appreciated!

  7. If some one desires expert view on the topic of blogging and site-building afterward i suggest him/her to visit this blog,
    Keep up the fastidious job. pof natalielise

  8. Definitely believe that that you said. Your favourite reason seemed to be on the web the easiest thing to
    consider of. I say to you, I certainly get annoyed even as people
    consider issues that they just do not recognise about.
    You managed to hit the nail upon the top as well as outlined out the whole thing
    without having side effect , people could take a
    signal. Will likely be back to get more. Thanks

  9. Remarkable things here. I’m very satisfied to see your article.
    Thank you so much and I’m looking forward to touch you. Will you kindly
    drop me a mail?

  10. I’m truly enjoying the design and layout of your website. It’s a very easy on the
    eyes which makes it much more enjoyable for me to come here and visit
    more often. Did you hire out a designer to create your theme?
    Outstanding work!

  11. I’ve read a few good stuff here. Definitely value
    bookmarking for revisiting. I surprise how so much attempt you
    set to make this kind of magnificent informative site.

  12. Have you ever thought about writing an ebook or guest authoring on other
    websites? I have a blog based upon on the same subjects you discuss and would love to have you share some
    stories/information. I know my audience would appreciate
    your work. If you’re even remotely interested, feel free to shoot me an e-mail.
    pof natalielise

  13. I am now not certain where you are getting your info, but great topic.

    I must spend some time finding out much more or understanding more.
    Thanks for magnificent information I was searching for this info
    for my mission.

  14. I loved as much as you will receive carried out right here.

    The sketch is attractive, your authored subject matter stylish.
    nonetheless, you command get got an impatience over that you wish be
    delivering the following. unwell unquestionably come more
    formerly again since exactly the same nearly a lot often inside case you shield this increase.

  15. Fantastic blog! Do you have any suggestions for aspiring writers?
    I’m planning 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 choices out there that I’m totally overwhelmed ..
    Any ideas? Thanks a lot!

  16. Wow that was unusual. I just wrote an incredibly long comment but after I clicked submit my comment
    didn’t show up. Grrrr… well I’m not writing all that over again.
    Anyway, just wanted to say excellent blog!

  17. I’ve learn some excellent stuff here. Certainly value
    bookmarking for revisiting. I wonder how so much attempt you place to make one of these excellent informative web site.

  18. Nice blog here! Additionally your site so much up fast!
    What host are you the use of? Can I get your associate hyperlink for your host?

    I wish my site loaded up as fast as yours lol

  19. Awesome blog! Do you have any tips for aspiring writers?

    I’m planning to start my own blog soon but I’m
    a little lost on everything. Would you advise starting with a free platform like WordPress or go for a paid option? There
    are so many choices out there that I’m totally overwhelmed
    .. Any ideas? Thank you!

  20. You could certainly see your expertise within the work you
    write. The sector hopes for more passionate writers like you who are not afraid to say how they believe.
    Always follow your heart.

  21. Hello there! This article could not be written much better!
    Looking through this post reminds me of my previous roommate!
    He continually kept talking about this. I most certainly will send this information to him.
    Pretty sure he’ll have a good read. Many thanks for
    sharing!

  22. It’s a pity you don’t have a donate button! I’d definitely donate to this outstanding blog!
    I suppose for now i’ll settle for bookmarking and adding your RSS feed
    to my Google account. I look forward to fresh updates and will talk about this website with my Facebook group.
    Chat soon!

  23. Undeniably believe that which you said. Your favorite reason appeared to be on the
    internet the easiest thing to be aware of. I say to you, I definitely get
    annoyed while people think about worries that they plainly
    don’t know about. You managed to hit the nail upon the top as well as defined out the whole thing without having side effect
    , people can take a signal. Will probably be back to get more.
    Thanks

  24. Can I simply just say what a relief to find somebody who really knows what they’re talking about online.
    You certainly understand how to bring an issue to light and make it important.
    A lot more people must check this out and understand this
    side of your story. I was surprised you are
    not more popular because you definitely have the gift.

  25. An intriguing discussion is worth comment. I do think that
    you ought to write more about this issue, it might not
    be a taboo subject but typically people do not discuss such subjects.
    To the next! Kind regards!!

  26. I’m really inspired together with your writing talents as well as
    with the format in your blog. Is this a
    paid subject or did you customize it your self? Anyway
    keep up the nice high quality writing, it’s uncommon to
    peer a great blog like this one these days..

  27. Have you ever considered about adding a little bit more than just your articles?

    I mean, what you say is fundamental and all. However just imagine if you added some great images or
    videos to give your posts more, “pop”! Your content is
    excellent but with images and video clips, this site could definitely
    be one of the very best in its field. Fantastic blog!

  28. Have you ever thought about including a little bit more than just your
    articles? I mean, what you say is important and all. But think about if you added some great
    pictures or video clips to give your posts more,
    “pop”! Your content is excellent but with images and videos, this blog could undeniably be one of the
    best in its niche. Terrific blog!

  29. Hello would you mind stating which blog platform you’re using?
    I’m looking to start my own blog soon but I’m
    having a hard time choosing between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your layout seems different then most blogs and
    I’m looking for something completely unique.
    P.S My apologies for being off-topic but I had to ask!

  30. Excellent post. I used to be checking continuously this weblog and I’m
    inspired! Extremely helpful info specifically the remaining section 🙂 I maintain such information a lot.

    I used to be looking for this certain info for a very lengthy time.
    Thanks and good luck.

  31. Howdy very nice website!! Man .. Beautiful .. Amazing ..
    I will bookmark your site and take the feeds also? I am glad
    to search out so many helpful information here within the
    publish, we’d like develop more strategies on this
    regard, thanks for sharing. . . . . .

  32. I’ll right away take hold of your rss as I can’t in finding your e-mail subscription hyperlink or newsletter service.

    Do you’ve any? Kindly let me recognise so that I
    could subscribe. Thanks.

  33. magnificent post, very informative. I wonder why the opposite experts
    of this sector don’t notice this. You must continue your writing.
    I am sure, you have a huge readers’ base already!

  34. of course like your web site but you need to
    take a look at the spelling on quite a few of your
    posts. Many of them are rife with spelling issues and I to
    find it very bothersome to inform the reality however I will
    definitely come again again.

  35. If some one desires expert view regarding blogging and site-building after that i advise him/her to pay a quick visit this web site, Keep
    up the pleasant job.

  36. I’ve been surfing online greater than three hours today,
    but I never found any fascinating article like yours. It’s lovely value sufficient for
    me. Personally, if all webmasters and bloggers made excellent content material as you did,
    the web will probably be a lot more helpful than ever
    before.

  37. We stumbled over here coming from a different web page and thought I might as well check
    things out. I like what I see so now i’m following you.
    Look forward to finding out about your web page again.

  38. Simply wish to say your article is as surprising. The clarity on your post is simply great and that i could think you’re knowledgeable in this subject.
    Fine along with your permission let me to grasp your feed to keep updated
    with drawing close post. Thanks a million and please continue the
    gratifying work.

  39. What i don’t understood is in truth how you’re not really much more neatly-liked than you might be right now.
    You’re so intelligent. You recognize thus significantly on the subject of this topic, produced me for my part imagine it from a lot of varied angles.
    Its like women and men don’t seem to be interested until it is one thing
    to accomplish with Woman gaga! Your personal stuffs outstanding.

    At all times maintain it up!

  40. Just want to say your article is as amazing. The clearness in your post is just cool
    and i can assume you are an expert on this subject.
    Well with your permission let me to grab your RSS feed to keep updated
    with forthcoming post. Thanks a million and please keep up the gratifying work.

  41. This is very interesting, You’re a very skilled blogger.
    I have joined your feed and look forward to seeking more of
    your fantastic post. Also, I’ve shared your website in my social networks!

  42. Its like you read my thoughts! You appear to understand a lot about this, like you wrote the e-book in it or something.
    I think that you simply can do with some % to force the message house a bit, but instead of that, that
    is excellent blog. A fantastic read. I’ll definitely be back.

  43. My partner and I stumbled over here by a different web address and thought I
    may as well check things out. I like what I see so
    now i’m following you. Look forward to exploring your web
    page again.

  44. Some really excellent content on this web site, thanks for contribution. “Once, power was considered a masculine attribute. In fact, power has no sex.” by Katharine Graham.

  45. I’m not positive where you’re getting your information, however good
    topic. I must spend a while finding out more or understanding more.
    Thank you for excellent information I used to be on the lookout for
    this info for my mission.

  46. Hi there! I could have sworn I’ve been to this website before
    but after browsing through some of the post I realized it’s new to me.
    Anyhow, I’m definitely glad I found it and
    I’ll be bookmarking and checking back often!

  47. Hiya very nice blog!! Man .. Excellent .. Amazing .. I’ll bookmark
    your website and take the feeds additionally? I am happy to seek out a lot
    of useful information right here in the publish, we’d like develop extra techniques on this regard, thank you for sharing.
    . . . . .

  48. Excellent blog here! Also your web site loads up fast!
    What host are you using? Can I get your affiliate link to your host?
    I wish my site loaded up as fast as yours lol

  49. I really like what you guys are up too. This kind of clever work and reporting!
    Keep up the very good works guys I’ve added you guys to my own blogroll.

  50. I would like to thank you for the efforts you’ve put in penning this website.
    I really hope to check out the same high-grade content by you in the future as
    well. In fact, your creative writing abilities has motivated me to get my own site
    now 😉

  51. I and also my pals were going through the excellent techniques found on your site then all of the sudden came up with a horrible suspicion I had not expressed respect to the website owner for them. My young men happened to be certainly joyful to study all of them and now have in truth been using those things. I appreciate you for simply being so helpful as well as for getting variety of terrific subject areas millions of individuals are really needing to know about. Our own honest regret for not expressing appreciation to sooner.

  52. you are in point of fact a just right webmaster. The site loading velocity is amazing. It seems that you are doing any unique trick. Furthermore, The contents are masterwork. you’ve performed a fantastic activity in this matter!|

  53. I’ve been browsing online more than 4 hours today, yet I never found any interesting article like yours. It is pretty worth enough for me. In my view, if all site owners and bloggers made good content as you did, the net will be a lot more useful than ever before.|

  54. I’m really enjoying the design and layout of your website. It’s a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a designer to create your theme? Exceptional work!|

  55. It’s perfect time to make some plans for the future and it is time to be happy. I’ve read this post and if I could I wish to suggest you some interesting things or tips. Maybe you could write next articles referring to this article. I want to read even more things about it!|

发表评论

电子邮件地址不会被公开。 必填项已用*标注