【BZOJ 2471】Count

相关链接

题目传送门: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;
}

27 thoughts to “【BZOJ 2471】Count”

  1. 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.

  2. 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.

  3. 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!

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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 .

  9. 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!

  10. 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

  11. 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!

  12. 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!

  13. 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 =)

  14. 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!

  15. 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.

Leave a Reply

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