# 【BZOJ 4589】Hard Nim

### 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];

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;
}


## 19 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!!

4. g说道：

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!

5. g说道：

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

6. This post will help the internet viewers for creating new web site or even a blog from start to end.

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

8. Wonderful, what a web site it is! This weblog gives useful data to us, keep it up.

9. I every time used to read paragraph in news papers but now as I am a user of internet so from now I
am using net for posts, thanks to web.

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

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

12. I always spent my half an hour to read this weblog’s articles or reviews everyday along
with a mug of coffee.

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

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

15. Greetings! Very helpful advice in this particular article! It is the little changes that make the biggest changes.

Thanks a lot for sharing!

16. No matter if some one searches for his necessary thing, so he/she
desires to be available that in detail, thus that thing is maintained over here.

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

18. I don’t even know how I ended up right here, but I thought this post was good.
I do not realize who you’re however certainly you are going to a well-known blogger in case you are