【BZOJ 4589】Hard Nim

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4589

解题报告

我们考虑用SG函数来暴力DP
显然可以用FWT来优化多项式快速幂
总的时间复杂度:$O(n \log n)$

Code

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

const int N = 100009; 
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
	for (int d = 1; d < len; d <<= 1) {
		for (int i = 0; i < len; i += d << 1) {
			for (int j = 0; j < d; j++) {
				int t1 = a[i + j], t2 = a[i + j + d];
				if (opt == 1) {
					a[i + j] = (t1 + t2) % MOD;
					a[i + j + d] = (t1 - t2) % MOD;
				} else {
					a[i + j] = (LL)(t1 + t2) * REV % MOD;
					a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
				}
			}
		}
	}
}

int main() {
	for (int n, m; ~scanf("%d %d", &n, &m); ) {
		memset(arr, 0, sizeof(arr));
		for (int i = 2; i <= m; i++) {
			if (!vis[i]) {
				arr[i] = 1;
				for (int j = i << 1; 0 <= j && j <= m; j += i) {
					vis[j] = 1;
				}
			}
		}
		int len = 1; 
		for (; len <= m; len <<= 1);
		FWT(arr, len);
		for (int i = 0; i < len; i++) {
			arr[i] = Pow(arr[i], n);
		}
		FWT(arr, len, -1);
		printf("%d\n", (arr[0] + MOD) % MOD);
	}
	return 0;
}

42 thoughts to “【BZOJ 4589】Hard Nim”

  1. You actually make it seem so easy with your presentation but
    I find this matter to be actually something which I
    think I would never understand. It seems too complicated and extremely broad for me.
    I am looking forward for your next post, I’ll try to
    get the hang of it!

  2. Oh my goodness! Incredible article dude!
    Thank you so much, However I am encountering issues with your RSS.
    I don’t know the reason why I cannot subscribe to
    it. Is there anybody getting similar RSS issues? Anyone who knows the solution will you kindly respond?
    Thanx!!

  3. Hey! Do you know if they make any plugins to assist with Search
    Engine Optimization? I’m trying to get my blog to rank
    for some targeted keywords but I’m not seeing very good success.
    If you know of any please share. Thank you!

  4. Hi there to every one, as I am actually eager of reading this webpage’s post to be updated regularly.
    It carries fastidious material.

  5. I do agree with all the ideas you have introduced for your post.
    They are really convincing and will definitely work.
    Still, the posts are too brief for starters. May you please extend them a bit from next time?

    Thanks for the post.

  6. Wow that was strange. I just wrote an really long comment
    but after I clicked submit my comment didn’t show up.
    Grrrr… well I’m not writing all that over again.
    Anyways, just wanted to say fantastic blog!

  7. Admiring the dedication you put into your website and in depth information you provide.

    It’s great to come across a blog every once in a while that isn’t the same old rehashed material.
    Great read! I’ve bookmarked your site and I’m including your RSS
    feeds to my Google account.

  8. Hi there, just became alert to your blog through Google, and found that it is really informative.
    I am gonna watch out for brussels. I will be
    grateful if you continue this in future. Numerous people
    will be benefited from your writing. Cheers!

  9. You are so awesome! I don’t believe I have read through a single thing like
    that before. So good to find another person with a
    few genuine thoughts on this subject. Seriously..

    many thanks for starting this up. This web site is something that is
    needed on the web, someone with some originality!

  10. Hey there! I know this is sort of off-topic however I had
    to ask. Does building a well-established blog such as yours require a lot of work?
    I am brand new to writing a blog however I do write
    in my journal everyday. I’d like to start a blog so I can share
    my personal experience and feelings online. Please let me know if you have any kind of suggestions or tips for new aspiring blog
    owners. Thankyou!

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

  12. I got this website from my buddy who informed me on the topic of this web page and now this time I am
    browsing this web site and reading very informative
    articles at this place.

  13. Hello! I could have sworn I’ve been to this website
    before but after going through many of the posts I realized it’s new to
    me. Anyways, I’m certainly pleased I found it and I’ll be
    bookmarking it and checking back frequently!

  14. What i don’t understood is in truth how you’re now not really
    a lot more smartly-favored than you may be now. You are so intelligent.
    You already know therefore significantly when it comes to
    this topic, made me for my part consider it from a lot of varied angles.
    Its like women and men aren’t fascinated unless it’s one thing to do with Girl gaga!
    Your individual stuffs outstanding. At all times handle it
    up!

  15. Pretty nice post. I just stumbled upon your weblog and wanted to say that I’ve
    really enjoyed surfing around your blog posts.
    In any case I’ll be subscribing to your rss feed and I hope you write again very soon!

  16. Nice weblog right here! Additionally your web site so much up very fast!
    What web host are you the use of? Can I get your affiliate link for your host?
    I wish my website loaded up as quickly as yours lol

  17. Hmm it appears like your site ate my first comment (it was super long)
    so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.

    I too am an aspiring blog blogger but I’m still new to everything.

    Do you have any helpful hints for newbie blog writers?
    I’d genuinely appreciate it.

  18. Pretty component of content. I simply stumbled upon your site and in accession capital to say that I get actually enjoyed account your blog posts.
    Any way I’ll be subscribing to your augment or even I achievement you get admission to constantly fast.

  19. Hello, i read your blog from time to time and i own a similar one and i was just wondering if you get a lot of spam feedback?
    If so how do you reduce it, any plugin or anything you can advise?

    I get so much lately it’s driving me mad so any support is very much appreciated.

  20. Hi there! I know this is kind of off topic but I was
    wondering if you knew where I could find a captcha plugin for my
    comment form? I’m using the same blog platform as yours and I’m
    having trouble finding one? Thanks a lot! pof natalielise

  21. hello there and thank you for your information – I have
    definitely picked up anything new from right here. I did however expertise several technical issues using this web site, since I experienced to
    reload the web site a lot of times previous to I could get it to load
    correctly. I had been wondering if your web host is
    OK? Not that I’m complaining, but sluggish loading instances times will very frequently affect your
    placement in google and can damage your quality score if ads and marketing
    with Adwords. Anyway I am adding this RSS to my e-mail and
    could look out for much more of your respective intriguing content.
    Ensure that you update this again very soon.

  22. Simply wish to say your article is as amazing. The clarity in your post is just cool and i can assume you are an expert on this subject.
    Fine with your permission allow me to grab your feed to keep up to date with forthcoming
    post. Thanks a million and please continue the gratifying work.

  23. I like the valuable information you supply to your articles.
    I will bookmark your blog and test again here regularly.
    I am reasonably certain I’ll be informed a lot of new stuff proper right here!
    Best of luck for the following!

  24. Your style is unique in comparison to other folks
    I’ve read stuff from. I appreciate you for posting when you’ve got
    the opportunity, Guess I will just bookmark this site.

  25. Great beat ! I would like to apprentice while you amend
    your website, how could i subscribe for a blog web site?

    The account helped me a acceptable deal. I had been a little bit acquainted of this your broadcast offered bright
    clear idea

  26. I have to thank you for the efforts you have put in penning this website. I’m hoping to view the same high-grade content by you later on as well. In fact, your creative writing abilities has encouraged me to get my own blog now 😉

发表评论

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