相关链接
题目传送门：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;
}