参考例题：http://www.lydsy.com/JudgeOnline/problem.php?id=4589
#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];
//XOR
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;
}
/*
AND
if (opt == 1) {
arr[i + j] = t1 + t2;
//arr[i + j + d] = t2;
} else {
arr[i + j] = t1 - r2;
//arr[i + j + d] = t2;
}
*/
/*
OR
if (opt == 1) {
//arr[i + j] = t1;
arr[i + j + d] = t2 + t1;
} else {
//arr[i + j] = t1;
arr[i + j + d] = t2 - t1;
}
*/
}
}
}
}
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;
}
Normally I do not learn article on blogs, however I
would like to say that this write-up very pressured me to
check out and do so! Your writing style has been surprised me.
Thank you, very great post.
Wow! At last I got a web site from where I can in fact take valuable information concerning my study and knowledge.
We stumbled over here different website and thought I may as well check things out.
I like what I see so i am just following you. Look forward to exploring your
web page for a second time.
I need to to thank you for this very good read!! I definitely
loved every little bit of it. I have you bookmarked to check
out new things you post…
Everything is very open with a very clear explanation of the issues.
It was definitely informative. Your website is extremely helpful.
Many thanks for sharing!
If you wish for to increase your know-how only keep visiting this web site and
be updated with the most up-to-date news posted here.
I always spent my half an hour to read this website’s content all the time along with a mug of coffee.
hey there and thank you for your info – I have definitely picked up
anything new from right here. I did however expertise a few technical points using this web site, since I experienced to reload the website many times previous to I could get it to load properly.
I had been wondering if your web hosting is OK?
Not that I’m complaining, but slow loading instances times will often affect your
placement in google and could damage your high-quality score
if advertising and marketing with Adwords. Anyway I’m adding this RSS to my e-mail and could look out
for much more of your respective interesting content.
Make sure you update this again soon.
Some genuinely good articles on this site, regards for contribution. “He that falls in love with himself will have no rivals.” by Benjamin Franklin.
Hi, I do believe this is a great website. I stumbledupon it 😉 I am going
to come back yet again since i have book-marked it.
Money and freedom is the best way to change, may you be rich and continue to help others.
Superb blog! Do you have any recommendations for aspiring
writers? I’m planning to start my own blog 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 options out there that I’m totally overwhelmed ..
Any recommendations? Thank you!
It’s impressive that you are getting thoughts from this article as well as from
our argument made here.
It is perfect time to make a few plans for the future and it is time to be happy.
I have learn this submit and if I could I want
to suggest you some attention-grabbing issues or
tips. Maybe you could write next articles relating to this article.
I wish to learn even more issues about it!
Greetings! Very helpful advice in this particular article!
It is the little changes that will make the biggest changes.
Many thanks for sharing!
What i do not realize is in fact how you are not really a
lot more well-liked than you may be right now. You’re very intelligent.
You know therefore significantly relating to this subject, produced me
individually believe it from so many varied angles.
Its like men and women are not involved unless it is one thing to
accomplish with Lady gaga! Your personal stuffs nice.
At all times care for it up!
Your means of describing all in this paragraph is
really fastidious, all can without difficulty be aware of it, Thanks a
lot.
I don’t even know how I finished up here, but I believed this submit was once good.
I don’t recognize who you’re but certainly you are going to a famous blogger when you aren’t already.
Cheers!
Wonderful web site. A lot of useful information here. I am sending it to some friends ans also sharing in delicious. And obviously, thank you on your sweat!